Tree TraversalTree AnatomyTree TraversalsBreadth First TraversalsQueue and stackBreadth first tree traversal with a queueDepth-First TraversalsPre-order Traversal: VLRPre-order tree traversal with a stackPreorder TraversalExampleOrdering of the preorder traversal is the same a the Universal Address System with lexicographic ordering.In-order Traversal: LVRInorder TraversalSlide 15Slide 16Post-order Traversal: LRVPostorder TraversalSlide 19Representing Arithmetic ExpressionsSlide 21Infix NotationPrefix Notation (Polish Notation)Evaluating Prefix NotationSlide 25Postfix Notation (Reverse Polish)Evaluating Postfix NotationSlide 281Tree TraversalSection 9.3Longin Jan LateckiTemple UniversityBased on slides byPaul Tymann, Andrew Watkins,and J. van Helden2Tree AnatomyRSY ZXTU V WRootInternal NodeLeafSubtreeLevel 0Level 1Level 2Level 3Child of XParent of Z and YThe children of a node are, themselves, trees, called subtrees.3Tree Traversals•One of the most common operations performed on trees, are a tree traversals•A traversal starts at the root of the tree and visits every node in the tree exactly once–visit means to process the data in the node•Traversals are either depth-first or breadth-first4Breadth First Traversals•All the nodes in one level are visited•Followed by the nodes the at next level•Beginning at the root•For the sample tree–7, 6, 10, 4, 8, 13, 3, 5763 54108 135Queue and stack•A queue is a sequence of elements such that each new element is added (enqueued) to one end, called the back of the queue, and an element is removed (dequeued) from the other end, called the front•A stack is a sequence of elements such that each new element is added (or pushed) onto one end, called the top, and an element is removed (popped) from the same end6Breadth first tree traversal with a queue•Enqueue root•While queue is not empty–Dequeue a vertex and write it to the output list–Enqueue its children left-to-rightStep Output Queue7Depth-First Traversals•There are 8 different depth-first traversals–VLR (pre-order traversal)–VRL–LVR (in-order traversal)–RVL–RLV–LRV (post-order traversal)8Pre-order Traversal: VLR•Visit the node•Do a pre-order traversal of the left subtree•Finish with a pre-order traversal of the right subtree•For the sample tree–7, 6, 4, 3, 5, 10, 8, 13763 54108 139Pre-order tree traversal with a stack•Push root onto the stack•While stack is not empty–Pop a vertex off stack, and write it to the output list–Push its children right-to-left onto stackStep Output Stack10Preorder TraversalrT1T2TnStep 1: Visit rStep 2: Visit T1 in preorderStep n+1: Visit Tn in preorderStep 3: Visit T2 in preorder11ExampleA R EY PM HJ Q TAREYPMHJQ T12Ordering of the preorder traversal is the same a the Universal Address System with lexicographic ordering. A R EY PM HJ Q TAREYPMHJQ T01 2 31.12.12.22.2.1 2.2.2 2.2.313In-order Traversal: LVR•Do an in-order traversal of the left subtree•Visit the node•Finish with an in-order traversal of the right subtree•For the sample tree–3, 4, 5, 6, 7, 8, 10, 13763 54108 1314Inorder TraversalStep 1: Visit T1 in inorderStep 2: Visit rStep n+1: Visit Tn in inorderStep 3: Visit T2 in inorderrT1T2Tn15ExampleA R EY PM HJ Q TAREYPMHJQ T16inorder (t) if t != NIL: { inorder (left[t]);write (label[t]);inorder (right[t]); }Inorder Traversal on a binary search tree.17Post-order Traversal: LRV763 54108 13•Do a post-order traversal of the left subtree•Followed by a post-order traversal of the right subtree •Visit the node•For the sample tree–3, 5, 4, 6, 8, 13, 10, 718Postorder TraversalStep 1: Visit T1 in postorderStep 2: Visit T2 in postorderStep n+1: Visit rStep n: Visit Tn in postorderrT1T2Tn19ExampleA R EYP MHJ Q TAREYPMHJQ T20Representing Arithmetic Expressions•Complicated arithmetic expressions can be represented by an ordered rooted tree–Internal vertices represent operators–Leaves represent operands•Build the tree bottom-up–Construct smaller subtrees–Incorporate the smaller subtrees as part of larger subtrees21Example(x+y)2 + (x-3)/(y+2)+xy2–x3+y2/+22Infix Notation+–+/+2xyx3y2•Traverse in inorder (LVR) adding parentheses for each operationx+y( )2( )+x–3( )/y+2( )( )( )23Prefix Notation(Polish Notation)•Traverse in preorder (VLR)x+y2+x–3/y+2+–+/+2xyx3y224Evaluating Prefix Notation•In an prefix expression, a binary operator precedes its two operands•The expression is evaluated right-left•Look for the first operator from the right•Evaluate the operator with the two operands immediately to its right25Example+ / + 2 2 2 / – 3 2 + 1 0+ / + 2 2 2 / – 3 2 1+ / + 2 2 2 / 1 1+ / + 2 2 2 1+ / 4 2 1+ 2 1326Postfix Notation(Reverse Polish)•Traverse in postorder (LRV)x+y2+x–3/y+2+–+/+2xyx3y227•In an postfix expression, a binary operator follows its two operands•The expression is evaluated left-right•Look for the first operator from the left•Evaluate the operator with the two operands immediately to its leftEvaluating Postfix Notation28Example32 2 + 2 / 3 2 – 1 0 + / +4 2 / 3 2 – 1 0 + / +2 3 2 – 1 0 + / +2 1 1 0 + / +2 1 1 / +2 1