关于Python二叉树的问题

链式存储二叉树构建，完成查找 求树高度 中序遍历 先遍历 后序遍历 层序遍历 并用相关数据进行测试。给出算法的时间和空间复杂度

可以参考

很详细

from collections import deque


class BiTreeNode:
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None

# ABCDE#F##G#####

class CreateBiTree:
    """
    str_tree: 传入字符串
    return: 返回根结点
    """
    def __init__(self, str_tree):
        self.str_tree = str_tree

    def create_tree(self):
        l1 = list(self.str_tree)
        l1 = [None if i == '#' else i for i in l1]
        nodes = [BiTreeNode(l1[i]) for i in range(len(l1))]
        root = nodes[0]
        for i in range(len(l1)):
            if 2*i+2 > len(l1):
                break
            cur_node = nodes[i]
            if nodes[2*i+1].data:
                cur_node.lchild = nodes[2*i+1]
            if nodes[2*i+2].data:
                cur_node.rchild = nodes[2*i+2]
        return root

    def __call__(self):
        return self.create_tree()

class BiTreeSorted:
    def __init__(self, root):
        self.root = root

    def pre_order(self, root):
        # 前序排列
        if root:
            print(root.data, end=',')
            self.pre_order(root.lchild)
            self.pre_order(root.rchild)

    def in_order(self, root):
        # 中序排列
        if root:
            self.in_order(root.lchild)
            print(root.data, end=',')
            self.in_order(root.rchild)


    def post_order(self, root):
        # 后序排列
        if root:
            self.post_order(root.lchild)
            self.post_order(root.rchild)
            print(root.data, end=',')

    def level_order(self, root):
        # 层序排列
        queue = deque()
        queue.append(root)
        while len(queue) > 0:
            node = queue.popleft()
            print(node.data, end=',')
            if node.lchild:
                queue.append(node.lchild)
            if node.rchild:
                queue.append(node.rchild)

    def __call__(self):
        print('前序排列')
        self.pre_order(self.root)
        print()

        print('中序排列')
        self.in_order(self.root)
        print()

        print('后序遍历')
        self.post_order(self.root)
        print()

        print('层序遍历')
        self.level_order(self.root)
        print()

a = CreateBiTree('ABCDE#F##G#####')
root = a()
print('根结点为：', root.data)
sorted = BiTreeSorted(root)
sorted() # 调用__call__方法