最小から最大まで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 */ 
}