Question? Leave a message!




In-Order Traversals

In-Order Traversals
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
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
sharer
Presentations
Free