Question? Leave a message!

In-Order Traversals

In-Order Traversals
ECE 250 Algorithms and Data Structures InOrder Traversals Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Inorder traversals 2 Outline In this topic we will look at: – Inorder traversals of binary search trees – Limitations of inorder traversals with nary treesInorder traversals 3 4.11.1 Inorder Traversals We’ve seen two depthfirst traversals: – Preorder – Postorder First and last visits during an Euler walkInorder traversals 4 4.11.1 Inorder Traversals For binary trees, there is a third intermediate visit – An inorder depthfirst traversalInorder traversals 5 4.11.1 Inorder Traversals This visits a binary search tree in order A, B, C, D, E, F, G, H, I, JInorder traversals 6 Application An implementation of an inorder traversal template typename Type void BinarytreeType::inordertraversal() const if ( empty() ) return; left()inordertraversal(); cout retrieve(); right()inordertraversal(); Inorder traversals 7 Inorder traversals on expression trees Printing an expression tree (pretty printing or humanreadable printing) using infix notation requires an inorder traversal (3x + 5 + y)(z + 7)Inorder traversals 8 Application class Expressionnode; void Expressionnode::prettyprint() if ( leaf() ) // If the precedence of the parent is higher than that of the // current operator, we need to print an opening parenthesis if ( parent()precedence() precedence() ) cout "("; // preorder visit left()prettyprint(); // traverse left tree // The inorder step: print this object cout this; // print this objectInorder traversals 9 Application if ( leaf() ) right()prettyprint(); // traverse right subtree // If the precedence of the parent is higher than that of the // current operator, we need to print a closing parenthesis if ( parent()precedence() precedence() ) cout ")"; // postorder visit Inorder traversals 10 Inorder traversals on general trees An inorder traversal does not make sense for either general trees or Nary trees with N 2Inorder traversals 11 Summary In this topic, we have looked at: – Inorder depthfirst traversals – Limitations on Nary and binary treesInorder traversals 12 References 1 Cormen, Leiserson, and Rivest, Introduction to Algorithms, MIT Press, 1990, §7.13, p.152. rd 2 Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, §6.56, p.21525.Inorder traversals 13 Usage Notes • These slides are made publicly available on the web for anyone to use • If you choose to use them, or a part thereof, for a course at another institution, I ask only three things: – that you inform me that you are using the slides, – that you acknowledge my work, and – that you alert me of any mistakes which I made or changes which you make, and allow me the option of incorporating such changes (with an acknowledgment) in my set of slides Sincerely, Douglas Wilhelm Harder, MMath
Document Information
User Name:
User Type:
United Kingdom
Uploaded Date: