如何使用B-Tree进行InOrder遍历？

Question

struct BTreeNode {
    bool is_leaf=true;
    std::vector<int> elements;
    std::vector<BTreeNode*> children;
    BTreeNode() {}
    BTreeNode (std::vector<int> v) {
    this->elements = v;
    }
};

void traverse(BTreeNode* root) {
  for(int i = 0; i < (int)root->children.size(); ++i){
    traverse(root->children[i]);
    cout << root->elements[i] << endl;
  }
  traverse(root->children[root->children.size() -1]);
}

我的方法不知何故段错误。我们如何为B-tree编写正确的inOrder Traversal？

Answer 1

当你在一片叶子时，这可能是最后一次横越调用。我认为不需要这种遍历。

Answer 2

假设BTreeNode是b树节点的通用定义，而T1是键的类型，T2是树中值的类型，而sortedKeys是您所追求的列表，则可以使用以下递归方法。这个想法非常类似于二元搜索树中的inOrder遍历，首先访问最左边的子节点，然后访问密钥 - 然后继续，因为B树中的子节点数总是比键数大一个，在访问密钥之前需要检查[代码在c＃中，但可以很容易地转换为任何其他语言，目的是仅显示算法]。

public void InOrderTraversal(BTreeNode<T1, T2> node, List<KeyValuePair<T1, T2>> sortedKeys)
        {
            if (node != null)
            {
                for (int i = 0; i < node.Children.Count; i++)
                {
                    InOrderTraversal(node.Children[i], sortedKeys);
                    if (i < node.KeyValues.Count)
                        sortedKeys.Add(node.KeyValues[i]);
                }
            }
        }