データ構造 巡回結果からの木の構築 Tree – Reconstruction of a Tree

投稿者: | 2016-07-06

先行順巡回 (preorder tree walk) と中間順巡回 (inorder tree walk)を行った結果の節点の列から、 後行順巡回 (postorder tree walk) で得られる節点の列を生成したい。

目的を達成するには、木を構築すれば良い。構築した木をPostorderで巡回することにより、目的を達したことになる。

まずは、それぞれの特徴を考える preorderは節点、左部分木、右部分木の順で回る。なので、preorderの結果の先頭は必ずrootになる。

一方、inorderでは、左部分木、節点、右部分木の順で回る。なので、preorderで発見したrootの位置で列を分割してみる。(分割するrootはどちらにも含まないようにする。) そうしてできた左の列と右の列は、それぞれ左部分木、右部分木になる。

以上のような点から、

1. ある部分木について、preorderから、節点を見つける

2. 見つけた節点でinorderを分割し、左部分木、右部分木を作る(実際はinorderの列)

3. 2で作った左右それぞれの部分木に対応するpreorderの列を生成する。

4. 2,3で作った左右それぞれのpreorderとinorderの列に対して、1を再帰的に実行する

を実行すればよい。

簡単な例

preorder: 1 2 3 4 5
inorder: 3 2 4 1 5
と与えられた時、

1. preorderを見て、rootは1。

2. inorderとrootが1であることから、rootの左部分木は、324の列になり、右部分木は、5になる。

この時点でrootの右部分木は確定する。子が5のみ。

3. preorderで324が出てくる部分は2番目から4番目なので、preorderの列は、234となる。

4. preorder=234、inorder=324として1に戻る。

1. preorderより、部分木の根root_partは2。

2. inorderとroot_partが2であることから、root_partの左部分木は、3となり、右部分木は、4となる。

この時点でroot_partの左部分木と右部分木は確定する。左の子が3。右の子が4。 これで元の木ができた。

下のような感じ。(雑)
   1
 2   5
3 4

これをPostorderで回ればよい。

コメントを残す