数据结构-----二叉搜索树

二叉搜索树是一种搜索树，通常的二分搜素算法有很好的搜索性能但是一般在顺序表上进行，插入和删除元素比较费时。而通过采用树型结构，能够有效的支持插入和删除，同时保证查找的效率。（很多内容摘自数据结构---陈慧南编写的书上）

一，二叉搜索树

1）二叉搜索树的定义

假定所有结点的关键字值各不相同，二叉搜索树或者是一个空二叉树，或者是具有下列性质的二叉树：

若左子树不空，则左子树上的所有结点的关键字值小于根节点的关键字值；若右子树不空，则右子树上所有节点的关键字值均大于根结点的关键字值；左右子树也分别是二叉搜索树。

2）二叉搜索树的性质

若以中序遍历一个二叉搜索树，将得到一个以关键字递增排列的有序序列

3）存储结构

采用通用的存储结构----链式存储

二、二叉树搜索树的操作

1）二叉搜索树的搜索

如果为空则搜索失败；负责，与根结点关键字值比较，若小于该结点的值，则以同样的方法搜索左子树。若比根结点的关键字值大，则以同样的方法搜索右子树。若等于根结点的关键字值则搜索成功。

2）二叉树的插入

在二叉树上的插入操作首先要搜索插入的位置，即找到新插入位置的双亲结点。故从根节点开始自上向下搜索，记录当前结点的父节点。故通常需要一个临时的指针，来记录当前结点的双亲结点记为q，当前结点为p，这样通过迭代的方法，当p指向空的是时候，即找到要插入的位置。若要插入的值大于q指向值，插在q的右子树，否则插在左子树。通过下图来形象的演示插入的过程。

3）二叉树的删除

与插入操作类似，应先搜索被删除结点p，并记录父结点q，如果不存在操作失败。删除结点的操作由以下几点构成：

若结点p有两个非空子树，需搜索结点p的中序遍历直接后继结点，设为s，将s值复制到p中，因为s最多有一棵非空子树，这样问题转化为“被删除结点最多只有一个非空子树”
若结点p只有一棵非空子树或p是叶子，以结点p的唯一孩子或空子树取代p若被删除的结点p是根结点，则删除后，结点c称为新的根；否则，若p是父节点q的左孩子，则结点c也应成为q的左孩子，不然c成为q的右孩子。最后释放p的资源。

下图形象表现删除两个孩子结点的节点

三、程序的实现