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

前の関連記事：Python(22)二分木をinorder（通りがけ順）で枝付きで出力する

preorder(行きかけ順）とinorder（通りがけ順）をやってきたので、最後にpostorder（帰りがけ順）をします。

まずは枝無しでpostorder（帰りがけ順）に出力する

python23.py
Python(20)MSDOSのtreeコマンドのように枝も出力する:いまいち編でやったpreorder(行きかけ順）を下から始めたような感じですね。

            ┌─A
            ├─C
        ┌─B
        │  ┌─E
        │  │
        ├─F
    ┌─D
    │      ┌─H
    │      ├─J
    │  ┌─I
    │  │  ┌─L
    │  │  │
    │  ├─M
    ├─K
┌─G
│          ┌─O
│          ├─Q
│      ┌─P
│      │  ┌─S
│      │  │
│      ├─T
│  ┌─R
│  │      ┌─V
│  │      │
│  │  ┌─W
│  │  │  ┌─Y
│  │  │  │
│  │  ├─Z
│  ├─X
├─U
N

これを出力できるようにします。

枝付きでpostorder（帰りがけ順）に出力する

python23.py

            ┌─A
            ├─C
        ┌─B
        │  ┌─E
        │  │
        ├─F
    ┌─D
    │      ┌─H
    │      ├─J
    │  ┌─I
    │  │  ┌─L
    │  │  │
    │  ├─M
    ├─K
┌─G
│          ┌─O
│          ├─Q
│      ┌─P
│      │  ┌─S
│      │  │
│      ├─T
│  ┌─R
│  │      ┌─V
│  │      │
│  │  ┌─W
│  │  │  ┌─Y
│  │  │  │
│  │  ├─Z
│  ├─X
├─U
N

やっぱりこの場合もスタックだけでは枝の種類を確定できず二進数を使っています。

例えば右のノードにつながる枝は"┌─"か"├─"かは上の行に同じ階層のノード、つまり左のノードがあるかどうかで決まりますが、右のノードを出力するときには左のノードはすでに消費されてスタックから消されてしまっているので、スタックを見ただけでは左のノードがあったかどうかはわかりません。

ということでその情報を保存しておくために二進数が必要となります。

別に二進数でなくても、出力したノードを収めるスタックをもう一つ作ってもよいかもしれませんね。

うーん、そっちの方がわかりやすいかも。

とりあえず前回までと同様にノードの値がないときは出力しないバージョンも作っておきます。

python23.py

            ┌─A
            ├─C
        ┌─B
        │  ┌─E
        ├─F
    ┌─D
    │      ┌─H
    │      ├─J
    │  ┌─I
    │  │  ┌─L
    │  ├─M
    ├─K
┌─G
│          ┌─O
│          ├─Q
│      ┌─P
│      │  ┌─S
│      ├─T
│  ┌─R
│  │      ┌─V
│  │  ┌─W
│  │  │  ┌─Y
│  │  ├─Z
│  ├─X
├─U
N

参考にしたサイト

Data Structures Notes: Binary tree traversal: Preorder, Inorder, and Postorder
preorder(行きかけ順）やinorder（通りがけ順）、postorder（帰りがけ順）の比較がわかりやすいです。

次の関連記事:Python(24)preorder(行きかけ順）inorder（通りがけ順）postorder（帰りがけ順）の比較