一、概念

二叉搜索树（Binary Search Tree）是一颗二叉树且满足性质：设x是二叉树的一个节点。如果y树x左子树的一个节点，那么；如果y是x右子树的一个节点，那么。

用通俗一点的话来说就是在一棵二叉树中，左子树所有节点都比它的根节点小，右子树所有节点都比它的根节点大。（如图所示）

所以当我们要定义一个BST树时，用双链表来做就要想到要初始化的东西：

1. 数据域data 0

2. 树的左孩子和右孩子（lchild/rchild） 

3. 他们的双亲parent

定义BST树代码如下：

class BSTreeNode:
    def __init__(self):
        self.data=data
        self.lchild=None    #左孩子
        self.rchild=None     #右孩子
        self.parent=None

 二、搜索二叉树的插入

递归插入代码思路：

1. 判断当前节点是否为空，是的话就直接插入结点

2. 如果当前节点不为空，则有三种判断

当前节点大于插入的结点，插入的结点应放在当前结点的左边

当前节点小于插入的结点，插入的结点应放在当前节点的右边

当前节点等于插入的结点，这个代码可以不执行，可以不写，如果想优化代码可以写如果当前及诶点等于插入的结点会怎样怎样

3. 最后别忘了绑定要插入的结点的双亲

代码如下：

# 递归插入函数 node结点位置 val为要插入的结点
def insert(self, node, val):
    # 如果node是空，有空间，可直接插入结点
    if not node:
        node = BSTreeNode(val)
    # 如果node不为空则有两种判断 插入的结点值小于（大于）node结点值
    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
        # 其实这里还有一个else val=node.data ， 这个默认我们找到了就不找了，所以不做什么回应
        # 如果想优化代码可以写上else
    return node

非递归插入代码思路如下：

1. 定义一个变量来保存这棵树的根

2. 判断该树是否为空，判断方法为判断根是否存在，如果是空，直接将要插入的结点插入根节点

3. 不是空树，则有三种判断

当前节点大于根节点，插入的结点应放在根节点的左边，所以要判断根节点有没有左子树，有左子树的话就再找它的左子树的下一个左子树，直到找到空节点进行插入

当前节点小于根节点，插入的结点应放在根节点的右边，所以要判断根节点有没有右子树，有右子树的话就再找它的右子树的下一个右子树，直到找到空节点进行插入

当前节点等于插入的结点，代码可以不写，也可以写，这里不写

代码如下：

def insert_not_rec(self,val):
    p=self.root
    #如果树是空树
    if not p:
        self.root=BSTreeNode(val)
        return
    #递归函数中因为直接判断是空树就直接返回了，不用特殊处理，但是这里需要特殊处理，因为这里不是递归
    # 如果不是空树：
    while True:
        if val<p.data:
            # 判断左子树是否为空，是空就直接插入，不是空就往下一个左子树找空间
            if p.lchild:  #如果存在左子树，左子树不为空
                p=p.lchild
            else:
                p.lchild=BSTreeNode(val)
                p.lchild.parent=p
                return
        elif val>p.data:
            if p.rchild: #如果存在右子树，右子树不为空
                p=p.rchild
            else:
                p.rchild=BSTreeNode(val)
                p.rchild.parent=p
                return
        else: #如果val=p.data
            return

总体代码如下：

因为递归执行效率较慢，所以改代码使用非递归执行，因为再创建了另一个类，所以需要初始化一下树的根

class BSTreeNode:
    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_not_rec(val)

    # 递归插入函数 node结点位置 val为要插入的结点
    def insert(self, node, val):
        # 如果node是空，有空间，可直接插入结点
        if not node:
            node = BSTreeNode(val)
        # 如果node不为空则有两种判断 插入的结点值小于（大于）node结点值
        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
        # 其实这里还有一个else val=node.data ， 这个默认我们找到了就不找了，所以不做什么回应
        # 如果想优化代码可以写上else
        return node

    # 非递归插入函数 参数只需要一个插入的结点
    def insert_not_rec(self,val):
        p=self.root
        #如果树是空树
        if not p:
            self.root=BSTreeNode(val)
            return
            #递归函数中因为直接判断是空树就直接返回了，不用特殊处理，但是这里需要特殊处理，因为这里不是递归
        # 如果不是空树：
        while True:
            if val<p.data:
                # 判断左子树是否为空，是空就直接插入，不是空就往下一个左子树找空间
                if p.lchild:  #如果存在左子树，左子树不为空
                    p=p.lchild
                else:
                    p.lchild=BSTreeNode(val)
                    p.lchild.parent=p
                    return
            elif val>p.data:
                if p.rchild: #如果存在右子树，右子树不为空
                    p=p.rchild
                else:
                    p.rchild=BSTreeNode(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=",")

tree=BST([4,6,7,9,2,1,3,5,8])
tree.pre_order(tree.root)
print("")
tree.in_order(tree.root)
print("")
tree.pre_order(tree.root)

结果输出为：

4,2,1,3,6,5,7,9,8,
1,2,3,4,5,6,7,8,9,
4,2,1,3,6,5,7,9,8,

可以看出，BST树的中序遍历一定是顺序的，记住这不是巧合就行