tree – Rooted and binary trees. Spanning trees, BFS, DFS, Spanning trees in a weighted graph. TREES
• Tree is a hierarchical data structure which stores
the information naturally in the form of hierarchy style. • Tree is a non-linear data structure which organizes data in hierarchical structure and this is a recursive definition. • It is a non-linear data structure compared to arrays, linked lists, stack and queue. • It represents the nodes connected by edges. TREES
Tree has 2 subtrees.
A is a parent of B and C. B is called a child of A and also parent of D, E, F. TREES • In tree data structure, every individual element is called as Node. Node in a tree data structure stores the actual data of that particular element and link to next element in hierarchical structure.
In a tree data structure, if we have N number of
nodes then we can have a maximum of N-1 number of links. Terminology • In a tree data structure, we use the following terminology... • 1. Root • In a tree data structure, the first node is called as Root Node. Every tree must have a root node. We can say that the root node is the origin of the tree data structure. In any tree, there must be only one root node. 2. Edge The connecting link between any two nodes is called as EDGE. In a tree with 'N' number of nodes there will be a maximum of 'N-1' number of edges. • 3. Parent • The node which is a predecessor of any node is called as PARENT NODE. In simple words, the node which has a branch from it to any other node is called a parent node. Parent node can also be defined as "The node which has child / children". 4. Child The node which is descendant of any node is called as CHILD Node. In simple words, the node which has a link from its parent node is called as child node. In a tree, any parent node can have any number of child nodes. In a tree, all the nodes except root are child nodes. 5. Siblings Nodes which belong to same Parent are called as SIBLINGS. In simple words, the nodes with the same parent are called Sibling nodes. 6. Leaf In a tree data structure, the node which does not have a child is called as LEAF Node. In simple words, a leaf is a node with no child. The leaf nodes are also called as External Nodes. External node is also a node with no child. In a tree, leaf node is also called as 'Terminal' node. 7. Internal Nodes The node which has atleast one child is called as INTERNAL Node. Nodes other than leaf nodes are called as Internal Nodes. The root node is also said to be Internal Node if the tree has more than one node. Internal nodes are also called as 'Non- Terminal' nodes. 8. Degree The total number of children of a node is called as DEGREE of that Node. The highest degree of a node among all the nodes in a tree is called as 'Degree of Tree' 9. Level The root node is said to be at Level 0 and the children of root node are at Level 1 and the children of the nodes which are at Level 1 will be at Level 2 and so on... In simple words, in a tree each step from top to bottom is called as a Level and the Level count starts with '0' and incremented by one at each level (Step). 10. Height The total number of edges from leaf node to a particular node in the longest path is called as HEIGHT of that Node. In a tree, height of the root node is said to be height of the tree. In a tree, height of all leaf nodes is '0'. 11. Depth The total number of egdes from root node to a particular node is called as DEPTH of that Node. In a tree, the total number of edges from root node to a leaf node in the longest path is said to be Depth of the tree. In simple words, the highest depth of any leaf node in a tree is said to be depth of that tree. In a tree, depth of the root node is '0'. 12. Path The sequence of Nodes and Edges from one node to another node is called as PATH between that two Nodes. Length of a Path is total number of nodes in that path. In below example the path A - B - E - J has length 4. 13. Sub Tree Each child from a node forms a subtree recursively. Every child node will form a subtree on its parent node. Properties of Trees:
• There is only one path between each pair of
vertices of a tree. • If a graph G there is one and only one path between each pair of vertices G is a tree. • A tree T with n vertices has n-1 edges. • A graph is a tree if and only if it a minimal connected. Distance of a Tree • The distance between two nodes is the minimum number of edges to be traversed to reach one node from another. centers in tree The center of a tree is a vertex with minimal eccentricity. Examples Example Rooted Trees: A rooted tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root. • If a directed tree has exactly one node or vertex called root whose incoming degrees is 0 and all other vertices have incoming degree one, then the tree is called rooted tree. • Note: 1. A tree with no nodes is a rooted tree (the empty tree) 2. A single node with no children is a rooted tree. Binary Tree Variants In a normal tree, every node can have any number of children. A binary tree is a special type of tree data structure in which every node can have a maximum of 2 children. One is known as a left child and the other is known as right child.
In a binary tree, every node can have either 0 children or 1
child or 2 children but not more than 2 children. Binary Tree Variants There are different types of binary trees and they are... 1. Strictly Binary Tree In a binary tree, every node can have a maximum of two children. But in strictly binary tree, every node should have exactly two children or none. That means every internal node must have exactly two children. A binary tree in which every node has either two or zero number of children is called Strictly Binary Tree Strictly Binary Tree/Full Binary Tree
Valid Invalid 27 2.A full binary tree • A full binary tree (sometimes proper binary tree or 2- tree) is a tree in which every node other than the leaves has two children. • The number of nodes, n, in a full binary tree is atleast n = 2h – 1, and atmost n = 2h+1 – 1, where h is the height of the tree. • The number of leaf nodes l, in a full binary tree is number, L of internal nodes + 1, i.e, l = L+1. Perfect binary tree: • Perfect binary tree: It is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level. • A perfect binary tree with l leaves has n = 2l-1 nodes. • In perfect full binary tree, l = 2h and n = 2h+1 - 1 where, n is number of nodes, h is height of tree and l is number of leaf nodes Perfect binary tree
Valid Invalid 3. Complete Binary Tree •In complete binary tree all the nodes must have exactly two children and at every level of complete binary tree there must be 2level number of nodes. It is also called as Perfect Binary Tree • For example at level 2 there must be 22 = 4 nodes and at level 3 there must be 23 = 8 nodes. •A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible 3. Complete Binary Tree
Valid Invalid 4. Extended Binary Tree A binary tree can be converted into Full Binary tree by adding dummy nodes to existing nodes wherever required. The full binary tree obtained by adding dummy nodes to a binary tree is called as Extended Binary Tree. 5. Balanced Binary Tree Balanced Binary Tree is a Binary tree in which height of the left and the right sub-trees of every node may differ by at most 1.
Valid BT Invalid BT 34 5. Degenerate(or Pathological) Binary Tree
Degenerate Binary Tree is a Binary Tree where every parent node
has only one child node.
Valid Invalid 35 Binary Tree Representations • A binary tree data structure is represented using two methods. Those methods are as follows... 1. Array Representation 2. Linked List Representation . Array Representation of Binary • we use one- Tree dimensional array (1-D Array) to represent a binary tree. To represent a binary tree of depth 'n' using array representation, we need one dimensional array with a maximum size of 2n+1 + 1. 2. Linked List Representation of Binary Tree • We use a double linked list to represent a binary tree. • In a double linked list, every node consists of three fields. First field for storing left child address, second for storing actual data and third for storing right child address. • In this linked list representation, a node has the following structure... • 2. Linked List Representation of Binary Tree Trees • A Tree is a special type of connected graph in which there are no circuits. • Every tree is a bipartite graph. • So, chromatic number of a tree with any number of vertices = 2. Tree A tree is a connected undirected graph that does not contain a simple circuit. Forest • If each component of a graph G is a tree, G is called a forest. Graph Traversal - DFS
• Graph traversal is a technique used for a searching vertex in a graph.
• The graph traversal is also used to decide the order of vertices is visited in the search process. • A graph traversal finds the edges to be used in the search process without creating loops. • That means using graph traversal we visit all the vertices of the graph without getting into looping path.
There are two graph traversal techniques and they are as
follows... 1. DFS (Depth First Search) 2. BFS (Breadth First Search) DFS (Depth First Search) • Traversal means visiting all the nodes of a graph. Depth first traversal or Depth first Search is a recursive algorithm for searching all the vertices of a graph • DFS traversal of a graph produces a spanning tree as final result. • Spanning Tree is a graph without loops. • We use Stack data structure with maximum size of total number of vertices in the graph to implement DFS traversal.
We use the following steps to implement DFS traversal...
• Step 1 - Define a Stack of size total number of vertices in the graph. • Step 2 - Select any vertex as starting point for traversal. Visit that vertex and push it on to the Stack. • Step 3 - Visit any one of the non-visited adjacent vertices of a vertex which is at the top of stack and push it on to the stack. • Step 4 - Repeat step 3 until there is no new vertex to be visited from the vertex which is at the top of the stack. • Step 5 - When there is no new vertex to visit then use back tracking and pop one vertex from the stack. • Step 6 - Repeat steps 3, 4 and 5 until stack becomes Empty. • Step 7 - When stack becomes Empty, then produce final spanning tree by removing unused edges from the graph DFS (Depth First Search) Cont.. Cont.. Cont.. Cont.. Cont.. Cont.. Cont.. Examples for DFS and BFS Examples Examples BFS (Breadth First Search) • BFS traversal of a graph produces a spanning tree as final result. • Spanning Tree is a graph without loops. • We use Queue data structure with maximum size of total number of vertices in the graph to implement BFS traversal.
We use the following steps to implement BFS traversal...
• Step 1 - Define a Queue of size total number of vertices in the graph. • Step 2 - Select any vertex as starting point for traversal. Visit that vertex and insert it into the Queue. • Step 3 - Visit all the non-visited adjacent vertices of the vertex which is at front of the Queue and insert them into the Queue. • Step 4 - When there is no new vertex to be visited from the vertex which is at front of the Queue then delete that vertex. • Step 5 - Repeat steps 3 and 4 until queue becomes empty. • Step 6 - When queue becomes empty, then produce final spanning tree by removing unused edges from the graph BFS (Breadth First Search) Cont.. cont.. Cont.. Cont.. Spanning Tree Spanning tree • A spanning tree is a sub-graph of an undirected connected graph, which includes all the vertices of the graph with a minimum possible number of edges. If a vertex is missed, then it is not a spanning tree. • The edges may or may not have weights assigned to them. • The total number of spanning trees with n vertices that can be created from a complete graph is equal to n(n-2). • If we have n = 4, the maximum number of possible spanning trees is equal to 44-2 = 16. Thus, 16 spanning trees can be formed from a complete graph with 4 vertices. Example
The initial graph is:
Graph
Some of the possible spanning trees that can be created from the above graph are: Minimum Spanning Tree • A minimum spanning tree is a spanning tree in which the sum of the weight of the edges is as minimum as possible.
The initial graph is:
• The possible spanning trees from the above graph are:
• The minimum spanning tree from the above spanning trees is: Applications Spanning Tree Applications • Computer Network Routing Protocol • Cluster Analysis • Civil Network Planning Minimum Spanning tree Applications • To find paths in the map • To design networks like telecommunication networks, water supply networks, and electrical grids. • The minimum spanning tree from a graph is found using the following algorithms: • Prim's Algorithm • Kruskal's Algorithm •
