Python(24)preorder(行きかけ順)inorder(通りがけ順)postorder(帰りがけ順)の比較

ラベル:

前の関連記事:Python(23)二分木をpostorder(帰りがけ順)で枝付きで出力する


二分木の3種類の出力方法についてまとめておきます。

preorder(行きかけ順)inorder(通りがけ順)postorder(帰りがけ順)はどう違う?



この二分木のノードを出力する方法にはpreorder(行きかけ順)inorder(通りがけ順)postorder(帰りがけ順)の3種類があります。

これらは根Nから左右のノードを取得するのとノードの値を取得するのの順番が違うだけです。

preorder(行きかけ順)
ノードの値を出力
左のノードを取得
右のノードを取得

inorder(通りがけ順)
左のノードを取得
ノードの値を出力
右のノードを取得

postorder(帰りがけ順)
左のノードを取得
右のノードを取得
ノードの値を出力

再帰関数でプログラムするとこれらの違いがよくわかります。

私は再帰関数がよく理解できないのでwhile文でプログラムしていますが、それでも上記の把握する順番は同じです。

ただwhile文では再帰関数のときと違ってそれぞれに相当する部分を単純に入れ換えればよい、というわけにはいきませんでした。

preorder(行きかけ順)inorder(通りがけ順)postorder(帰りがけ順)の元データはすべて同じ二分木であって、ノード同士の関係はすべて同じです。

なのに出力されるものが全然違うように思えたのですが、その出力を1行ずつにしてそれらのノードを枝でつなぐとこれらの相違点がよくわかりました。

以下に掲げる3つの図は左端にそれぞれの走査順に出力したノード、その同じ行の右側に枝と階層をつけて同じノードを出力しています。

これら3つの方法とも階層構造のデータを図にするときによく使うパターンですね。

preorder(行きかけ順)


Python(21)二分木をMSDOSのtreeコマンドのように枝も出力するでしたものです。

ノードインスタンスがないときはスタックに加えないように変更しています。

このpreorder(行きかけ順)では次の二つのinorder(通りがけ順)postorder(帰りがけ順)と違って、これからでてくるノードインスタンスがスタックに入っているために枝を下に伸ばすかどうかの判断はスタックをみるだけで判断できます。

python24.py

python24.py 値がないノードの行も出力したもの。

inorder(通りがけ順)


Python(22)二分木をinorder(通りがけ順)で枝付きで出力するでやったものです。

preorder(行きかけ順)と違って枝を下に伸ばすかどうかはスタックをみてもわからず、スタックとは別に出力済みのノードの階層のリストを用意してそれをみて枝の種類の判断をしています。

これによって各階層の枝の状態を二進数で判断していたのを二進数を使わずプログラムができました。

でも二進数を使ったほうが脳みそで値を把握をしやすいです。

これから出力するノードを入れるスタックとすでに出力したノードのスタックの二種類を脳みそで追っていくのは私には困難で、デバッガ頼りでプログラムしないといけませんでした。

とくにこのinorder(通りがけ順)では左右の子ノードの間に親ノードを出力しないといけないので、スタックの動きは複雑です。

二進数を使っていたときはlevelが枝の階層を表していたのと異なり、今回はlevelがノードの階層を表しています。


python24.py 値がないノードの行も出力したもの。

postorder(帰りがけ順)


Python(23)二分木をpostorder(帰りがけ順)で枝付きで出力するでやったものです。

これもinorder(通りがけ順)と同様に各階層の枝の有無を二進数で判断していたのを、出力済みのノードの階層を収めたリストを用意することで二進数を使わずプログラムができました。

inorder(通りがけ順)のときと異なり、リストlst_d_levelには階層順に収納されるのでまだわかりやすいです。

python24.py

python24.py 値がないノードの行も出力したもの。

次の関連記事:Python(25)実行時間を計測する方法

PR

0 件のコメント:

コメントを投稿