如何从最小到最大打印 2-3 棵树？

Question

我不知道如何处理该算法。我在想这样的事情：

TreeNode n = root;
while(n.first.first!=0){ 
    n=n.first;
} // finding the leftMost parent
//printing the first child key, then first num of parent, then second child.. and so on

有人有更好的主意吗？

Answer 1

根据2-3树的定义，可以遇到3种类型的节点：

具有 2 个 children 和 1 个值的内部节点
具有 3 个 children 和 2 个值
没有 children 和 1 或 2 个值的叶

有了这些信息，您可以使用递归方法遍历节点，从根节点开始。如果它遇到叶节点，它只打印值。在其他情况下，该方法必须为最左边的节点调用自身（跳转到左边的节点），然后打印第一个值，然后跳转到下一个节点等等。之后该方法结束，因此整个算法结束（如果实际节点是根节点）或跳回到 parent 节点（如果实际节点是内部节点，children 节点）

这是伪代码。我把实际的实现留给了你自己。研究并确保您了解该方法的流程（您可以使用调试器并跟踪实际参数）

/* you start algorithm by calling recursivePrint(root) */

void recursivePrint(node){

    if (node is a leaf){

        /* Here print node's value/values */

    } else if (node has 2 children){

        recursivePrint(node.leftChild);
        /* Here print node's value */
        recursivePrint(node.rightChild);

    } else if (node has 3 children)

        recursivePrint(node.leftChild);
        /* Here print node's left value */
        recursivePrint(node.middleChild);
        /* Here print node's right value */
        recursivePrint(node.rightChild)

    }

    /* Shouldn't be other cases in 2-3 trees */
}

如何从最小到最大打印 2-3 棵树？

How to print 2-3 tree from min to max?

java

data-structures

tree

2-3-tree