一、概念
二叉搜索树（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树的中序遍历一定是顺序的，记住这不是巧合就行