4.5.1 二叉排序树

1、二叉排序树的定义

左子树结点值<根结点值<右子树结点值

2、二叉排序树的查找

二叉排序树的查找时从根结点开始，沿着某一分支逐层向下进行比较比较的过程。若二叉排序树非空，将给定值与根结点的关键字比较，若相等，则查找成功；若不等，则当根结点的关键字大于给定关键字时，在根结点的左子树中查找，否则在根结点的右子树中查找。

二叉排序树的非递归查找算法：

BSTNode *BST_Search(BiTree T,ElemType key,BSTNode *&p){
//查找函数返回指向关键字为key的结点指针，若不存在，则返回NULL
	p=NULL;//p指向被查找结点的双亲，用于以后的插入和删除操作
	while（T!=null&&key!=T->data）{
		p=T;
		if(key<T->data)
			T=T->lchild;
		else
			T=T->Rchild;
	}
	return T;
}

二叉排序树的递归查找算法：

BSTNode *BST_Search(BiTree T,ElemType key,BSTNode *&p){
//查找函数返回指向关键字为key的结点指针，若不存在，则返回NULL
<pre name="code" class="cpp">        p=NULL;//p指向被查找结点的双亲，用于以后的插入和删除操作

  if(key==T->data){return T;}

        p=T;

  if(key<T->data)BST_Search(T->Lchild);elseBST_Search(T->Rchild);}

3、二叉排序树的插入

二叉排序树作为一种动态集合，其特点是树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。

由于二叉排序树是递归定义的，插入结点的过程是，若原二叉排序树为空，则直接插入结点，否则，若关键字k小于根结点关键字，则插入到左子树中，若关键字K大于根结点关键字，则插入到右子树中。

int BST_insert(BiTree &T,keyType k){
//在二叉排序树T中插入一个关键字为k的结点
	if(T==null){//原树为空，新插入的记录为根结点
		T=(BiTree)malloc(sizeof(BSTNode));
		T->key=k;
		T->lchild=T->rchild=null;
		return 1;//返回1，表示成功
	}
	else if(k==T->key)//树中存在相同关键字的结点
		return 0;
	else if(k<T->key)//插入到T的左子树中
		return BST_insert（T->lchild，k);
	else
		return BST_insert（T->rchild，k);
}

4.二叉排序树的构造

构造一棵二叉排序树就是依次输入数据元素，并将它们插入二叉排序树中的适当位置上的过程。

具体过程是，每读入一个元素就建立一个新结点，若二叉排序树非空，则将新结点的值与根结点的值比较，如果小于根结点的值，则插入到左子树，否则插入到右子树；若二叉排序为空，则新结点作为二叉排序树的根结点。

void create_BST(BiTree &T,KeyType Str[],int n){
//用关键字数组str[]建立一个二叉排序树
	T=null;//初始时bt为空树
	int i=0;
	while (i<n){//依次将每个元素插入
		BST_insert(T,str[i]);
		i++;
	}
}

5、二叉排序树的删除

在二叉排序树中删除一个结点时，不能把以该结点为根的子树的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下来，将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性子不会丢失。

①如果被删除结点Z是叶结点，则直接删除，不会破坏二叉排序树的性质。

②若结点Z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，代替z的位置。

③若结点z有左、右两棵子树，则令z的直接后继（或直接前驱）代替Z，然后从二叉排序树中删除这个直接后继（或直接前驱），这样就转化成第一种或第二种情况。

6、二叉排序树的查找效率分析

对于高度为H的二叉树，其插入和删除操作的运行时间都是O(H)，但在最坏的情况下，即构造二叉排序树的输入序列是有序的，则会形成一个倾斜的单支树，此时二叉排序树的性能显著变坏，树的高度也增加为元素个数N。

二叉排序树查找算法的平均查找长度，主要取决于树的高度，即与二叉树的形态相关。如果二叉排序树是一个只有右（左）孩子的单支树（类似于有序的单链表），其平均查找长度和单链表相同，为O(n).如果二叉排序树的左、右子树的高度之差的绝对值不超过1，这样的二叉排序称为平衡二叉树，它的平均查找长度达到O(log2 N)。

从查找过程看，二叉排序树与二分查找相似。就平均时间性能而言，二叉排序树的上的查找和二叉查找差不多。但二分查找的判定树唯一，二叉排序树不唯一，相同的关键字其插入顺序不同可能生成不同的二叉排序树。

就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，平均执行时间为O(log2 n)。

二分查找的对象是有序顺序表，若有插入和删除结点的操作，所花的代价是O(n)。

当有序表是静态查找表时，宜用顺序表作为其存储结构，而采用二分查找实现其查找操作。

若有序表是动态查找表时，则应选择二叉排序树作为其逻辑结构。