java - 如何从最小到最大打印 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 个子节点和 1 个值的内部节点
• 具有 3 个子节点和 2 个值的内部节点
• 没有孩子和 1 或 2 个值的叶子

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

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

/* 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 */
}