ホニャホニャorder traversalからtreeを作る問題の考え方

• Preorder traversalから木を求める
• Level order traversalから木を求める
• Postorder traversalから木を求める

をお届けします。

Preorder traversalから木を求める

問題

Binary search treeがあるとします。そのPreorder traversalでは値は以下のように並びます。

3, 1, 2, 6, 4, 5, 7

この時、Postorder traversalをするとどういう結果になるでしょうか。

また3をこのBinary search treeから削除した場合、the Level order traversalはどういう結果を表示するでしょうか。

解き方

Preorder traversalは、Root -> Left -> Rightと探索していきます。そのため、結果の1つ目の要素は木全体の親の値です。またBSTの性質から、親の3より小さい値はleft subtreeへ、3より大きい値はright subtreeへ属します。

       3
{1, 2}   {6, 4, 5, 7}

つぎに{1,2}と{6,4,5,7}を見ていくわけですが、これらの列の最初はそのsubtreeの親になります。{1,2}から成るleft subtreeは1が親で2が子となります。同様に、{6, 4, 5, 7}では6が親となり、{4,5}が、left subtreeとなり、{7}がright subtreeとなります。

       3
    1    6 
   2  {4, 5} {7}

上の操作を繰り返します。4がsubtreeの親となります。right subtreeも完成します。

       3
    1     6 
   2   4    7
        5   

上の木をPostorder traverse（Left -> Right -> Root）すればいいので、2,1,5,4,7,6,3となります。

ここから親ノードの3を消すわけですが、この時、right subtreeから親のノードの次に大きいnodeを親として持ってきます。right subtreeのminumum nodeを探します。それは4です。

       4
    1     6 
   2     5  7

the Level order traversalは親のノードから下へかつ左から右のノードの値を並べれば良いので、4,1,6,2,5,7となります。

Level order traversalから木を求める

Level order traversalで以下のように表示されるBinary search treeがあったとします。

3, 2, 5, 1, 4 ,8, 6, 7

この木を Preorder traversalで表示するとどうなるでしょうか。
また5を削除した場合をPostorder traversalで表示するとどうなるでしょうか

解き方

今回はLevel order traversalなので簡単です。BSTの制約である、(左の子ノードの値)<(親ノードの値)<(右の子ノードの値)を破らないように並べてきます。

      3
   2      5
  1     4   8
           6  7

これをPreorder traversalで表示すればいいので3,2,1,5,4,8,6,7となります。

5を削除します。このとき、5を親と見た時のright subtreeから親のノードの次に大きいnodeを親として持ってきます。６がそれに当たります。

      3
   2      6
  1     4   8
             7

Postorder traversalで表示すると1,2,4,7,8,6,3となります。

Postorder traversalから木を求める

Postorder traversalで以下のように表示されるBinary search treeがあったとします。

1, 3, 4, 5, 2, 8, 7, 6

この木をLevel order traversalで表示するとどうなるでしょうか。
また2を削除した場合をPreorder traversalで表示するとどうなるでしょうか

解き方

Preorder traversalは、Left -> Right -> Rootと探索していきます。そのため、結果の最後の要素は木全体の親の値です。またBSTの性質から、親の6より小さい値はleft subtreeへ、3より大きい値はright subtreeへ属します。

            6
{1,3,4,5,2}  {8,7}  

つぎに{1,3,4,5,2}と{8,7}を見ていくわけですが、これらの列の最後の要素も同様に、そのsubtreeの親になります。{1,3,4,5,2}から成るleft subtreeは2が親となり、そのleft subtreeは{1}、right subtreeは{3,4,5}です。同様に、{8, 7}では7が親となります。

                  6
           2          7 
      {1} {3,4,5}       8  

同様の操作を繰り返します。

                  6
           2          7 
       1     5          8  
            4
	   3

Level order traversalで表示すると、6,2,7,1,5,8,4,3となります。

2を削除します。このとき、2を親と見た時のright subtreeから親のノードの次に大きいnodeを親として持ってきます。3がそれに当たります。

                6
           3       7 
         1   5      8  
            4	   

Preorder traversalで表示すると、6,3,1,5,4,7,8となります。