python23.py

#  -*- 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のノードインスタンスに対応する階層を入れるリスト。
    b = 0
    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:  # 右の枝にも左の枝にもノードがないとき。
            branch = ""  # 枝をリセット。
            if level > 1:  # 2階層以上のとき。
                for i in range(level - 1):  # 2つ下の階層まで二進数の各桁を調べる。
                    if b & (2 ** i):  # 二進数の桁が1のとき。
                        branch += "│  "  # 縦枝を加える。
                    else:
                        branch += indent
            if level > 0:  # 1階層より上のとき
                if node.label:  # ノードの値があるとき
                    if b & 2 ** (level - 1):  # 上の行に同じ階層のノードがあるとき。
                        branch += "├─"
                    else:
                        branch += "┌─"
                elif b & 2 ** (level - 1):  #　ノードの値がなく、かつ、上の行に同じ階層のノードがあるとき。
                    branch += "│  "  # 縦枝を追加。
            print(branch + node.label)  # ノードの値とともに枝を出力。
            if level > 0:  # 根以外のとき。
                b |= 2 ** (level - 1)  # ノードに続く枝の階層の二進数の桁を1にする。
                b &= 2 ** level - 1  # 追加した桁より上の桁はすべて0にする。ノードより上の階層には枝が存在しないので。
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について枝付きで出力。