Left-child right-sibling binary tree

basic terminology of tree in data structure and binary search tree traversal inorder preorder postorder example
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 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 treeLeft-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 transformLeft-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() ); Left-child right-sibling 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 LCRS_treeType::height() const int h = 0; for ( LCRS_treeType ptr = first_child(); ptr = nullptr; ptr = ptr-next_sibling() ) h = std::max( h, 1 + ptr-height() ); return h; Left-child right-sibling binary tree 22 Summary This topic has covered a binary representation of general trees – The first child is the left sub-tree of a node – Subsequent siblings of that child form a chain down the right sub-trees – An empty left sub-tree indicates no children – An empty right sub-tree indicates no other siblingsLeft-child right-sibling binary tree 23 References 1 Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, nd 2 Ed., MIT Press, 2001, §19.1, pp.457-9. rd 2 Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, §6.8.1, p.240.Left-child right-sibling 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