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


class BST:
    def __init__(self, li=None):
        self.root = None
        if li:
            for val in li:
                self.insert_no`在这里插入代码片`_rec(val)  # 调用非递归的插入方法

    # 插入(递归写法)
    def insert(self, node, val):  #
        if not node:  # 如果node为空（如果是空树）
            node = BiTreeNode(val)  # 则新建一个node
        elif val < node.data:  # 如果传入的node不为空，如果传入的val小于node的data
            node.lchild = self.insert(node.lchild, val)  # node的左孩子等于递归插入node的左孩子和val
            node.lchild.parent = node  # node节点的左孩子的父节点为node
        elif val > node.data:  # 如果传入的val大于node的data
            node.rchild = self.insert(node.rchild, val)
            node.rchild.parent = node
        # 如果val与要插入的节点相等，则什么也不做
        return node

    # 非递归写法
    def insert_no_rec(self, val):  # 传入一个要插入的值
        p = self.root  # 定义一个节点，为根节点p
        if not p:  # 如果p(self.root)为空
            self.root = BiTreeNode(val)  # 给self.roo传入值val
            return  # 结束
        while True:  # 进行循环
            if val < p.data:  # 如果要插入的val小于p节点的data
                if p.lchild:  # 如果p有左孩子
                    p = p.lchild  # 把p的左孩子赋值给p
                else:  # 如果p的左孩子不存在
                    p.lchild = BiTreeNode(val)  # 新建一个节点把它赋值给p的左孩子
                    p.lchild.parent = p  # 双向指向
                    return  # 结束
            elif val > p.data: # 如果要插入的val大于p节点的data
                if p.rchild:
                    p = p.rchild
                else:
                    p.rchild = BiTreeNode(val)
                    p.rchild.parent = p
                    return
            else:  # 如果val == p.data
                return

    # 前序遍历
    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=',')

import random
li = list(range(10))
random.shuffle(li)
tree = BST(li)
tree.pre_order(tree.root)  # 传入类实例的root属性，空的根节点
print('')  # 5,3,0,1,2,4,8,7,6,9,
tree.in_order(tree.root)  # 因为二叉搜索树的节点值大小顺序为：左孩子<父节点<右孩子
print('')  # 0,1,2,3,4,5,6,7,8,9,  所以二叉搜索树的中序遍历是有序的
tree.post_order(tree.root)
print('')  # 2,1,0,4,3,6,7,9,8,5,