-
-
Save p--q/e9ecf13d30ebeec650b6 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を入れる。preorder(行きかけ順)に取得する。 | |
lst_level = [0] # stackのノードインスタンスに対応する階層を入れるリスト。 | |
while stack: # ノードインスタンスがある間実行。 | |
node = stack.pop() # ノードインスタンスを取得。 | |
level = lst_level.pop() # ノードインスタンスの階層を取得。 | |
branch = "" # このノードインスタンスの枝を入れる変数をクリア。 | |
if node: # ノードインスタンスがあり、かつ、ノードの値があるとき。 | |
if level > 1: # 階層が2以上のときのみ。 | |
for i in range(1, level): # 1階層から一つしたの階層までについて。 | |
if i in lst_level and stack[lst_level.index(i)].label: # 値があるノードが同じ階層にスタックにあるとき。 | |
branch += "│ " # 縦枝を取得。 | |
else: # 同じ階層のノードインスタンスがスタックにないとき。 | |
branch += indent # 枝なし空白を取得。 | |
if level > 0: # 1階層以上のときのみ。 | |
if node.label: | |
if level in lst_level and stack[lst_level.index(level)].label: # 値があるノードが同じ階層にスタックにあるとき。 | |
branch += "├─" # 同じ階層に続く枝を取得。 | |
else: | |
branch += "└─" # この階層で終わる枝を取得。 | |
print(branch + node.label) # 枝とノードの値を出力。 | |
stack.extend([node.right, node.left]) # 次の階層のノードインスタンスをスタックに取得。 | |
lst_level.extend([level + 1, level + 1]) # スタックに追加したノードインスタンスの階層を取得。 | |
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についてpreorder(行きかけ順)に出力。 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment