JavaScript でのツリー トラバーサルの探索: インオーダー、プレオーダー、ポストオーダーと例

ツリー トラバーサルは、ツリー データ構造内の各ノードを体系的に訪問することを含むコンピューター サイエンスの基本的な概念です。ツリー トラバーサルを通じて、あらかじめ決められた順序でノードを処理できるため、検索、並べ替え、式の評価などの操作が容易になります。

この記事では、最も広く使用されている 3 つのツリー走査方法、inorder、preorder、postorder について説明します。

JavaScript で実装された明確で簡潔な例を通じて、これらのトラバーサル手法をしっかりと理解できます。

ツリー構造の定義

ツリー トラバーサル アルゴリズムに入る前に、バイナリ ツリーに使用する構造を定義しましょう。ツリーはノードで構成され、各ノードには値とその左右の子ノードへの参照が含まれます。

 function TreeNode(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; }

ツリー構造を定義したので、3 つのツリー走査方法の検討に進むことができます。

インオーダートラバーサル

インオーダートラバーサルは、バイナリツリー内のノードを訪問する次のパターンに従います。アルゴリズムは、最初に左側のサブツリーを移動し、次に現在のノードを訪問し、最後に右側のサブツリーを移動します。これにより、ツリーがソートされたデータ構造を表す場合、ノードが昇順でアクセスされることが保証されます。

 A / \ BC / \ / \ DEFG // Inorder traversal result: D -> B -> E -> A -> F -> C -> G

再帰的な順序トラバーサル

1. 現在のノードが null かどうかを確認します。そうであれば、戻ってください。

   
   

2. 左側のサブツリーの関数を再帰的に呼び出します。

   
   

3. 現在のノードにアクセスします。

   
   

4. 右側のサブツリーで関数を再帰的に呼び出します。

 function inorderRecursive(tree) { const result = []; function inorderTraverse(node) { if (!node) return; inorderTraverse(node.left); result.push(node.val); inorderTraverse(node.right); } inorderTraverse(tree); return result; }

非再帰的なインオーダートラバーサル

1. 空のスタックを初期化し、現在のノードをツリーのルートに設定します。

   
   

2. スタックが空でない間、または現在のノードが null でない間、繰り返します。

   • null の左の子に到達するまで、すべての左のノードをスタックにプッシュします。

   • スタックからノードをポップし、そこにアクセスし、現在のノードをその右側の子に設定します。

     
     

3. スタックが空になり、現在のノードが null になるまでステップ 2 を繰り返します。

 function inorderRecursive(tree) { const stack = []; const result = []; let currentNode = tree; while (currentNode || stack.length) { while (currentNode) { stack.push(currentNode); currentNode = currentNode.left; } const node = stack.pop(); result.push(node.val); currentNode = node.right; } return result; }

予約注文トラバーサル

プリオーダートラバーサルでは、アルゴリズムは最初に現在のノードを訪問し、次に左のサブツリーをトラバースし、最後に右のサブツリーをトラバースします。この順序により、ノードはルートから開始してリーフに向かって「トップダウン」方式でアクセスされるようになります。

 A / \ BC / \ / \ DEFG // Preorder traversal result: A -> B -> D -> E -> C -> F -> G

再帰的な事前注文トラバーサル

1. 現在のノードが null かどうかを確認します。そうであれば、戻ってください。

   
   

2. 現在のノードにアクセスします。

   
   

3. 左側のサブツリーの関数を再帰的に呼び出します。

   
   

4. 右側のサブツリーで関数を再帰的に呼び出します。

   
   

 function preorderRecursive(tree) { const result = []; function preorderTraverse(node) { if (!node) return; result.push(node.val); preorderTraverse(node.left); preorderTraverse(node.right); } preorderTraverse(tree); return result; }

非再帰的な事前注文トラバーサル

1. 空のスタックから開始し、ルート ノードをスタックにプッシュします。

   
   

2. 空の配列を初期化して、事前順序走査結果を保存します。

   
   

3. スタックが空になるまで実行される while ループを入力します。

   
   

4. スタックからノードをポップし、その値を結果の配列に追加してアクセスします。

   
   

5. ノードに右側の子がある場合は、右側の子をスタックにプッシュします。

   
   

6. ノードに左の子がある場合は、左の子をスタックにプッシュします。

   
   

7. スタックが空になるまで手順 3 ～ 6 を繰り返します。

 function preorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack.pop(); result.push(node.val); if (node.right) stack.push(node.right); if (node.left) stack.push(node.left); } return result; }

事後トラバーサル

この走査では、アルゴリズムは最初に左側のサブツリーを走査し、次に右側のサブツリーを走査し、最後に現在のノードにアクセスします。この順序により、ノードはリーフから開始してルートに向かって「ボトムアップ」方式でアクセスされるようになります。

 A / \ BC / \ / \ DEFG // Postorder traversal result: D -> E -> B -> F -> G -> C -> A

再帰的なポストオーダートラバーサル

1. 現在のノードが null かどうかを確認します。そうであれば、戻ってください。

   
   

2. 左側のサブツリーの関数を再帰的に呼び出します。

   
   

3. 右側のサブツリーで関数を再帰的に呼び出します。

   
   

4. 現在のノードにアクセスします。

 function postorderRecursive(tree) { const result = []; function postorderTraverse(node) { if (!node) return; postorderTraverse(node.left); postorderTraverse(node.right); result.push(node.val); } postorderTraverse(tree); return result; }

非再帰的なポストオーダートラバーサル

1. 空のスタックから開始し、ルート ノードをスタックにプッシュします。

   
   

2. 空の配列を初期化して、ポストオーダー走査結果を保存します。

   
   

3. スタックが空になるまで実行される while ループを入力します。

   
   

4. スタックから最上位ノードを取得します (削除せずに)。

   
   

5. ノードに左の子がある場合は、左の子をスタックにプッシュし、現在のノードの左の子を null に設定します。

   
   

6. ノードに右側の子がある場合は、右側の子をスタックにプッシュし、現在のノードの右側の子を null に設定します。

   
   

7. ノードに左にも右にも子がない場合、それはリーフ ノードです。スタックからノードをポップし、その値を結果配列に追加します。

   
   

8. スタックが空になるまで手順 4 ～ 7 を繰り返します。

 function postorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack[stack.length - 1]; if (node.left) { stack.push(node.left); node.left = null; } else if (node.right) { stack.push(node.right); node.right = null; } else { result.push(stack.pop().val); } } return result; }

結論

JavaScript における inorder、preorder、postorder のトラバースの違いを明確に理解できたと思います。提供された知識と例により、これらのテクニックを自分のタスクやプロジェクトに効果的に適用できるようになりました。