C++で指定された順序および事前順序トラバーサルからツリーを構築します

二分木のインオーダートラバーサルとプレオーダートラバーサルが与えられます。目標は、与えられたトラバーサルからツリーを構築することです。

順序のないトラバーサル −このタイプのツリートラバーサルでは、最初に左側のサブツリーにアクセスし、最後にノードと右側のサブツリーにアクセスします。

順序（ツリールート）

• ルートが指すノードの左サブツリーをトラバースし、順番に呼び出します（ルート→左）

• ルートにアクセス

• ルートが指すノードの右サブツリーをトラバースし、順番に呼び出します（ルート→右）

プレオーダートラバーサル −このタイプのツリートラバーサルでは、ノードが最初にアクセスし、最後に左側のサブツリーと右側のサブツリーが続きます。

事前注文（ツリールート）

• ルートにアクセス
• ルートが指すノードの左側のサブツリーをトラバースし、順番に呼び出します（ルート→左）
• ルートが指すノードの右サブツリーをトラバースし、順番に呼び出します（ルート→右）

以下のツリーのインオーダーおよびプレオーダートラバーサルが与えられます-

順序

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

事前注文

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

次に、指定されたプレオーダーおよびインオーダートラバーサルに対して上記のツリーを再度構築します。

順序

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

事前注文

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

• preorderが最初にルートノードにアクセスすることがわかっているので、最初の値は常にツリーのルートを表します。上記のシーケンス5から、ツリーのルートになります。

事前注文

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

• 上記の順序付けられたトラバーサルから、ノードの左側のサブツリーがトラバースされてから、右側のサブツリーが続くことがわかります。したがって、順番に5の左側にあるすべての値は左側のサブツリーに属し、右側にあるすべての値は右側のサブツリーに属します。

順序

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

• 左側のサブツリーについても、上記と同じようにします。

左サブツリーのプレオーダートラバーサルは3-2-4です。したがって、3がルートになります。

インオーダートラバーサルはさらに2←3→4に分割されます

• 正しいサブツリーについては、上記と同じようにします。

右側のサブツリーのプレオーダートラバーサルは8-6-10です。したがって、8がルートになります。

順序トラバーサルはさらに6←8→10に分割されます

したがって、このようにして、指定されたプレオーダーおよびインオーダートラバーサルから元のツリーを構築しました。