binary tree

binary tree

• 1.
  BINARY TREE
• 2.
  BINARY TREE •A binary tree is a special form of tree in which a node can have atmost two children • A node in a binary tree may not necessarily have the maximum of two children i.e either 1,2 or 0 child. • A tree which does not contain any node is called empty binary node.
• 3.
  Binary Tree Fullbinary tree Complete binary tree
• 4.
  Full Binary Tree A binary tree is said to be full binary tree if each node has exactly zero or two children. Also known as proper binary tree
• 5.
  Complete Binary Tree A complete binary tree is either a full binary tree or one in which every level is fully occupied except possibly for the bottomost level where all the nodes must be as far left as possible.
• 6.
  PROPERTIES OF BINARYTREE • 1.The maximum number of nodes in a binary tree on a given level (say L) is 2L a,where L>=0 . • 2.The maximum number of nodes in an binary tree with height h is 2h+1-1 • 3.the minimum number of nodes possible in a binary tree of height h is h+1
• 7.
  • 4.if nis the number of nodes and e is the number of edges in an non-empty binary tree then n=e+1. • 5.if n0 is the number of leaf nodes (no child) and n2 is the number of nodes with two children in a non-empty binary tree then n0= n2+1 • 6.for a complete binary tree T with n nodes ,the height is floor[log2(n+1) -1]
• 8.
  Binary Tree TraversalTechniques • Three recursive techniques for binary tree traversal • In each technique, the left subtree is traversed recursively, the right subtree is traversed recursively, and the root is visited • What distinguishes the techniques from one another is the order of those 3 tasks 8
• 9.
  Preoder, Inorder, Postorder • In Preorder, the root is visited before (pre) the subtrees traversals • In Inorder, the root is visited in-between left and right subtree traversal • In Preorder, the root is visited after (pre) the subtrees traversals 9 Preorder Traversal: 1. Visit the root 2. Traverse left subtree 3. Traverse right subtree Inorder Traversal: 1. Traverse left subtree 2. Visit the root 3. Traverse right subtree Postorder Traversal: 1. Traverse left subtree 2. Traverse right subtree 3. Visit the root
• 10.
  Illustrations for Traversals 1 • Assume: visiting a node is printing its label 3 7 • Preorder: 5 8 9 1 3 5 4 6 7 8 9 10 11 12 10 4 6 • Inorder: 11 12 4 5 6 3 1 8 7 9 11 10 12 • Postorder: 4 6 5 3 8 11 12 10 8 9 7 1 10
• 11.
  Illustrations for Traversals(Contd.) • Assume: visiting a node 15 8 20 is printing its data • Preorder: 15 8 2 6 3 7 2 11 27 11 10 12 14 20 27 22 30 6 10 12 22 30 • Inorder: 3 6 7 2 8 10 11 3 7 14 12 14 15 20 22 27 30 • Postorder: 3 7 6 2 10 14 12 11 8 22 30 27 20 15 11
• 12.
  Tree Traversals Pre-Order(NLR) 1, 3, 5, 9, 6, 8
• 13.
  Tree Traversals In-Order(LNR) 5, 3, 9, 1, 8, 6
• 14.
  Tree Traversals Post-Order(LRN) 5, 9, 3, 8, 6, 1
• 15.
  PRE-ORDER USING STACK • PREORD(INFO,LEFT,RIGHT,ROOT): A binary tree T is in memory .The algorithm does a preorder traversal of T, applying an operation PROCESS to each of its node. An array STACK is used to temporarily hold the addresses of nodes.
• 16.
  • 1.[Initiaaly pushNULL onto STACK and initialize PTR] Set TOP1.STACK[1]NULL and PTRROOT 2.Repeat steps 3 to 5 while PTR!=NULL 3.Apply PROCESS to INFO[PTR] 4.[Right Child?] If RIGHT[PTR]!=NULL [Push on STACK] TOPTOP+1 STACK[TOP]RIGHT[PTR] [End of if structure]
• 17.
  • 5.[Left Child?] If LEFT[PTR]!=NULL, Set PTRLEFT[PTR] Else [pop from stack] PTRSTACK[TOP] TOPTOP-1 [End of if strucutre] [End of step 2 loop] 6.Exit
• 18.
  IN-ORDER • INORDER(INFO,LEFT,RIGHT,ROOT):Abinary tree is in memory. This algorithm does an inorder traversal .applying PROCESS to each of its node.An array STACK is used to temporarily hold the addresses of node.
• 19.
  1.[Push NULL ontoSTACK and initialize PTR] TOP1,STACK[1]NULL and PTRROOT 2.Repeat while PTR!=NULL [Push left most path onto stack] a)TOPTOP+1 and STACK[TOP]PTR [Saves nodes] b)PTRLEFT[PTR] [updates PTR] [End of loop] 3.PTRSTACK[TOP] TOPTOP-1 [pops node from STACK]
• 20.
  4.Repeat steps 5to 7 while PTR!=NULL [Backtracking] 5.Apply PROCESS to INFO[PTR] 6.[Right child?] If RIGHT[PTR]!=NULL a)PTRRIGHT[PTR] b)GOTO step 2 7.PTRSTACK[TOP] TOP=TOP-1 [Pops node] [end of step 4 loop] 8.Exit
• 21.
  POSTORDER • POSTORD(INFO,LEFT,RIGHT,ROOT):Abinary tree T is in memory.This algorithm does a postorder traversal of T,applying an operation PROCESS to each of its node.An array STACK is used to temporarily hold the address of nodes
• 22.
  1.[push NULL ontoSTACK and initialize PTR] Set TOP1,STACK[1]NULL,PTRROOT 2.[Push left-most path onto STACK] Repeat steps 3 to 5 while(PTR!=NULL) 3.TOPTOP+1 STACK[TOP]PTR [ Pushes PTR on STACK] 4.if RIGHT[PTR]!=NULL, then [Push on STACK] TOPTOP+1 and STACK[TOP]=-RIGHT[PTR]. [end of If strucutre]
• 23.
  Set PTRLEFT[PTR] [Updatespointer PTR] [End of Step 2 loop] 6.Set PTRSTACK[TOP] and TOPTOP-1 [Pops node from STACK] 7.Repeat while PTR>0. A)Apply PROCESS to INFO[PTR] B)Set PTRSTACK[TOP] and TOPTOP-1 [pops node from STACK] 8.If PTR<0 ,then: a)PTR-PTR b)Goto step 2. [End of If structure] 9.EXIT