from collections import deque

# 树节点类
class Node:
    def __init__(self, value):
        self.value = value
        self.lchild = None
        self.rchild = None


# 二叉树类
class BinaryTree:
    # 初始化属性
    def __init__(self, node = None):
        self.root = node

    def is_empty(self):
        return self.root is None

    # 添加节点
    def add(self, value):
        # 创建新节点
        new_node = Node(value)
        # 判空
        if self.is_empty():
            self.root = new_node
            return
        # 非空
        queue = deque([self.root])
        while queue:
            cur = queue.popleft()
            # 左子树
            if cur.lchild is None:
                cur.lchild = new_node
                return
           
            queue.append(cur.lchild)
            # 右子树
            if cur.rchild is None:
                cur.rchild = new_node
                return
            queue.append(cur.rchild)
            

    # 广度优先遍历
    def breadth_traversal(self):
        # 判空
        if self.is_empty():
            return []
        # 非空
        res = []
        queue = deque([self.root])
        while queue:
            cur = queue.popleft()
            res.append(cur.value)
            # 左子树
            if cur.lchild:
                queue.append(cur.lchild)
            # 右子树
            if cur.rchild:
                queue.append(cur.rchild)
        return res


    # 深度优先遍历
    # 前序 根左右
    def pre_order_traversal(self):
        res = []
        def dfs(node):
            if node:
                res.append(node.value)
                dfs(node.lchild)
                dfs(node.rchild)
        dfs(self.root)
        return res


    # 中序 左根右
    def in_order_traversal(self):
        res = []
        def dfs(node):
            if node:
                dfs(node.lchild)
                res.append(node.value)
                dfs(node.rchild)
        dfs(self.root)
        return res

    # 后序 左右根
    def post_order_traversal(self):
        res = []
        def dfs(node):
            if node:
                dfs(node.lchild)
                dfs(node.rchild)
                res.append(node.value)
        dfs(self.root)
        return res


if __name__ == "__main__":
    # 测试广度优先
    my_binary_tree = BinaryTree()
    test_binary = [chr(c) for c in range(ord('A'), ord('J') + 1)]
    for c in test_binary:
        my_binary_tree.add(c)
    print('->'.join(map(str, my_binary_tree.breadth_traversal())))

    # 测试深度优先
    my_binary_tree2 = BinaryTree()
    test_binary2 = [i for i in range(0, 10)]
    for i in test_binary2:
        my_binary_tree2.add(i)
    root_l_r = my_binary_tree2.pre_order_traversal()
    l_root_r = my_binary_tree2.in_order_traversal()
    r_l_root = my_binary_tree2.post_order_traversal()
    print('->'.join(map(str, root_l_r)))
    print('->'.join(map(str, l_root_r)))
    print('->'.join(map(str, r_l_root)))