前の関連記事：Python(20)MSDOSのtreeコマンドのように枝も出力する:いまいち編
ノードインスタンスとその階層を別のリストで扱うようにして解決
python21.py
これでtree_repr()のwhile文を3つから1つにできました。
19行目と25行目で同じ階層のノードがスタックにあるときにそのノードの値が空文字でないかどうかを判定しています。
if i in lst_level and stack[lst_level.index(i)].label: # 値があるノードが同じ階層にスタックにあるとき。i in lst_levelがFalseのとき、iはlst_levelの要素にないので、lst_level.index(i)はエラーになるのですが、andで結ばれているとandの前がFalseだとandの後ろは計算されないようです。
なのでエラーにならずに済みます。
tree()で二分木をリストから生成するときに、左右のどちらかの枝につながるノードがあるときはノードない方の枝にNoneをいれずに、62行目で空文字""を値をもつノードインスタンスにしているために、子ノードがない枝の部分は空白で出力しています。
N
├─G
│ ├─D
│ │ ├─B
│ │ │ ├─A
│ │ │ └─C
│ │ └─F
│ │ └─E
│ │
│ └─K
│ ├─I
│ │ ├─H
│ │ └─J
│ └─M
│ └─L
│
└─U
├─R
│ ├─P
│ │ ├─O
│ │ └─Q
│ └─T
│ └─S
│
└─X
├─W
│ └─V
│
└─Z
└─Y
E, L, S, V, Yの次に1行空いているのはそのためです。
この空行を出力させないようにするにはnode.labeｌが空文字のときを除外すればよいです。
python21.py
24行目にあったif node.label:を16行目のif node:と一緒にしました。
このif node and node.label:をif node.label and node:と逆にするとnodeがNoneのときにnode.labelがないためにエラーになります。
N
├─G
│ ├─D
│ │ ├─B
│ │ │ ├─A
│ │ │ └─C
│ │ └─F
│ │ └─E
│ └─K
│ ├─I
│ │ ├─H
│ │ └─J
│ └─M
│ └─L
└─U
├─R
│ ├─P
│ │ ├─O
│ │ └─Q
│ └─T
│ └─S
└─X
├─W
│ └─V
└─Z
└─Y
これで空白の行がなくなりましたね。
多次元リストの要素を1行で検索する方法はない？
最初はノードインスタンスを入れているスタックと階層を入れているリストを一つにまとめて２次元のリストをスタックにしようと思っていたのですが２次元リストのリストのリストの要素のスマートな検索方法がわからないのですよね。
Pythonコード研究所 配列(リスト)を検索する
どうも２次元リストの要素のリストをfor文で取り出してその要素を調べるという方法しかないようです。
19行目と24行目で階層のリストをinで検索しているのですが、for文で取り出して評価するとなると一文では収まりそうにないですね。
リストから二分木を生成するtree()ではノードインスタンスとその階層を1つのリストで扱う
Python(18)リストから二分木を生成するで作ったtree()ですが、あとでバグに気づいて修正したのでやっつけ仕事になっています。
これはリストの要素を検索する部分がないのでノードインスタンスをいれるスタックとその階層を入れるリストを一つのスタックにまとめてしまいます。
まずはtree()の中のwhile文の前で無駄な場合わけをしていたのでそれを削除しました。
python21.py
そしてノードの値のリストと生成したノードを入れるリストをそれぞれの階層をつけて2次元配列にしてみました。
python21.py
コードは短くなりましたが何をしているのかはわかりにくくなりましたね。
参考にしたサイト
Pythonコード研究所 配列(リスト)を検索する
2次元リストの要素の検索仕方はfor文で入れ子のリストを取り出してやるしかないようです。
Data Structures Notes: Binary tree traversal: Preorder, Inorder, and Postorder
preorder(行きかけ順）やinorder（通りがけ順）、postorder（帰りがけ順）の比較がわかりやすいです。
0 件のコメント:
コメントを投稿