Left-child Right-sibling Binary Tree

Given a N-ary tree construct a new binary tree as follows:

For node n in the binary tree, the left child correponds to the children of n in the original N-ary tree
the right child of n should include all the siblings of n in the original N-ary tree

An empty left sub-tree indicates no children, i.e. that is a leaf node
An empty right subtree indicates that is the last sibling
The root node doesn't have any right subtree

Transformation

Transforming a general tree to a left-child right-sibling tree is called Knuth trasnformation.

Traversals

Pre-order: pre-order traversal in the original tree is identical to pre-order traversal in the Knuth-transformed tree.
Post-order: post-order traversal in the Knuth trasnform tree, requires three steps: left, root, right
- first traverse all the nodes on the left subtree
- then visit the current node
- move on to the right and traverse the right subtree

Implementation

LCRS_tree class

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();

};

degree()

template<typename Type>
int LCRS_tree<Type>::degree() const {
    int count = 0;
    for (LCRS_tree *ptr = first_child();
         ptr != nullptr;
         ptr = ptr->next_sibling()) {
            ++ count;
    }
    return count;
}

is_leaf()

template<typename Type>
bool LCRS_tree<Type>::is_leaf() const {
    return (first_child() == nullptr);
}

size()

template<typename Type>
int LCRS_tree<Type>::size() const {
    return 1 +
        (first_child() == nullptr ? 0 : first_child()->size()) +
        (next_sibling() == nullptr ? 0 : next_sibling()->size());
}

height()

template<typename Type>
int LCRS_tree<Type>::height() const {
    int h = 0;

    for (LCRS_tree *ptr = first_child();
         ptr != nullptr;
         ptr = ptr->next_sibling()) {
        h = std::max(h, 1 + ptr->height());
    }

    return h;
}



In [ ]: