ds 2.pdf

What is Tree Data Structure? Tree data structure is a hierarchical structure that is used to represent and organize data in a way that is easy to navigate and search. It is a collection of nodes that are connected by edges and has a hierarchical relationship between the nodes. The topmost node of the tree is called the root, and the nodes below it are called the child nodes. Each node can have multiple child nodes, and these child nodes can also have their own child nodes, forming a recursive structure. Why Tree is considered a non-linear data structure? The data in a tree are not stored in a sequential manner i.e., they are not stored linearly. Instead, they are arranged on multiple levels or we can say it is a hierarchical structure. For this reason, the tree is considered to be a non-linear data structure. Basic Terminologies in Tree Data Structure: Parent Node: The node which is a predecessor of a node is called the parent node of that node. {B} is the parent node of {D, E}. Child Node: The node which is the immediate successor of a node is called the child node of that node. Examples: {D, E} are the child nodes of {B}. Root Node: The topmost node of a tree or the node which does not have any parent node is called the root node. {A} is the root node of the tree. A non-empty tree must contain exactly one root node and exactly one path from the root to all other nodes of the tree. Leaf Node or External Node: The nodes which do not have any child nodes are called leaf nodes. {I, J, K, F, G, H} are the leaf nodes of the tree. Ancestor of a Node: Any predecessor nodes on the path of the root to that node are called Ancestors of that node. {A,B} are the ancestor nodes of the node {E} Sibling: Children of the same parent node are called siblings. {D,E} are called siblings. Level of a node: The count of edges on the path from the root node to that node. The root node has level 0. Types of tree Data Structure Tree data structure can be classiﬁ ed into three types based upon the number of children each node of the tree can have. The types are: Binary tree: In a binary tree, each node can have a maximum of two children linked to it. Some common types of binary trees include full binary trees, complete binary trees, balanced binary trees, and degenerate or pathological binary trees. Ternary Tree: A Ternary Tree is a tree data structure in which each node has at most three child nodes, usually distinguished as “left”, “mid” and “right”. N-ary Tree or Generic Tree: Generic trees are a collection of Types of tree Data Structure What is a Binary Tree? A binary tree is a tree data structure with a maximum of 2 children per node. We commonly refer to them as the left and right child as each element in a binary Whattree mayBinary is a Full only Tree? have two children. A full binary tree is a binary tree with either zero or two child nodes for each node. If T has a total of N nodes, the number of leaves is L = (N + 1)/2. What is a Complete Binary Tree? A complete binary tree is a special type of binary tree where all the levels of the tree are ﬁ lled completely except the lowest level nodes which are ﬁ lled from as left as possible. All leaf nodes on level n or n-1 Levels are ﬁ lled from left to right Some terminology of Complete Binary Tree: Degree of a node – Number of children of a particular parent. Example- Degree of A is 2 and Degree of C is 1. Degree of D is 0. Internal/External nodes – Leaf nodes are external nodes and non leaf nodes are internal nodes. Level – Count nodes in a path to reach a destination node. Example- Level of node D is 2 as nodes A and B form the path. Height – Number of edges to reach the destination node, Root is at height 0. Example – Height of node E is 2 as it has two edges from the root. BINARY TREES A binary tree is an important type of tree structure. It is characterized by the fact that any node can have at most two branches, i.e., there is no node with degree greater than two. For binary trees we distinguish between the subtree on the left and on the right, whereas for trees the order of the subtrees was irrelevant. Also a binary tree may have zero nodes. Deﬁ nition: A binary tree is a ﬁ nite set of nodes which is either empty or consists of a root and two disjoint binary trees called the left subtree and the right subtree we can deﬁ ne the data structure binary tree as follows: structure BTREE declare CREATE( ) btree ISMTBT(btree) boolean MAKEBT(btree, item, btree) btree LCHILD(btree) btree DATA(btree) item RCHILD(btree) btree for all p,r Ꞓ btree, d Ꞓ item let ISMTBT(CREATE) :: = true ISMTBT(MAKEBT(p, d, r)) :: = false LCHILD(MAKEBT(p, d, r)):: = p; LCHILD(CREATE):: = error DATA(MAKEBT(p, d, r)) :: = d; DATA(CREATE) :: = error RCHILD(MAKEBT(p, d, r)) :: = r; RCHILD(CREATE) :: = error Binary Tree Representations Representing Binary Tree in memory Let T be a Binary Tree. There are two ways of representing T in the memory as follow 1.Sequential Representation of Binary Tree. 2.Link Representation of Binary Tree. 1.Linked Representation of Binary Tree Consider a Binary Tree T. T will be maintained in memory by means of a linked list representation which uses three parallel arrays; INFO, LEFT, and RIGHT pointer variable ROOT as follows. In Binary Tree each node N of T will correspond to a location k such that LEFT [k] contains the location of the left child of node N. INFO [k] contains the data at the node N. RIGHT [k] contains the location of right child of node N. Representation of a node: In this representation of binary tree root will contain the location of the root R of T. If any one of the subtree is empty, then the corresponding pointer will contain the null value if the tree T itself is empty, the ROOT will contain the null value. Example Consider the binary tree T in the ﬁ gure. A schematic diagram of the linked list representation of T appears in the following ﬁ gure. Observe that each node is pictured with its three ﬁ elds, and that the empty subtree is pictured by using x for null entries. Linked Representation of the Binary Tree 2) Sequential representation of Binary Tree Let us consider that we have a tree T. let our tree T is a binary tree that us complete binary tree. Then there is an eﬃ cient way of representing T in the memory called the sequential representation or array representation of T. This representation uses only a linear array TREE as follows: The root N of T is stored in TREE. If a node occupies TREE [k] then its left child is stored in TREE [2 * k] and its right child is stored into TREE [2 * k + 1]. For Example: Consider the following Tree: Its sequential representation is as follow: Binary Trees-Traversal-More On Binary Tree Traversal Techniques Trees Tree Traversal techniques include various ways to visit all the nodes of the tree. Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways. Tree Traversal Meaning: Tree Traversal refers to the process of visiting or accessing each node of the tree exactly once in a certain order. Tree traversal algorithms help us to visit and process all the nodes of the tree. Since tree is not a linear data structure, there are multiple nodes which we can visit after visiting a certain node. Tree Traversal Techniques: Tree Traversal Techniques: A Tree Data Structure can be traversed in following ways: Depth First Search or DFS 1.Preorder Traversal 2.Inorder Traversal 3.Postorder Traversal Preorder Traversal of Binary Tree Preorder traversal is deﬁ ned as a type of tree traversal that follows the Root-Left-Right policy where: 1.The root node of the subtree is visited ﬁ rst. 2.Then the left subtree is traversed. 3.At last, the right subtree is traversed. Time Complexity: O(N) Algorithm for Preorder Traversal: procedure PREORDER (T) //T is a binary tree where each node has three ﬁ elds L CHILD,DATA,RCHILD// if T ≠0 then print (DATA(T)) call PREORDER(LCHILD(T)) call PREORDER(RCHILD(T))]] end PREORDER Inorder Traversal of Binary Tree Inorder traversal is deﬁ ned as a type of tree traversal technique which follows the Left-Root-Right pattern, such that: 1.The left subtree is traversed ﬁ rst 2.Then the root node for that subtree is traversed 3.Finally, the right subtree is traversed Time Complexity: O(N) Algorithm for Inorder Traversal procedure INORDER(T) //T is a binary tree where each node has three ﬁ elds L CHILD,DATA,RCHILD// if T ≠0 then [call INORDER(LCHILD(T)) print(DATA(T)) call(INORDER(RCHILD(T))] end INORDER Postorder Traversal of Binary Tree Postorder traversal is deﬁ ned as a type of tree traversal which follows the Left-Right-Root policy such that for each node: 1.The left subtree is traversed ﬁ rst 2.Then the right subtree is traversed 3.Finally, the root node of the subtree is traversed Time Complexity: O(N) Algorithm for Postorder Traversal procedure POSTORDER (T) //T is a binary tree where each node has three ﬁ elds LCHILD,DATA,RCHILD// if T≠ 0 then call POSTORDER(LCHILD(T)) call POSTORDER(RCHILD(T)) print (DATA(T)) end POSTORDER MORE ON BINARY TREES MORE ON BINARY TREES Using the deﬁ nition of a binary tree and the recursive version of the traversals, we can easily write other routines for working with binary trees. For instance, if we want to produce an exact copy of a given binary tree we can modify the postorder traversal algorithm only slightly to get: procedure COPY(T) //for a binary tree T, COPY returns a pointer to an exact copy of T; new nodes are gotten using the usual mechanism// Q 0 if T≠ 0 then [R COPY(LCHILD(T)) //copy left subtree// S COPY(RCHILD(T)) //copy right subtree// call GETNODE(Q) LCHILD(Q) R; RCHILD(Q) S //store in ﬁ elds of Q// DATA(Q) DATA(T)] return(Q) //copy is a function// end COPY procedure EQUAL(S,T) //This procedure has value false if the binary trees S and T are not equivalent. Otherwise, its value is true/ ans false case : S = 0 and T = 0: ans true : S ≠0 and T≠ 0: if DATA(S) = DATA(T) then [ans EQUAL(LCHILD(S),LCHILD(T)) if ans then ans EQUAL(RCHILD(S),RCHILD(T))] end return (ans) end EQUAL BINARY TREE REPRESENTATION OF TREES Tree preorder which is deﬁ ned by: (i) if F is empty then return; (ii) visit the root of the ﬁ rst tree of F; (iii) traverse the subtrees of the ﬁ rst tree in tree preorder; (iv) traverse the remaining trees of F in tree preorder. Inorder traversal of T is equivalent to visiting the nodes of F in tree inorder as deﬁ ned by: (i) if F is empty then return; (ii) traverse the subtrees of the ﬁ rst tree in tree inorder; (iii) visit the root of the ﬁ rst tree; (iv) traverse the remaining trees in tree inorder. The above deﬁ nitions for forest traversal will be referred to as preorder and BINARY TREE REPRESENTATION OF TREES The proofs that preorder and inorder on the corresponding binary tree are the same as preorder and inorder on the forest are left as exercises. There is no natural analog for postorder traversal of the corresponding binary tree of a forest. Nevertheless, we can deﬁ ne the postorder traversal of a forest as: (i) if F is empty then return; (ii) traverse the subtrees of the ﬁ rst tree of F in tree postorder; (iii) traverse the remaining trees of F in tree postorder; (iv) visit the root of the ﬁ rst tree of F. Counting Binary tree we determine the number of distinct binary trees having n nodes. We know that if n = 0 or n = 1 there is one such tree. If n = 2, then there are two distinct binary trees, and if n = 3, there are ﬁ ve 1.N=0 means tree in Null 2.N=1 means tree ,only one tree we will draw 3.N=2 means , Two trees we can draw. 4.N=3 means, Five trees we can draw If the nodes of a binary tree are numbered such that its preorder permutation is 1,2,...,n, then from our earlier discussion it follows that distinct binary trees deﬁ ne distinct inorder permutations. The number of distinct binary trees is thus equal to the number of distinct inorder permutations obtainable from binary trees having the preorder permutation 1,2,...,n. Using this concept of an inorder permutation, it is possible to show that the number of distinct permutations obtainable by passing the numbers 1 to n through a stack and deleting in all possible ways is equal to the number of distinct binary trees with n nodes (see the exercises). N=4{5,6,7,8} no of possible binary trees:

Document Details

Tags

Related

Full Transcript

Upgrade to continue