先行順巡回 (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で回ればよい。
コメント