[数据结构与算法]关于二叉搜索树的操作

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：
1.若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2.若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3.它的左、右子树也分别为二叉排序树。

代码实现：

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 = BiTreeNode(val)
        elif val < node.data:
            node.lchild = self.insert(node.lchild,val)
            node.lchild.parent = node
        elif val>node.data:
            node.rchild = self.insert(node.rchild,val)
            node.rchild.parent = node
        return node
    def insert_no_rec(self,val):     #非递归的写法
        p = self.root
        if not p:     #特殊处理空树的情况
            self.root = BiTreeNode(val)
            return
        while True:
            if val < p.data:
                if p.lchild:
                    p = p.lchild
                else:
                    p.lchild = BiTreeNode(val)
                    p.lchild.parent = p
                    return
            elif val >p.data:
                if p.rchild:
                    p = p.rchild
                else:
                    p.rchild =BiTreeNode(val)
                    p.rchild.parent = p
                    return
            else:
                return

    def pre_order(self,root):  # 前序遍历(E,A,C,B,D,G,F,)迭代的思想
        if root:
            print(root.data, end=',')
            self.pre_order(root.lchild)
            self.pre_order(root.rchild)

    # pre_order(root)
    def in_order(self,root):  # 中序遍历(A,B,C,D,E,G,F,)
        if root:
            self.in_order(root.lchild)
            print(root.data, end=',')
            self.in_order(root.rchild)

    # in_order(root)
    def post_order(self,root):  # 后序遍历（B,D,C,A,F,G,E,）
        if root:
            self.post_order(root.lchild)
            self.post_order(root.rchild)
            print(root.data, end=',')

tree = BST([4,6,7,9,2,1,3,5,8])
tree.pre_order(tree.root)
print("")
tree.in_order(tree.root)
print("")
tree.post_order(tree.root)
import random
li = list(range(20))
random.shuffle(li)
print("")
print(li)
print("中序遍历")
tree.in_order(tree.root)