7. Tree - Data Structures using C++ by Varsha Patil

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  Study how trees are used to represent data in hierarchical manner  Define Binary Search Trees (BST), that allow both rapid retrieval by key and inorder traversal  Learn use of trees as a flexible data structure for solving a wide range of problems 2

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  Adjacent Nodes  Directed and Undirected Graph  Parallel Edges and Multigraph  Weighted Graph  Null Graph and Isolated Vertex  Manipulate Hierarchical Data 5

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 7  A graph in which every edge is directed is called as a directed graph or diagraph  A graph in which every edge is undirected is called as an undirected graph  If some of edges are directed and some are undirected in a graph, the graph is called as mixed graph

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 9  Any graph which that contains parallel edges is called a Multigraph  On the other hand, a graph which has no parallel edges is called as a simple graph

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 10  A graph in which weights are assigned to every edge is called as a weighted graph  Weights can also be assigned to vertices  A graph of area and streets of a city may be assigned weights according to its traffic density  A graph of areas and roads connecting may be assigned distance between cities to edges and area population to vertices

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 11  In a graph, a node which that is not adjacent to any other node is called an isolated node  A graph containing only isolated nodes is called a null graph  A graph in which weights are assigned to every edge is called as a weighted graph

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  In a directed graph, for any node V the number of edges which that have V as their initial node is called outdegree of the node V  In other words, the number of edges incident from node is its outdegree (outgoing degree)  and the number of edges incident to it is an indegree (incoming degree)  The sum of indegree and out degree is the total degree of a node (vertex)  In an undirected graph, the total degree or degree of a node is the number of edges incident with the node.  The isolated vertex degree is zero 13

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 14  A path which originates and ends at the same node is called a cycle (circuit)  A cycle is elementary if each node is traversed once (except origin) and is simple if every edge of cycle is traversed once

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 16 Figure 5 (a): Graph with two connected components Figure 5 (b): Graph with one connected component Figure 5: Graph with connected component

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 18  A class of graphs which that are acyclic are termed as trees  Trees are useful in describing any structure which that involves hierarchy  Familiar examples of such structures are family trees, the hierarchy of positions in organization, etc

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 19  In non-linear data structures, every data element may have more than one predecessor as well as successor  Elements do not form any particular linear sequence  A forest is a graph that contains no cycles and a connected forest is a tree Figure 6: Forest with three trees

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 20  Directed Tree : An acyclic directed graph is a directed tree  Root : A directed tree has one node called its root, with indegree 0, while for all other nodes in-degree is 1

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 21  Terminal node (Leaf node) : In a directed tree, any node which has out degree zero is a terminal node Terminal node is also called as leaf node (or external node)  Branch node (Internal node) : All other nodes whose outdegree is not zero are called as branch nodes  Level of node : The level of any node is the path length of it from the root.  The level of root of a directed tree is 0, while the level of any node is equal to its distance from the root  Distance from the root is the number of edges to be traversed to reach the root

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 22  A set of zero items is a tree, called the empty tree (or null tree)  If T1, T2, - - - -,Tn are n trees for n > 0 and R is an item, called a node, then the set T containing R and the trees T1, T2, - - - - ,Tn is a tree  Within T, R is called the root of T and T1, T2, - - - -, Tn are called subtrees A tree is defined recursively, as follows General Trees

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 23  We can use either sequential organization or linked organization for representing a tree  If we wish to use generalized linked list, then a node must have varying number of fields depending upon the number of branches  However, it is simpler to use algorithms for data in which the node size is fixed Representation of a General Tree Figure 6: Node Structure

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 24  Pseudo code Notations  For a fixed size node, we can use a node with data and pointer fields as in generalized linked list Figure 7: Node Structure in generalized linked list

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 28 Specification  A free tree is a connected, acyclic graph  It is undirected graph  It has no node designated as a root  As it is connected, any node can be reached from any other node by a unique path Free Tree Figure 10: Free Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 29  Unlike free tree, rooted tree is a directed graph in which one node is designated as root, whose incoming degree is zero  And for all other nodes incoming degree is one Rooted Tree Figure 11: Rooted Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 30  In many applications the relative order of the nodes at any particular level assumes some significance  It is easy to impose an order on the nodes at a level by referring to a particular node as the first node, to another node as the second, and so on  Such ordering can be done left to right Ordered Tree Figure 12: Ordered Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 31  A tree in which each branch node vertex has the same outdegree is called as Regular Tree  If in a directed tree, the outdegree of every node is less than or equal to m, then the tree is called as an m-ary tree  If the outdegree of every node is exactly equal to m (branch nodes) or zero (leaf nodes) then the tree is called as regular m-ary tree Regular Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 32  A Binary Tree is a special form of a tree  A tree in which each branch node vertex has the same out- de Binary tree is important and frequently used in various applications of computer science Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 33  A tree with n nodes and of depth k is complete iff its nodes correspond to the nodes which are numbered one to n in the full tree of depth k  A binary tree of height, h, is complete iff it is empty or its left subtree is complete of height h – 1 and its right subtree is completely full f height h – 2 or – its left subtree is completely full of height h-1 and its right subtree is complete of height h – 1  A binary tree is completely full if it is of height, h and has (2h+1 – 1) nodes Complete Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 34  A binary tree is a full binary tree, if it contains maximum possible number of nodes in all levels  In a full binary tree each node has two children or no child at all  Total number of nodes in full binary tree of height h is 2h+1 – 1 considering root at level 0.  It can be calculated as by adding number of nodes of each level 2 0 + 2 1 + 2 2 + ………..+ 2 h = 2 h+1 – 1 Full Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 35  A binary tree is said to be a complete binary tree, if all its level, except the last level, have maximum number of possible nodes, and all the nodes of the last level appear as far left as possible  In a complete binary tree all leaf nodes are at last and second last level and levels are filled from left to right Complete Binary Tree Figure 13: Complete Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 36  Every non-terminal node in a binary tree consists of non- empty left subtree & right subtree, then such a tree is called Strictly Binary Tree Strictly Binary Tree Figure 15: Strictly Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 37  A binary tree T consists of each node has 0 or 2 children is called extended binary tree  Node with 2 children are called internal nodes and nodes with 0 children are called external nodes  Trees can be converted into extended trees by adding a node Binary Tree(cont….)

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 38  Definition : A Binary Tree is either : an empty tree; or consists of a node, called root and two children, left and right, each of which are themselves binary trees Binary Tree(cont….) Figure 16 : Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 39 Binary Tree(cont….) 1. Declare CREATE( ) btree 2. MAKEBTREE(btree,element, btree) btree 3. ISEMPTY(btree) boolean 4. LEFTCHILD(btree) btree 5. RIGHTCHILD(btree) btree 6. DATA((btree) element for all l,r ε btree, e ε element, Let 7. DATA(MAKEBTREE(l,e,r)) = e 8. ISEMPTY(CREATE) = true 9. ISEMPTY(MAKEBTREE(l,e,r)) = false 10. LEFTCHILD(CREATE( )) = error 11. RIGHTCHILD(CREATE( )) = error 12. LEFTCHILD(MAKEBTREE(l,e,r)) = l 13. RIGHTCHILD(MAKEBTREE(l,e,r)) = r 15. end

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 40 The basic operations on a binary tree can be as listed below as follows:  Creation : Creating an empty binary tree to which 'root' points  Traversal : To Visiting all the nodes in a binary tree  Deletion : To Deleting a node from a non-empty binary tree A binary tree T consists of each node has 0 or 2 children is called extended binary tree  Insertion : To Inserting a node into an existing (may be empty) binary tree Operations on Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 41 The basic operations on a binary tree can be as listed below as follows:  Merge : To Merging two binary trees  Copy : Copying a binary tree  Compare : Comparing two binary trees  Find replica or mirror Operations on Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 42 The two main reasons are  A Binary Tree has a natural implementation in linked storage  The linked structure is more convenient for insertions and deletions Realization Of A Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 43  For any node with index i, 0 ≤ i ≤ n-1,  PARENT (i) = ë(t–1)/2û if i ¹ 0 If i = 0 then it is root which has no parent  LCH ILD (i) = 2 * i + 1 if 2i + 1 ≤ n-1 If 2i ³ n, then i has no left child  RCHILD (i) = 2i + 2 if 2i + 2 ≤ n-1 If (2i + 1) ³ n, then i has no right child Array Implementation of a Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 44  Any node can be accessed from any other node by calculating the index  Here, data are stored without any pointers to their successor or ancestor  Programming languages, where dynamic memory allocation is not possible (such as BASIC, FORTRAN), array representation is the only mean to store a tree Advantages of Array Representation of Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 45  Other than full binary trees, majority of the array entries may be empty  Other than full binary trees, majority of the array entries may be empty  a new node to it or deleting a node from it are inefficient with this representation, because these require considerable data, movement up and down the array which demand excessive Inserting amount of processing time Disadvantages of Array Representation of Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 46  Binary tree has natural implementation in linked storage. In linked organization we wish that all nodes should be allocated dynamically  Hence we need each node with data and link fields  Each node of a binary tree has both a left and a right subtree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 47  Each node will have three fields Lchild, Data, and Rchild. Pictorially this node is shown in Fig. Linked Implementation of Binary Trees Figure 17 : Node Structure in Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 49  The drawback of sequential representation are overcome in this representation  We may or may not know the tree depth in advance. Also for unbalanced tree, memory is not wasted  Insertion and deletion operations are more efficient in this representation. Advantages of Linked Representation of Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 50  In this representation, there is no direct access to any node  It has to be traversed from root to reach to a particular node  As compared to sequential representation memory needed per node is more  This is due to two link fields (left child and right child for binary trees) in node  The drawback of sequential representation are overcome in this representation Disadvantages of Linked Representation of Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 51  This operation is used to visit each node (or visit each node exactly once)  A full traversal of a tree visits nodes of a tree in a certain linear order  This linear order could be familiar and useful  For example, if the Binary Tree contains an arithmetic expression then its traversal may give us the expression in infix notation or postfix notation or prefix notation

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 53 Computing Time Complexity of Algorithm LDR : 5 – 6 + 3 * 8 / 4 LRD : 5 6 – 3 8 4 / * + DLR : + – 5 6 * 3 / 8 4 DRL : + * / 4 8 3 – 6 5 RDL : 4 / 8 * 3 + 6 – 5 RLD : 4 8 / 3 * 6 5 – +

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 54  In this traversal, the root is visited first then left subtree in preorder and then right subtree in preorder  Tree characteristics lead to naturally implement tree traversals recursively  It can be defined in the following steps. Preorder (DLR) Algorithm:  Visit the root node  Traverse the left subtree of node in preorder and then  Traverse the right subtree of node in preorder Pre-order Traversal

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 55 Pre-order Traversal A preorder traversal of the tree in Fig. 2 visits node in a sequence: A B D E G C F For an Expression Tree, preorder traversal yields a prefix expression Figure 20: Binary Tree Figure 21: Expression Tree and its preorder traversal

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 56 In-order Traversal In this traversal, the left subtree is visited first in inorder, then root and then the right subtree in inorder

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 57 In-order Traversal Inorder ((LDR)) Algorithm (a) Traverse the left subtree of root node in inorder (b) Visit the root node (c) Traverse the right subtree of root node in inorder

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 59 Post-order Traversal In this traversal, the left subtree is visited first in postorder, then the right subtree in postorder and then the root

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 60 Post-order Traversal Algorithm (i) Traverse the root's left child (subtree) of root node in postorder (ii) Traverse the root's right child (subtree) of root node in postorder (iii) Visit the root node

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 61  For the expression tree in Fig. 21 the postorder traversal yields a postfix expression as : = A B * D +  The postorder traversal says that traverse left and continue again  When you cannot continue, move right and begin again or move back, until you can move right and visit the node Pre-order Traversal

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 63  Sometimes we need to construct a binary tree if its traversals are known  From a single traversal a unique binary tree cannot be constructed  However, if two traversals are known then the corresponding tree can be drawn uniquely Formation of Binary Tree from its Traversals

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 64  If the preorder traversal is given, then the first node is the root node  If the preorder traversal is given, then the first node is the root node  Once the root node is identified, all the nodes in all left subtrees and right subtrees of the root node can be identified  Same techniques can be applied repeatedly to form subtrees  We can conclude that, for the binary tree construction and traversals are essential out of which one should be inorder traversal and another preorder or postorder  Alternatively given preorder and postorder traversals, binary tree cannot be obtained uniquely Formation of Binary Tree from its Traversals

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 65  As defined earlier, we know that traversal of tree means visiting through the nodes of a tree  A traversal in which the node is visited before its children are visited is called a breadth first traversal; a walk where the children are visited prior to the parent is called a depth first traversal Breadth and Depth First Traversals

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 66  We have already seen a few ways to traverse the elements of a tree  A traversal in which children are visited (operated on) before the parent is called Depth First Traversal Depth-first Traversal

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 67  For Example, given the following tree  A Preorder Traversal would visit the elements in the order  j, f, a, d, h, k, h  This type of traversal is called a Depth-first Traversal  Because as it tries to go deeper in the tree before exploring siblings Depth-first Traversal

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 68  For Depth-first is not the only way to go through the elements of a tree  Another way is to go through them level-by-level  For example, each element exists at a certain level (or depth) in the tree Breadth-first Traversal

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 69  This operation computes the height of linked binary tree. Height of tree is maximum path length in tree  We can get path length by traversing tree depth wise  Let us consider that an empty tree's height is 0 and tree with only one node has height Computing Height of Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 70  This operation finds mirror of the tree that will interchange all left and right subtrees in linked binary tree Getting mirror or replica or Tree Interchange of Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 71  TreeCopy operation will make a copy of linked binary tree  The function should allocate necessary nodes and copy respective contents in it. as right child Copying Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 72  This operation checks whether two binary trees are equal  Two trees are said to be equal if they have the same topology and all corresponding nodes are equal  Same topology refers to fact that each branch in first tree corresponds to a branch in second tree in the same order and vice versa Equality Test

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 73 Binary trees are trees where the maximum degree of any node is two  Any general tree can be represented as a binary tree using the following algorithm  ALL nodes general tree will be nodes of binary tree.  The root T of general tree is the root of binary tree.  To obtain a binary tree, we use a relationship between the nodes that can be characterized by two characteristics  i) One relationship is the leftmost-child Conversion Of A General Tree To Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 74 A Binary Search Tree (BST) is a binary tree that is either empty or in which every node contains a key and satisfies the conditions:  The key in the left child of a node, if it exists, is less than the key in its parent node  The key in the right child of a node, if it exists, is greater than the key in its parent node  The left and right subtrees of node are again binary search trees  The definition ensures that no two entries in a binary search tree can have equal keys Binary Search Tree (BST)

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 75 Following are the operations commonly performed on binary search tree  Searching a key  Inserting a key  Deleting a key  Traversing a tree Equality Test

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 76 Thornton has suggested to replace all the null links by pointers, called Threads  A tree with thread is called as Threaded Binary Tree (TBT)  Both threads and tree pointers are pointers to nodes in the tree  The difference is that threads are not structural pointers of the tree  They can be removed and the tree does not change  Tree pointers are the pointers that join and hold the tree together Threaded Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 77  Threads utilize the NULL pointers waste space to improve processing efficiency  One such application is to use these NULL pointers to make traversals faster  In a left NULL pointer, we store a pointer to the node's inorder successor  This allows us to traverse the tree both left to right and right to left without recursion Threaded Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 79  Threaded binary tree has some advantages over non-threaded binary tree.  The traversal for threaded binary tree is straight forward. No recursion or stack is needed  Once we locate the leftmost node, we loop, following the thread to next node  When we find null thread, the traversal is complete Pros and Cons of Threaded Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 80  In case of non threaded binary tree, this task is time consuming and difficult  Also stack is needed for the same Threaded binary tree has some advantages over non-threaded binary tree.  Threads are usually more to upward whereas links are downward  Thus in a threaded tree we can traverse in either direction and nodes are infact circularity linked  Hence, any node can be reached from any other node  Insertions into and deletion from a threaded tree are although time consuming as the link and thread are to be man Pros and Cons of Threaded Binary Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 82  Binary tree storing or representing an arithmetic expression is called as expression tree  The leaves of an expression tree are operands  Operands could be variables or constants  Branch nodes (internal nodes) represent the operators  Binary tree is the most suitable one for arithmetic expression as it contains either binary or unary operators Expression

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 83  The expression tree for expression E, is shown in Fig.  Let E : ((A * B)+ (C – D)) / (C – E) Expression Figure 25: Expression Tree for E= ((A * B) + (C – D)) / (C – E)

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 84  Decision Tree is a classifier in the form of a tree structure , where each node is either  A Leaf Node - indicates the value of the target attribute (class) of examples, or  A Decision Node - specifies some test to be carried out on a single attribute-value, with one branch and sub-tree for each possible outcome of the test  A Decision Tree can be used to classify an example by starting at the root of the tree and moving through it until a leaf node, which provides the classification of the instance  Decision Tree induction is a typical inductive approach to learn knowledge on classification DECISION TREE

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 86  Decision Trees are less appropriate for estimation tasks where the goal is to predict the value of a continuous attribute  Decision Trees are prone to errors in classification problems with many class and relatively small number of training examples  Decision Tree can be computationally expensive to train  The process of growing a Decision Tree is computationally expensive  Weaknesses Of Decision Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 87  At each node, each candidate splitting field must be sorted before its best split can be found. In some algorithms, combinations of fields are used and a search must be made for optimal combining weights  Decision Trees are less appropriate for estimation tasks where the goal is to predict the value of a continuous attribute  Decision trees do not treat well non-rectangular regions. Most decision- tree algorithms only examine a single field at a time  Decision Trees are prone to errors in classification problems with many class and relatively small number of training examples Weaknesses Of Decision Tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 88 One of the most important applications of binary tree is in Communication  Huffman’s Algorithm : HUFFMAN’S CODING 1. Organize the data into a row as ascending order frequency weights. Each character is leaf node of a tree. 2. Find two nodes with the smallest combined weights and join them to form third node 3. This will form a new two level tree 4. The weight of new third node is addition of two nodes. 5. Repeat step 2 till all the nodes on every level are combined to form a single tree.

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 89 One of the most important applications of binary tree is in Communication  One of the most important applications of binary tree  Another Interesting application of trees is in the playing of games such as tic-tac-toe, chess, nim, checkers, go, etc  As an example let us consider the game of tic-tac-toe Game Trees Figure 27 : An example game tree

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 90  A binary tree is a special form of a tree. Binary tree is important and frequently used in various application of computer science. A binary tree has degree two, each node has at most two children. This makes the implementation of tree easier. Implementation of binary tree should represent hierarchical relationship between parent node and its left and right children.  Tree, a non-linear data structure, is a mean to maintain and manipulate data in many applications as listed above. Where ever the hierarchical relationship among data is to be preserved, tree is used.  A binary tree is a special form of a tree. Binary tree is important and frequently used in various application of computer science. A binary tree has degree two, each node has at most two children. This makes the implementation of tree easier. Implementation of binary tree should represent hierarchical relationship between parent node and its left and right children. Summary

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 91  Binary tree has natural implementation in linked storage. In linked organization we wish that all nodes should be allocated dynamically. Hence we need each node with data and link fields. Each node of a binary tree has both a left and a right subtree. Each node will have three fields Lchild, Data and Rchild.  The operations on binary tree include- insert node, delete node and traverse tree. Traversal is one of the key operations. Traversal means visiting every node of a binary tree. There are various traversal methods. For a systematic traversal, it is better to visit each node (starting from root) and its both subtrees in same way. Summary

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 92  Let L represent left subtree, R represent right subtree and D be node data, three traversals are fundamental: LDR, LRD and DLR. These are called as inorder, postorder and preorder traversals because there is a natural correspondence between these traversals and producing the infix, postfix and preorder forms of an arithmetic expressions respectively. Also a traversal in which the node is visited before its children are visited is called a breadth first traversal; a walk where the children are visited prior to the parent is called a depth first traversal.  The binary search tree is a binary tree with the property that the value in a node is greater than any value in a node's left subtree and less than any value in the node's right subtree. This property guarantees fast search time provided the tree is relatively balanced.·  The key applications of tree include: expression tree, gaming, Huffman coding and decision tree.

7. Tree - Data Structures using C++ by Varsha Patil

In this document

More Related Content

What's hot

Viewers also liked

Similar to 7. Tree - Data Structures using C++ by Varsha Patil

Recently uploaded

7. Tree - Data Structures using C++ by Varsha Patil