Question? Leave a message!




Left-child right-sibling binary tree

Left-child right-sibling binary tree
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
Comment
ECE 250 Algorithms and Data Structures Left-child 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.Left-child right-sibling binary tree 2 Background Our simple tree data structure is node-based where children are stored as a linked list – Is it possible to store a general tree as a binary tree?Left-child right-sibling binary tree 3 The Idea Consider the following: – The first child of each node is its left sub-tree – The next sibling of each node is in its right sub-tree This is called a left-child—right-sibling 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.Left-child right-sibling binary tree 12 Transformation The transformation of a general tree into a left-child right-sibling 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.Left-child right-sibling binary tree 15 Implementation The class is similar to that of a binary tree template typename Type class LCRS_tree private: Type element; LCRS_tree first_child_tree; LCRS_tree next_sibling_tree; public: LCRS_tree(); LCRS_tree first_child(); LCRS_tree next_sibling(); // ... ;Left-child right-sibling binary tree 16 Implementation The implementation of various functions now differs – An iterative approach is much more desirable template typename Type int LCRS_treeType::degree() const int count = 0; for ( LCRS_treeType ptr = first_child(); ptr = nullptr; ptr = ptr-next_sibling() ) ++count; return count; Left-child right-sibling binary tree 17 Implementation The implementation of various functions now differs template typename Type bool LCRS_treeType::is_leaf() const return ( first_child() == nullptr ); Left-child right-sibling binary tree 18 Implementation The implementation of various functions now differs template typename Type LCRS_treeType LCRS_treeType::child( int n ) const if ( n 0 n = degree() ) return nullptr; LCRS_treeType ptr = first_child(); for ( int i = 0; i n; ++i ) ptr = ptr-next_sibling(); return ptr; Left-child right-sibling binary tree 19 Implementation The implementation of various functions now differs template typename Type void LCRS_treeType::append( Type const &obj ) if ( first_child() == nullptr ) first_child_tree = new LCRS_treeType( obj ); else LCRS_treeType ptr = first_child(); while ( ptr-next_sibling() = nullptr ) ptr = ptr-next_sibling(); ptr-next_sibling_tree = new LCRS_treeType( obj ); Left-child right-sibling 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 LCRS_treeType::size() const return 1 + ( first_child() == nullptr ? 0 : first_child()-size() ) + ( next_sibling() == nullptr ? 0 : next_sibling()-size() );