python20.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, level=0, indent="    "):  # 二分木を枝付きで出力。
    #  まず根tから各ノードをたどって各ノードの値とその階層をそれぞれのリストにpostorder(帰りがけ順)に得る。
    stack = [t, level]  # 初期値のノードインスタンスとその階層をにスタックに入れる。
    lst_n = []  # ノードの値をいれるリスト。
    lst_lev = []  # ノードの階層をいれるリスト。
    while stack:  # スタックがあるあいだ続行。
        node, level = stack[-2:]  # スタックからノードインスタンスと階層を得る。
        if node.left:  # 左の枝があるとき。
            lst_n.append(node.label)  # 左の枝につながるノードの値をlst_nに取得。
            lst_lev.append(level)  # lst_nに取得したノードの階層を得る。
            stack.extend([node.left, level + 1])  # 左の枝のノードインスタンスとその階層をスタックに追加する。
            node.left = None  # 使用後の左の枝を消去。
        elif node.right:  # 右の枝があるとき。
            del stack[-2:]  # もうこのノードインスタンスは使わないのでスタックから削除。
            stack.extend([node.right, level + 1])  # 右の枝のノードインスタンスとその階層をスタックに追加する。
        else:  # 左右の枝がないとき。
            lst_n.append(node.label)  # このノードの値をlst_nに取得。
            lst_lev.append(level)  # lst_nに取得したノードの階層を得る。
            del stack[-2:]  # このノードインスタンスをスタックから消去。
    # print(lst_n)  # postorder(帰りがけ順)に得たリストを確認する。
    # 木構造の枝を取得。枝葉出力順と逆に取得するのでまだ出力せずstackに枝とノードの値を取得する。
    b = 0  # 枝が存在する階層情報を保持する二進数を入れる変数。
    while lst_n:  # ノードがlst_nにある間続行。
        branch = ""  # 枝をいれる変数を初期化。
        node = lst_n.pop()  # ノードを得る。
        level = lst_lev.pop()  # nodeの階層を得る。
        if node:  # ノードの値があるとき。
            if level > 0:  # 階層が1以上のとき。
                bb = b  # 前のノードの枝情報をbbにとっておく。
                b |= 2 ** (level - 1)  # ノードの枝がある階層に対応する桁を1にする。
                b &= 2 ** level - 1  # 1にした桁より大きい桁の値をすべて0にする。ノードより後ろには枝葉存在しないため。
                if level > 1:  # 階層が2以上のときは縦の枝があるのでその情報を取得する。
                    for i in range(level - 1):  # ノードの枝がある階層の手前までbの値を調べる。二進数でイテレータを生成する方法がわからず。
                        if b & (2 ** i):  # 二進数で1の桁があるとき。
                            branch += "│  "  # 縦の枝を取得。
                        else:
                            branch += indent  # 縦の枝がないときはインデント。
                if bb & (2 ** (level - 1)):  # ノードからでた枝について、下から生えてきた枝があるかどうかで場合わけ。
                    branch += "├─"  # 下から生えてきた枝があるとき。
                else:
                    branch += "└─"  # 下から生えてきた枝がないとき。
        else:  # ノードがないときは縦の枝を取得。
            for i in range(level):
                if b & (2 ** i):
                    branch += "│  "
                else:
                    branch += indent
        stack.append(branch + node)  # スタックに枝とノードを各行について取得。
    while stack:  # スタックの情報を出力。
        print(stack.pop())
def tree(lst):  # 引数のリストから二分木を作成する関数。
    node = list()  # ノードインスタンスを収納するスタック。
    node_level = list()  # ノードインスタンスの二分木での階層を保存するスタック。
    if len(lst) > 3:
        i = len(lst) // 2  # ノードの値にする要素番号を取得。
        stack = [lst[i], lst[i+1:], lst[:i]]  # スタックに初期値を入力。初期値; ノードの値、左のノードとなる値のリスト、右のノードとなる値のリスト。
        level = [0, 1, 1]  # stackの要素のリスとの二分木での階層を保存するスタック。
    else:  # リストの要素が3個以下のときはまとめて処理する。
        stack = [lst]
        level = [0]
    while stack:  # ノードの値となる要素をもったリストがある間。
        lst = stack.pop()  # リストを取り出す。
        if len(lst) > 3:  # リストの要素が3以上あるとき。
            i = len(lst) // 2  # ノードの値にする要素番号を取得。
            stack.extend([lst[i], lst[i+1:], lst[:i]])  # ノードの値、左のノードとなる値のリスト、右のノードとなる値のリスト,をスタックに新たに追加。
            n = level[-1]+1  # 階層を1つ加えるて、階層スタックに追加する。
            level.extend([n, n])
        elif len(lst) == 1:  # リストの要素が一つだけのとき。
            if len(node_level) > 1 and node_level[-1] == node_level[-2]:  # ノードインスタンスが複数あり、かつ階層が同一のとき。
                    left = node.pop()  # 左の枝につながるノードを得る。
                    right = node.pop()  # 右の枝につながるノードを得る。
                    node.append(Tree(lst[0], right, left))  # リストの要素を値とするノードインスタンスを生成して、ノードインスタンス用のスタックに追加。
                    node_level.pop()  # ノードを二つ消費したのでノードの階層のスタックの要素を一つ破棄。
                    node_level[-1] -= 1  # 新たに生成したノードインスタンスの階層を設定。ノードを結合したノードの階層は一つ根に近づく。
                    level.pop()  # リストのスタックも要素を一つ消費したので階層のスタックを一つ破棄する。
            else:  # ノードインスタンスがないときは枝のないノードにする。
                node.append(Tree(lst[0]))
                node_level.append(level.pop())  # リストの階層からノードの階層を取得。
        elif lst:  # リストの要素が2個か3個のときはすべてノードにしてしまう。
            i = len(lst) // 2  # ノードの値にする要素番号を取得。
            node.append(Tree(lst[i], Tree(lst[:i]), Tree(lst[i+1:])))  # i番目の要素をノードの値、i-1番目の要素を右のノードの値、i+1番目の要素の値を左のノードの値にする。左右のノードより深い階層のノードは存在しない。
            node_level.append(level.pop())  # リストの階層からノードの階層を取得。
    return node[0]  # 最後にスタックに残ったノードが根となるのでそれを返す。
t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ")  # 引数のリストから二分木を生成してその根をtに取得。
tree_repr(t)  # 根tについてpreorder(行きかけ順)に出力。