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