c++ - Btree をトラバースする方法は?

Question

私は Btree を持っており、キーが昇順で表示されるようにそれをトラバースする方法を理解しようとしています。

私が理解できるのは、これが再帰関数で実行できるということだけです。

それを行うための擬似コードは何ですか?

Answer 1

次のような定義があるとします。

template <class T>
class btree_node
{
    btree_node **child;  // an array of child nodes
    T **element;  // the elements in this node

    unsigned int child_count; // the number of children
                              // the number of elements is 1 less then child_count
};

次に、次のようなことをする必要があります。

void btree_inorder(node):
    for (int i = 0; i < node.child_count; ++i)
    {
        btree_inorder(node.child[i]);
        handle_element(node.element[i]);
    }
    btree_inorder(node.child[node.child_count-1]);