B-Tree如何进行中序遍历？

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-tree 节点的通用定义，而 T1 是键的类型，T2 是树中值的类型，而 sortedKeys 是您之后的列表，您可以使用下面的递归方法。思路很像二叉搜索树中的中序遍历，先访问left-mostchild，然后访问key-再继续，因为children的个数在[=15] =]总是比键的个数大1，访问键前需要检查[代码是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]);
                }
            }
        }

B-Tree如何进行中序遍历？

How to do InOrder traversal with B-Tree?

c++

b-tree