Lecture Data Structures: Lesson 28 provide students with knowledge about calling nextInorder with root; fix with dummy node; inorder traversal; trace or nextInorder; complete binary tree; different definition of complete binary tree than an earlier definition we had; . | Data Structures Lecture 28 Sohail Aslam 1 Calling nextInorder with root TreeNode nextInorder TreeNode p if p- gt RTH thread return p- gt R else p p- gt R while p- gt LTH child 14 p p p- gt L return p 4 15 3 9 18 7 16 20 5 2 Calling nextInorder with root TreeNode nextInorder TreeNode p if p- gt RTH thread return p- gt R else p p- gt R while p- gt LTH child p p- gt L return p 14 4 15 p 3 9 18 7 16 20 5 3 Fix with Dummy Node dummy 14 4 15 3 9 18 7 16 20 5 4 Inorder traversal void fastInorder TreeNode p while p nexInorder p dummy cout getInfo Start the inorder traversal by calling fastInorder dummy . 5 Trace or nextInorder p dummy 14 4 15 3 9 18 7 16 20 5 6 Trace or nextInorder dummy p 14 4 15 3 9 18 7 16 20 5 7 Trace or nextInorder dummy p 14 4 15 3 9 18 7 16 20 5 8 Trace or nextInorder dummy 14 p 4 15 3 9 18 7 16 20 5 9 Trace or nextInorder dummy 14 4 15 p 3 9 18 7 16 20 5 10 Trace or nextInorder dummy 14 4 p 15 3 9 18 7 16 20 5 11 Trace or nextInorder dummy 14 4 15 3 9 18 7 16 20 p 5 12 Trace or nextInorder dummy 14 4 15 3 9 18 7 p 16 20 5 And so on. 13 Complete Binary Tree 14 Complete Binary Tree A complete binary tree is a tree that is completely filled with the possible exception of the bottom level. The bottom level is filled from left to right. Different definition of complete binary tree than an earlier definition we had. The earlier definition could be called a perfect binary tree. 15 Complete Binary Tree A B C D E F G H I J 16 Complete Binary Tree Recall that such a tree of height h has between 2h to 2h 1 1 nodes. The height of such a tree is thus log2N where N is the number of nodes in the tree. Because the tree is so regular it can be stored in an array no pointers are necessary. 17 Complete Binary Tree A B C D E F G H I J A B C D E F G H I J 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 18 Complete Binary Tree For any array element at position i the left child is at 2i the right child is at 2i 1 and the parent is at i 2 . A B C D E F G H I J 0 1 2 3 4 5 6 7 8 9 10
