前の関連記事：Python(21)二分木をMSDOSのtreeコマンドのように枝も出力する
前回preorder(行きかけ順）にノードを枝付きで出力しましたが今度はinorder（通りがけ順）で出力します。
まずは枝無しでpreorder(行きかけ順）に出力する
いまになって気がつきましたがインデントと枝を取り除いてみてみると前回作った枝付き木構造はpreorder(行きかけ順）にノードを1行ずつ出力したものに階層に応じてインデントしてるだけですね。
今度はこれをinorder（通りがけ順）で出力します。
┌─A
┌─B
│ └─C
┌─D
│ │ ┌─E
│ └─F
┌─G
│ │ ┌─H
│ │ ┌─I
│ │ │ └─J
│ └─K
│ │ ┌─L
│ └─M
N
│ ┌─O
│ ┌─P
│ │ └─Q
│ ┌─R
│ │ │ ┌─S
│ │ └─T
└─U
│ ┌─V
│ ┌─W
└─X
│ ┌─Y
└─Z
最終的には枝付きでこのように出力するのが目標です。
python22.py
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
まずは枝無しで出力しました。枝付きでinorder（通りがけ順）に出力する
python22.py
┌─A
┌─B
│ └─C
┌─D
│ │ ┌─E
│ └─F
│
┌─G
│ │ ┌─H
│ │ ┌─I
│ │ │ └─J
│ └─K
│ │ ┌─L
│ └─M
│
N
│ ┌─O
│ ┌─P
│ │ └─Q
│ ┌─R
│ │ │ ┌─S
│ │ └─T
│ │
└─U
│ ┌─V
│ ┌─W
│ │
└─X
│ ┌─Y
└─Z
Python(20)MSDOSのtreeコマンドのように枝も出力する:いまいち編と同様に二進数を使いました。
preorder(行きかけ順）のときと違って、ノードを収めたスタックだけをみて縦の枝を表現する方法は思いつきませんでした。
python22.py
┌─A
┌─B
│ └─C
┌─D
│ │ ┌─E
│ └─F
┌─G
│ │ ┌─H
│ │ ┌─I
│ │ │ └─J
│ └─K
│ │ ┌─L
│ └─M
N
│ ┌─O
│ ┌─P
│ │ └─Q
│ ┌─R
│ │ │ ┌─S
│ │ └─T
└─U
│ ┌─V
│ ┌─W
└─X
│ ┌─Y
└─Z
これは値のないノードの行は出力しないバージョンです。
if node.label:を31行目から16行目に移動させただけです。
参考にしたサイト
Data Structures Notes: Binary tree traversal: Preorder, Inorder, and Postorder
preorder(行きかけ順）やinorder（通りがけ順）、postorder（帰りがけ順）の比較がわかりやすいです。
複数のフラグ(真偽値)を1つの整数値として扱う上でのメモ - 試験運用中なLinux備忘録
二進数の扱いが具体的に解説してありわかりやすいです。
0 件のコメント:
コメントを投稿