JavaScriptの木構造における後順走査（Post-order Traversal）の解説

後順走査（ポストオーダー走査）は、木構造（ツリー）を巡回する方法のひとつで、「根ノードを最後に訪問する」ことからこの名前が付いています。まず左側の部分木をたどり、次に右側の部分木をたどり、最後に根ノードを処理するのが特徴です。

後順走査の流れ

ここでは、ノード A を起点として考えてみましょう。後順走査では、最初に左部分木である B を訪問します。B の部分木も同じく後順でたどられるため、すべてのノードを訪問し終えるまで処理が再帰的に続きます。この木に対して後順走査を行った場合の出力結果は以下の通りです。

D → E → B → F → G → C → A

後順走査のアルゴリズム

今回実装するアルゴリズムの手順は次のようになります。

• 左部分木を再帰的に走査する
• 右部分木を再帰的に走査する
• ノードのデータを出力する

それでは、クラスの中でこれをどのように実装するか見ていきましょう。

postOrder() {
   postOrderHelper(this.root);
}

そして、実際の処理を担うヘルパー関数は以下のようになります。

コード例

function postOrderHelper(root) {
   if (root !== null) {
      postOrderHelper(root.left);
      postOrderHelper(root.right);
      console.log(root.data);
   }
}

この関数では、まずノードが存在するかどうかを確認し、存在する場合は「左→右→自分」の順で処理を進めます。null に到達した時点でその呼び出しは終了し、再帰が巻き戻されながら各ノードのデータが出力されていく仕組みです。

動作確認

実際に二分探索木を作成して、後順走査が正しく機能するかテストしてみましょう。

コード例

let BST = new BinarySearchTree();
BST.insertRec(10);
BST.insertRec(15);
BST.insertRec(5);
BST.insertRec(50);
BST.insertRec(3);
BST.insertRec(7);
BST.insertRec(12);
BST.postOrder();

実行結果

上記のコードを実行すると、次のような出力が得られます。

3
7
5
12
50
15
10

出力を見ると、最小値から順に葉に近いノードが先に表示され、根ノードである 10 が最後に出力されていることがわかります。これこそが後順走査の最大の特徴であり、ノードの削除処理や、子ノードを先に評価したい場面などで特に役立つ走査手法です。