c++ - 在 2-3 树中找到正确的祖先

Question

所以我很难在 2-3 树中找到正确的祖先。在任意高度的 2-3 树中，有几种情况需要寻找。

我的节点设计如下：

template<typename DataType>
struct node{
   Node<DataType> *child1; //left-child
   Node<DataType> *child2; //middle-child (3-node only)
   Node<DataType> *child3; //right-child
   Node<DataType> *extraChild; //for splitting purposes

   Node<DataType> *parent;

   DataType key1; //key1 <= key2
   DataType key2; //key2 <= extraKey (only when node needs to be split)
   DataType extraKey; //for splitting purposes
};

是否有算法或类似的东西来找到节点的正确祖先？

例如，假设我们正在寻找 H 的祖先（提供的树的底部），从视觉角度来看，很明显 H 的祖先是树根处的 H。但这需要跳上 4 个父链接。树可能是任意大小，这是问题所在。

我最终的目标是创建一个按顺序遍历 2-3 树的迭代器。查找祖先节点的目的是，祖先节点将成为其父节点的右孩子叶节点的有序后继。同样，如上面提供的示例所示。

Answer 1

如果目标只是按顺序遍历 2-3 树，那么您只需要编写一个从根开始的递归函数。

算法如下：

traverse(Node n)

    if n.left != null
        traverse(n.left)

    if n.middle != null
        visit(n.key1)
        traverse(n.middle)
        visit(n.key2)
    else
        visit(n.key1)

    if n.right != null
        traverse(n.right)

取自此链接的算法。