-
-
Save p--q/fcfd47ca61c9dabd8787 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# -*- coding: utf-8 -*- | |
class Tree: # これのインスタンスが二分木のノードとなる。 | |
def __init__(self, label, left=None, right=None): # インスタンス化のときの第一引数をノードの値に、第二引数を左の枝につながるノードに、第3引数を右の枝につながるノードにする。 | |
self.label = label # ノードの値を設定。 | |
self.left = left # 左の枝につながるノードを設定。 | |
self.right = right # 右の枝につながるノードを設定。 | |
def __repr__(self): # repr(このクラスのインスタンス)で呼び出されたときに文字列を返す特殊メソッド。デバッグ画面でもこの戻り値が表示されるのでデバッグ用。 | |
return self.label # ノードの値のみ出力する。 | |
def tree_repr(t, indent=" "): # 根tの二分木を枝付きで出力。 | |
stack = [t] # ノードインスタンスをいれるスタックにまず根tを入れる。postorder(帰りがけ順)に取得する。 | |
lst_level = [0] # stackのノードインスタンスに対応する階層を入れるリスト。 | |
lst_d_level = list() # 枝につなげっている出力済みノードの階層をいれるリスト。 | |
while stack: # ノードインスタンスがある間実行。 | |
node = stack.pop() # ノードインスタンスを取得。 | |
level = lst_level.pop() # ノードインスタンスの階層を取得。 | |
while node.left: # 左の枝につながるノードがあるとき。 | |
n_node = node.left # 次のノードとして左の枝につながるノードを取得。 | |
node.left = None # 使用したノードは消す。 | |
stack.append(node) # 左の枝につながるノードを消した状態でスタックに取得。 | |
lst_level.append(level) # スタックに取得したノードに対応する階層を取得。 | |
node = n_node # 次のノードを設定。 | |
level += 1 # 子ノードなので階層を一つ増やす。 | |
if node.right: # 右の枝につながるノードをあるとき。 | |
n_node = node.right # 右の枝につながるノードを取得。 | |
node.right = None # 使用したノードは消す。 | |
stack.extend([node, n_node]) | |
lst_level.extend([level, level + 1]) | |
elif not node.left: # 右の枝にも左の枝にもノードがないとき。 | |
if node.label: | |
branch = "" # 枝をリセット。 | |
if level > 1: # ノードの階層が2以上のとき。 | |
for i in range(1, level): # 階層iにあるノードから出た枝が次行の階層i-1の枝になる。 | |
if i in lst_d_level: # iは枝の階層ではなく、枝のより上の行にあるその枝がでたノードの階層になる。 | |
branch += "│ " # 縦枝を加える。 | |
else: | |
branch += indent | |
if level > 0: # ノードの階層が1以上のとき | |
if level in lst_d_level: # 既に同じ階層のノードが出力してあった場合。 | |
branch += "├─" | |
del lst_d_level[lst_d_level.index(level):] # このノード以上の階層のノードの階層をlst_d_indexから削除する。 | |
else: | |
branch += "┌─" | |
if level + 1 in lst_d_level: # この階層より上の階層が出力リストにあるとき。 | |
del lst_d_level[lst_d_level.index(level + 1):] # このノードより上の階層のノードの階層をlst_d_indexから削除する。 | |
lst_d_level.append(level) # 出力したノードの階層をリストに追加する。 | |
print(node.label + indent + branch + node.label) # ノードの値とともに枝を出力。 | |
def tree(lst): # 引数のリストから二分木を作成する関数。 | |
node = list() # [ノードインスタンス, 階層]のリストを要素とするリスト。 | |
stack = [[lst, 0]] # [ノードの値のリスト, 階層]のリストを要素とするスタック。 | |
while stack: # ノードの値となる要素をもったリストがある間。 | |
lst, level = stack.pop() # リストと階層を取り出す。 | |
if len(lst) > 3: # リストの要素が3以上あるとき。 | |
i = len(lst) // 2 # ノードの値にする要素番号を取得。 | |
stack.extend([[lst[i], level], [lst[i+1:], level + 1], [lst[:i], level + 1]]) # ノードの値、左のノードとなる値のリスト、右のノードとなる値のリスト,をスタックに新たに追加。 | |
elif len(lst) == 1: # リストの要素が一つだけのとき。 | |
if len(node) > 1 and node[-2][1] == node[-1][1]: # ノードインスタンスが複数あり、かつ階層が同一のとき。 | |
left = node.pop()[0] # 左の枝につながるノードを得る。 | |
right = node.pop()[0] # 右の枝につながるノードを得る。 | |
node.append([Tree(lst[0], right, left), level]) # リストの要素を値とするノードインスタンスを生成して、ノードインスタンス用のスタックに追加。 | |
else: # ノードインスタンスがないときは枝のないノードにする。 | |
node.append([Tree(lst[0]), level]) | |
elif lst: # リストの要素が2個か3個のときはすべてノードにしてしまう。 | |
i = len(lst) // 2 # ノードの値にする要素番号を取得。 | |
node.append([Tree(lst[i], Tree(lst[:i]), Tree(lst[i+1:])), level]) # i番目の要素をノードの値、i-1番目の要素を右のノードの値、i+1番目の要素の値を左のノードの値にする。左右のノードより深い階層のノードは存在しない。 | |
return node[0][0] # 最後にスタックに残ったノードが根となるのでそれを返す。 | |
t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ") # 引数のリストから二分木を生成してその根をtに取得。 | |
tree_repr(t) # 根tについて枝付きで出力。 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment