C++で中間順・先行順トラバーサルから二分木を構築する方法

はじめに

二分木の中間順トラバーサル(Inorder)と先行順トラバーサル(Preorder)の結果が与えられたとき、それらから元の二分木を復元して構築することができます。本記事では、その具体的な考え方と手順をわかりやすく解説します。

中間順トラバーサル(Inorder traversal)とは

中間順トラバーサルでは、「左部分木 → ノード自身 → 右部分木」の順でノードを訪問します。

中間順トラバーサルの手順(root を起点とする場合)

• root が指すノードの左部分木をたどる(inorder(root→left) を再帰呼び出し)
• ノード自身(ルート)を訪問する
• root が指すノードの右部分木をたどる(inorder(root→right) を再帰呼び出し)

先行順トラバーサル(Preorder traversal)とは

先行順トラバーサルでは、「ノード自身 → 左部分木 → 右部分木」の順でノードを訪問します。

先行順トラバーサルの手順(root を起点とする場合)

• ノード自身(ルート)を訪問する
• root が指すノードの左部分木をたどる(preorder(root→left) を再帰呼び出し)
• root が指すノードの右部分木をたどる(preorder(root→right) を再帰呼び出し)

例:対象となる二分木

以下の二分木に対する中間順トラバーサルと先行順トラバーサルの結果は次のとおりです。

中間順(Inorder)

2-3-4-5-6-8-10

先行順(Preorder)

5-3-2-4-8-6-10

トラバーサル結果から木を構築する手順

それでは、上記の中間順・先行順トラバーサルの結果から、元の木を実際に組み立てていきましょう。

• 先行順トラバーサルは必ず最初に根(ルート)ノードを訪問するため、系列の先頭の値が常に木全体の根となります。この例では、先頭の「5」が木の根です。

先行順(Preorder)

5 -3-2-4-8-6-10

• 中間順トラバーサルには「あるノードより前にその左部分木が現れ、後にその右部分木が現れる」という性質があります。したがって、中間順の並びにおいて「5」より左側にある値はすべて左部分木に、「5」より右側にある値はすべて右部分木に属します。

中間順(Inorder)

2-3-4 ← 5 → 6-8-10

• 次に、左部分木に対して同じ操作を繰り返します。

左部分木の先行順トラバーサルは「3-2-4」なので、根は「3」となります。

中間順トラバーサルはさらに「2 ← 3 → 4」と分割されます。

• 同様に、右部分木に対しても同じ操作を行います。

右部分木の先行順トラバーサルは「8-6-10」なので、根は「8」となります。

中間順トラバーサルはさらに「6 ← 8 → 10」と分割されます。

まとめ

このように、先行順トラバーサルで根を特定し、中間順トラバーサルで左右の部分木を切り分ける、という手順を再帰的に繰り返すことで、与えられた先行順・中間順トラバーサルの結果から元の二分木を正確に構築することができます。