如何遍歷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]);