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