Slide 1: Data and File Structures A Paper of MCA / MSc. Computer Science – Presentation by, Varsha Pathak, IMR Jalgaon
Slide 2: Unit II : Non linear data structures Coverage: General Trees, Binary Trees, BST, Heap Applications of trees Operations on binary trees Graphs Representations Graph traversals Applications of graphs Spanning trees
Slide 3: General Trees : This is a very important type of data objects. Many times we need to represent data in the form of charts where the items of information are to be related by hierarchies and branches. Such organized form of hierarchical information resembles the tree structures uses to represent family history charts also known as genealogical charts. Dusty Honey Bear Brandy Brunhilde Terry Coyote Nugget Gill Tansey Tweed Zoe Crocus Primrose Nous Belle
Slide 4: Definition: A tree is a finite set of one or more nodes such that There is a specially designated node called the root. The remaining nodes are partitioned into n>=0 disjoint sets T 1 , …..,Tn are called the subtrees of the root. A B C D E F G J K L H I M Level 1 2 3 4
Slide 5: Terminology : A node : item with information and branches to other nodes. each node has one parent and maximum m number child nodes. Degree of a node is : the number of subtrees of a node . Degree/Order of tree is : The maximum degree of all nodes of the tree i.e. m. Leaf nodes are : the nodes with degree zero . Also called as terminal nodes. e.g. K,L,F,G,I,J are the leaf node in above fig Root of the tree : is the node at top most level which has no parent node and maximum m number of children . e.g. Item A is root . Ancestors : of a node are app nodes along the path from root to that node. Level : Considering root at level 1, its children at level 2 and so on. “If a node is at level l its children are at level l+1”. Height/depth of tree : is the m aximum level number of the tree .
Slide 6: Representation of Trees 1) List representation (A(B(E(K,L),F),C(G),D(H(M),I,J))) A B F C G 0 D E K L 0 H I J 0 M 0 0
Slide 7: Left Child-Right Sibling Representation Data left child right sibling Left child-right sibling node structure A B E K C D F G H M L J I Left:first child Right: next sibling
Slide 8: Binary Trees : A ny general tree structure can be represented using two links 1 Left : as the link to first child node of the current node 2 Right : as the link to the next sibling of the current node. Thus binary tree structure is applicable to represent all tree structures. The binary tree has all its nodes with at most two disjoint subtrees. Definition : A binary tree is a finite set nodes that either is empty or Consist of a root and two disjoint binary trees called the left subtree and the right subtree. Special kinds of binary trees : Complete binary tree Skewed binary tree – Left Skewed -- Right Skewed
Slide 9: Full Binary Tree A C D E F G H I J K L O N M B Root Maximum Number of nodes In a binary tree of depth 4 k = Σ 2 i-1 = 2 k -1 i=1 = 1+2+4+8 = 15 Max = ? If h = 5. Def n : A full Binary tree of depth k is a binary tree of depth k having 2 k -1 nodes where k >=0. A binary tree with n nodes and depth k is complete iff its Nodes correspond to the nodes numbered from 1 to n in the full binary Tree.
Slide 10: Binary tree representations : Two ways of representation 1> Array Representation 2> Linked Representation Array Representation : The binary tree is stored in the array form in such a manner that the “parent-child” relationship is maintained. 1> parent(i) is at [i/2] if i 1. If i=1, i is at the root and has no parent. 2> LeftChild(i) and RightChild(i) is at 2i and 2i+1 respectively. It is an efficient way of representing a Complete Binary Tree. If binary tree is not a complete on the contrary skewed significant amount of memory is wasted. A C G O Root Right Skewed Binary Tree A D H B Root Left Skewed Binary Tree
Slide 11: Linked Representation : If binary tree has few nodes comparing its full length then for such application array is not the proper solution. We can use linked representation for a more dynamic representation of binary tree. Linked representation allow to extend the height as required by the application. It also allows to allocate memory according to the number of nodes required to store the information. Following is the declaration class Tree; class TreeNode { friend class Tree; private: TreeNode *LeftChild; char data[4]; TreeNode *RightChild; }; class tree { public : // tree operations Private : TreeNode *root; }
Slide 12: Applications of binary tree: 1] Arithmetic Expression tree N odes represent tokens either operand or operator. A ll operands as leaf nodes A ll operators as parent of its left and right expression. Here expression represent the left and right subtrees respectively. O perators are stored an such manner that Operators with higher priority hold higher level node. The root node holds the operator with lowest priority. expr1 = (a+b) * (c-d) expr2=a+b*c-d/2 Root * + - a b c d - + / a * 2 d b c root
Slide 13: 2 ]Binary Search Tree : This is another application. The binary tree is further ruled by the additional property that makes it a search tree. All elements in bst are stored in such a manner that L eft subtree holds values less than root element value. R ight subtree holds values greater than root element. A nd left and right subtrees are recursively Binary Search Tree 70 92 32 60 78 97 20 45 55 68 75 99 94 80 50 bst
Slide 14: Binary tree traversal and tree iterators Traversing – “Visiting each and every tree node exactly once”. Most of the tree operations are based on the traversing method used. A full traversal of the tree produces a linear order of the nodes. Hence it is possible to access the tree and process the information built in it in a specific order. There are three operations on which the traversals are based. L - Moving to left. V - Visiting the current node. R- Moving to right. Using these notations there are six possible combinations and three Traversals . Inorder – LVR, RVL Postorder- LRV, RLV Preorder- VLR, VRL
Slide 15: Inorder Traversal- LVR, RLV LVR() 1 Move left and traverse the left subtree by “Inorder”. 2 Visit the current /root and retrieve, process the element. 3 Move to right and traverse the right subtree by “Inorder”. Applications- By traversing Expression tree in Inorder produces Infix expression. Traversing the Binary search tree ,produces sorted order of the elements stored in. void Tree :: inorder( ) { inorder(root); } void Tree::inorder( TreeNode *CurrentNode) { if (CurrentNode) { inorder(CurrentNode -> LeftChild); cout << CurrentNode -> data; inorder(CurrentNode -> RightChild); } }
Slide 16: void Tree :: postorder( ) { postorder(root); } void Tree::postorder( TreeNode *CurrentNode) { if (CurrentNode) { postorder(CurrentNode -> LeftChild); postorder(CurrentNode -> RightChild); cout << CurrentNode -> data; } }
Slide 17: void Tree :: preorder( ) { preorder(root); } void Tree::preorder( TreeNode *CurrentNode) { if (CurrentNode) { cout << CurrentNode -> data; preorder(CurrentNode -> LeftChild); preorder(CurrentNode -> RightChild); } }
Heap tree : Heap tree Heap tree is a complete binary tree with the property such that every parent node has at least equal value of that of two of its child values. 90 70 75 40 35 55 57 20 17 30 19 heap This is a Max heap tree with largest element at root. All parents hold greater value than their two child values
Algorithm- Heap Adjust: Algorithm- Heap Adjust Algorithm HeapAdjust (List, N) 1. [Start from the first parent element from bottom] Parent N/2 2. [ Adjust all parent elements from bottom up] Repeat step 3thru 4while Parent >=0 3. [ Check if any child element is heavier than parent and repeat] J=Parent Repeat while J<=N/2 X List [J] I J*2 If List[I] < List[I+1] Then I I+1 If X<List[I] Then List[J] List[ I] J I Else break 4. [ Store the element] List[I] X 5. [ Shift to previous parent] Parent=Parent-1 6. [Finished] Return(List)
Algorithm – Heap Adjust: Algorithm – Heap Adjust 9 45 25 17 80 30 55 37 20 38 40 35 70 90 57 9 45 25 37 80 70 90 40 35 38 30 55 57 20 17 Tree at the beginning With no heap property. Parent at 7 i.e.55 < 90, where 90>57 , thus exchange 90 and 55 Tree after heap adjust Of 3 rd Level Parent N = 15 Parent = 15/2 =7 Then 6, 5,4 parent elements after heap adjust
Heap Sort Algorithm: Heap Sort Algorithm Algorithm HeapSort ( Tree, N) adjusts the tree to heap then Sorts the elements using heap property. 1. [Adjust heap applying function] HeapAdjust (Tree, N) 2. [ Set last position of tree] Last N 3. [ Exchange root with last element] Swap(Tree[Last], Tree[1]) 4. [Adjust root to heap] J=1 X List[J] Repeat while J>=Last/2 I J*2 If List[I] < List[I+1] Then I J*2 If List[I] < List[I+1] Then I I+1 If X<List[I] Then List[J] List[ I] J I Else break 5. [ Store the element] List[ i ] X 6. [ Decrement size of tree] Last = Last-1 7. [ Loop till the all in order] Repeat step 3 thru 6 while Last > 1 8. [Finish] Return (Tree)
Heap Adjust : Heap Adjust 45 25 17 50 9 40 35 70 90 57 80 70 37 45 35 57 17 20 38 90 40 9 30 55 25 The binary tree using list (array) Apply heap adjust to construct heap tree representation Now as in following list every ith element has greater or equal value than its two child element at position 2*i and 2*i+1 positions. eg. 70 at 3 rd position its child elements 35 and 57 are at 6 th and 7 th position respectively and 70 is greater than 35 & 57. So root element is the largest element of the list i.e. 90 30 55 37 20 38 The Heap tree after heap adjust
Heap tree logical view: Heap tree logical view 90 80 70 37 45 35 57 40 9 38 30 55 25 20 17 25 80 70 37 45 35 57 40 9 38 30 55 90 20 17 Heap tree has the largest value at root. Sorting involves- 1. exchange of root value with last value. 2. Decrement size by 1. 3. Adjust root to heap from remaining size 4. Repeat step 1 ..3 till size of Heap tree is reduced to 1. Fig to left is heap tree root exchange with last element as in figure below.
Repeat step1,2 then....3: Repeat step1,2 then.. ..3 80 70 37 45 35 57 17 20 38 25 40 9 30 55 90 45 70 37 40 35 57 17 20 38 80 25 9 30 55 90 45 70 37 40 35 57 17 20 38 55 25 9 30 80 90 45 57 37 40 35 55 17 20 38 70 25 9 30 80 90 45 57 37 40 35 55 17 20 38 30 25 9 70 80 90 45 55 37 40 35 30 17 20 38 57 25 9 70 80 90
Heap Sort Cont…..: Heap Sort Cont….. 45 55 37 40 35 30 17 20 38 9 25 57 70 80 90 45 35 37 40 9 30 17 20 38 55 25 57 70 80 90 45 35 37 40 9 30 17 20 38 25 55 57 70 80 90 40 35 37 25 9 30 17 20 38 45 55 57 70 80 90 40 35 37 25 9 30 17 20 45 38 55 57 70 80 90 38 35 37 25 9 30 17 20 45 40 55 57 70 80 90
After remaining iterations: After remaining iterations 17 20 25 30 35 37 38 40 45 9 55 57 70 80 90 9 17 20 25 30 35 37 55 57 45 70 80 90 40 38 List view of heap tree After complete sorting Binary tree (logical view) of heap tree After complete sorting
So that’s not end of Trees more to learn and more to understand ………….Thanks V. M. Pathak: So that’s not end of Trees more to learn and more to understand ………….Thanks V. M. Pathak