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（通りがけ順）

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

postorder（帰りがけ順）

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

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

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

python24.py

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

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