python18.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, level=0, indent="    "):  # repr(このクラスのインスタンス)で呼び出されたときに文字列を返す特殊メソッド。repr(ノード)でそのノードから葉まで出力する。levelは木の階層（根を0階層とする）、indentは出力するときのインデント。
        s = level*indent + repr(self.label)  # ノードの値を階層に応じたインデントをつけて出力する。sが出力する文字列になる。
        if self.left:  # 左の枝につながるノードがあるとき。
            s = s + "\n" + self.left.__repr__(level+1, indent)  # 左の枝につながるノードについて階層を一つ加えて出力する。
        if self.right:  # 右の枝につながるノードがあるとき。
            s = s + "\n" + self.right.__repr__(level+1, indent)  # 右の枝につながるノードについて階層を一つ加えて出力する。
        return s  # repr(ノード)のノードについてpreorder(行きかけ順）(出力、左の枝、右の枝の順に処理したから）にそのノードから葉まで出力することになる。
def tree(list):  # 引数のリストから二分木を作成する関数。
    if list:
        i = len(list) // 2  # リストのi番目の要素を値にもつノードを生成する。
        label = list[i]  # i番目の要素をノードの値にする。
        lst1 = list[:i]  # リストの先頭のi個の要素のリストを取得。
        lst2 = list[i+1:]  # リストのi+1番目以降の要素のリストを取得。
        list = lst1
        left = tree(list)  # lst1のリストからノードの左の枝につながるノードを生成する。
        list = lst2
        right = tree(list)  # lst2のリストからノードの右の枝につながるノードを生成する。
        return Tree(label, left, right)  # 値がlabel、左の枝にleft、右の枝にrightのノード(あるいはNone)をもつノードインスタンスを生成。
t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ")  # 引数のリストから二分木を生成してその根をtに取得。
print(repr(t))  # 根tについてpreorder(行きかけ順）に出力。