Question? Leave a message!




Left-child right-sibling binary tree

Left-child right-sibling binary tree
ECE 250 Algorithms and Data Structures Leftchild right sibling binary tree Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20143 by Douglas Wilhelm Harder. Some rights reserved.Leftchild rightsibling binary tree 2 Background Our simple tree data structure is nodebased where children are stored as a linked list – Is it possible to store a general tree as a binary treeLeftchild rightsibling binary tree 3 The Idea Consider the following: – The first child of each node is its left subtree – The next sibling of each node is in its right subtree This is called a leftchild—rightsibling binary treeECE 250 Algorithms and Data Structures Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20143 by Douglas Wilhelm Harder. Some rights reserved.ECE 250 Algorithms and Data Structures Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20143 by Douglas Wilhelm Harder. Some rights reserved.ECE 250 Algorithms and Data Structures Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20143 by Douglas Wilhelm Harder. Some rights reserved.ECE 250 Algorithms and Data Structures Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20143 by Douglas Wilhelm Harder. Some rights reserved.ECE 250 Algorithms and Data Structures Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20143 by Douglas Wilhelm Harder. Some rights reserved.ECE 250 Algorithms and Data Structures Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20143 by Douglas Wilhelm Harder. Some rights reserved.ECE 250 Algorithms and Data Structures Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20143 by Douglas Wilhelm Harder. Some rights reserved.ECE 250 Algorithms and Data Structures Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20143 by Douglas Wilhelm Harder. Some rights reserved.Leftchild rightsibling binary tree 12 Transformation The transformation of a general tree into a leftchild rightsibling binary tree has been called the Knuth transformECE 250 Algorithms and Data Structures Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20143 by Douglas Wilhelm Harder. Some rights reserved.ECE 250 Algorithms and Data Structures Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20143 by Douglas Wilhelm Harder. Some rights reserved.Leftchild rightsibling binary tree 15 Implementation The class is similar to that of a binary tree template typename Type class LCRStree private: Type element; LCRStree firstchildtree; LCRStree nextsiblingtree; public: LCRStree(); LCRStree firstchild(); LCRStree nextsibling(); // ... ;Leftchild rightsibling binary tree 16 Implementation The implementation of various functions now differs – An iterative approach is much more desirable template typename Type int LCRStreeType::degree() const int count = 0; for ( LCRStreeType ptr = firstchild(); ptr = nullptr; ptr = ptrnextsibling() ) ++count; return count; Leftchild rightsibling binary tree 17 Implementation The implementation of various functions now differs template typename Type bool LCRStreeType::isleaf() const return ( firstchild() == nullptr ); Leftchild rightsibling binary tree 18 Implementation The implementation of various functions now differs template typename Type LCRStreeType LCRStreeType::child( int n ) const if ( n 0 n = degree() ) return nullptr; LCRStreeType ptr = firstchild(); for ( int i = 0; i n; ++i ) ptr = ptrnextsibling(); return ptr; Leftchild rightsibling binary tree 19 Implementation The implementation of various functions now differs template typename Type void LCRStreeType::append( Type const obj ) if ( firstchild() == nullptr ) firstchildtree = new LCRStreeType( obj ); else LCRStreeType ptr = firstchild(); while ( ptrnextsibling() = nullptr ) ptr = ptrnextsibling(); ptrnextsiblingtree = new LCRStreeType( obj ); Leftchild rightsibling binary tree 20 Implementation The implementation of various functions now differs – The size doesn’t care that this is a general tree… template typename Type int LCRStreeType::size() const return 1 + ( firstchild() == nullptr 0 : firstchild()size() ) + ( nextsibling() == nullptr 0 : nextsibling()size() ); Leftchild rightsibling binary tree 21 Implementation The implementation of various functions now differs – The height member function is closer to the original implementation template typename Type int LCRStreeType::height() const int h = 0; for ( LCRStreeType ptr = firstchild(); ptr = nullptr; ptr = ptrnextsibling() ) h = std::max( h, 1 + ptrheight() ); return h; Leftchild rightsibling binary tree 22 Summary This topic has covered a binary representation of general trees – The first child is the left subtree of a node – Subsequent siblings of that child form a chain down the right subtrees – An empty left subtree indicates no children – An empty right subtree indicates no other siblingsLeftchild rightsibling binary tree 23 References 1 Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, nd 2 Ed., MIT Press, 2001, §19.1, pp.4579. rd 2 Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, §6.8.1, p.240.Leftchild rightsibling binary tree 24 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
Website URL
Comment
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017