#列表函数
def BinaryTree(r):
    return [r, [], []]

#插入左子树
def insertLeft(root, newBranch):
    t = root.pop(1)
    if len(t) > 1:
        root.insert(1, [newBranch, t, []])
    else:
        root.insert(1, [newBranch, [], []])
    return root

#插入右子树
def insertRight(root, newBranch):
    t = root.pop(2)
    if len(t) > 1:
        root.insert(2, [newBranch, [], t])
    else:
        root.insert(2, [newBranch, [], []])
    return root

#树的访问函数
def getRootVal(root):
    return root[0]

def setRootVal(root, newval):
    root[0] = newval

def getLeftChild(root):
    return root[1]

def getRightChild(root):
    return root[2]


# 二叉树的访问函数
def getLeftChild(self):
    return self.leftChild

def getRightChild(self):
    return self.rightChild

def setRootValue(self, obj):
    self.key = obj

def getRootValue(self):
    return self.key


# 定义节点
class BinaryTree:
    def __init__(self, rootObj):
        self.key = rootObj
        self.leftChild = None    # 左子节点也是树
        self.rightChild = None    # 右子节点也是树

# 插入左子节点
def insertLeft(self, newNode):
    if self.leftChild == None:
        self.leftChild = newNode
    else:
        t = BinaryTree(newNode)
        t.leftChild = self.leftChild
        self.leftChild = t

# 插入右子节点
def insertRight(self, newNode):
    if self.rightChild == None:
        self.rightChild = newNode
    else:
        t = BinaryTree(newNode)
        t.rightChild = self.rightChild
        self.rightChild = t

# 树的遍历

# 前序
def preorder(tree):
    if tree:
        print(tree.getRootVal())
        preorder(tree.getLeftChild())
        preorder(tree.getRightChild())

# 中序
def inorder(tree):
    if tree:
        inorder(tree.getLeftChild())
        print(tree.getRootVal())
        inorder(tree.getRightChild())

# 后序
def postorder(tree):
    if tree:
        postorder(tree.getLeftChild())
        postorder(tree.getRightChild())
        print(tree.getRootVal())

# 树
# class Bnode(object):
#     def __init__(self, data, left=None, right=None):
#         self.data = data
#         self.left = left
#         self.right = right
#
# class Btree(object):
#     def __init__(self, root=None):
#         self.root = root
#
#     @classmethod
#     def bulid(cls, list):
#         node_dict = {}
#         # 制作节点
#         for item in list:
#             data = item['data']
#             node_dict[data] = Bnode(data)
#         # 把节点组装成数
#         for item in list:
#             data = item['data']
#             node = node_dict[data]
#             if node['is_root']:
#                 root = node
#             node.left = node_dict.get(item['left'])
#             node.right = node_dict.get(item['right'])
#         return cls(root)
#
#     def preorder(self, subtree):
#         # 先序
#         if subtree is not None:
#             print(subtree.data)
#             self.preorder(subtree.left)
#             self.preorder(subtree.right)
#
#     def reverse(self, subtree):
#         # 后序
#         if subtree is not None:
#             subtree.left, subtree.right = subtree.right, subtree.left
#             self.reverse(self, subtree.left)
#             self.reverse(self, subtree.right)

# 回溯通用模板
# res = []
#
# def backtrack(路径, 选择列表):
#     if 满足结束条件:
#         res.append(路径)
#         return
#
#     if 满足剪枝条件： return
#
#     for 选择 in 选择列表:
#         做选择
#         backtrack(路径, 选择列表)
#         撤销选择