Binary tree inorder traversal

inorder traversal using a queue and binary search tree inorder traversal
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
ECE 250 Algorithms and Data Structures In-Order Traversals Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.In-order traversals 2 Outline In this topic we will look at: – In-order traversals of binary search trees – Limitations of in-order traversals with n-ary treesIn-order traversals 3 4.11.1 In-order Traversals We’ve seen two depth-first traversals: – Pre-order – Post-order First and last visits during an Euler walkIn-order traversals 4 4.11.1 In-order Traversals For binary trees, there is a third intermediate visit – An in-order depth-first traversalIn-order traversals 5 4.11.1 In-order Traversals This visits a binary search tree in order A, B, C, D, E, F, G, H, I, JIn-order traversals 6 Application An implementation of an in-order traversal template typename Type void Binary_treeType::in_order_traversal() const if ( empty() ) return; left()-in_order_traversal(); cout retrieve(); right()-in_order_traversal(); In-order traversals 7 4.11.1.1 In-order traversals on expression trees Printing an expression tree (pretty printing or human-readable printing) using in-fix notation requires an in-order traversal (3x + 5 + y)(z + 7)In-order traversals 8 Application class Expression_node; void Expression_node::pretty_print() 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 "("; // pre-order visit left()-pretty_print(); // traverse left tree // The in-order step: print this object cout this; // print this objectIn-order traversals 9 Application if ( leaf() ) right()-pretty_print(); // traverse right sub-tree // 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 ")"; // post-order visit In-order traversals 10 4.11.1.3 In-order traversals on general trees An in-order traversal does not make sense for either general trees or N-ary trees with N 2In-order traversals 11 Summary In this topic, we have looked at: – In-order depth-first traversals – Limitations on N-ary and binary treesIn-order traversals 12 References 1 Cormen, Leiserson, and Rivest, Introduction to Algorithms, MIT Press, 1990, §7.1-3, p.152. rd 2 Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, §6.5-6, p.215-25.In-order 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 dwharderalumni.uwaterloo.ca