二叉排序树的插入、查找、删除

二叉排序树的定义

二叉排序树右称二叉查找树。或者为空树，或者是具有以下性质：

（1）若它的左子树不为空，则左子树所有节点的值小于根结点，

（2）若它的右子树不为空，则根结点的值小于所有右子树结点的值

（3）它的左右子树叶分别为二叉排序树

总结起来就是根据结点的值有：左子树<根结点<右子树

如下图就是一棵二叉排序树

它的中序遍历：12、19、23、28、34、36、38、42、53、65、90，刚好是排好序的。

二叉排序树的查找分析

二叉排序树有一些基本的应用，可以用于查找，查找的长度与树的深度有关。其平均查找长度为logN（以2位底的对数，N为结点个数）。

一个序列的排序二叉树有多种构造情况。下面考虑两种极端情况：深度最小和深度最大的二叉排序树。

关键字序列（45,24,53,12,37,93），假设6个记录的查找概率相等都为1/6

容易看出这是一棵完全二叉树，该数的深度（最大层次）为3，它的平均查找长度为：

ASL = 1/6（1+2+2+3+3+3）= 14/6

再来看该关键字序列构成深度最大的二叉排序树

这是一棵单支树，其深度为6，它的平均查找长度为：

ASL = 1/6（1+2+3+4+5+6）= 21/6

在随机情况下,该数的平均查找长度总是介于这两种情况之间，即14/6 < log6 < 21/6。二叉排序树的平均查找长度和logN是等数量级的。

二叉排序树的构造过程

以上述完全叉树序列为例，构造该二叉排序数的过程如下图：

容易看出，每次插入新的结点都是二叉排序树上的叶子结点，则在插入时，不必移动其他结点，只需改动某个结点的指针，由空变为非空即可。

结点的插入操作与二叉排序树的定义紧密相关，即左<根<右，新插入一个关键字时，从根结点开始比较，直到找到合适的插入位置为止。还有一种情况就是一个序列中可能有两个相同的关键字，对于这种情况，向树中插入关键字时遇到相同关键字时，什么都不做，不进行重复插入操作。

二叉排序树的删除过程

删除二叉排序树中任意一个结点，需要分成以下三种情况讨论：

（1）删除的是叶子结点

这种情况最简单，由于删除叶子结点不会破坏整棵树的结构，只需要修改其双亲结点的指针即可。

（2）删除的结点只有左子树或只有右子树。

这种情况只需要将其左子树或右子树往上推，替代要删除结点的位置，显然，作此修改也不会破坏二叉排序树的结构。

（3）删除的结点左右子树都不为空

这种情况稍微复杂一点，为了不保持二叉排序树的结构，有两种思路，一种就是从要删除结点的左子树中选取最大的结点进行替代之，另一种就是从要删除的结点的右子树中选取最小的结点替代之。

下面考虑第三种情况

f、p、q、s分别为指向结点F、P、Q、S的指针，假如现要删除结点P，它的左右子树都不为空。

其一就是寻找P的左子树中的最大结点，代替之。

易知左子树中最大结点为S，将P结点用S结点代替，还需处理S结点的左孩子K，由于S只有左子树K,在删除结点S之后，只要令K为S的双亲Q的右子树即可。

其二就是寻找P结点的右子树中最小的结点，代替之。

找到P后，第一步就是往右走一步到R，若R的左子树不为空，则最小的结点在R的左子树中，只需一直往左走即p=p->Left,指定p->Left为空（右子树最小结点，其左子树定为空

），则找到最小结点，将其代替要删除的结点P，并将最小结点的右子树代替该最小结点即可。如下图，Z为要删除结点中右子树中最小结点，将P用Z代替后，Z的位置再由Y代替

若R的左子树为空，那么最小结点就是R，只需将R往上推代替P

具体实现：

/*BinarySearchTree.cpp*/

#include

#include

typedef int ElementType;

typedef struct TreeNode{

ElementType Element;

struct TreeNode *Left;

struct TreeNode *Right;

}TreeNode,*SearchTree;

SearchTree Insert(SearchTree T,ElementType e)

{

//二叉排序树的插入过程

if(!T)

{

//未找到值为e的结点，就新生成一个结点

T = (TreeNode*)malloc(sizeof(TreeNode));

T->Element = e;

T->Left = NULL;

T->Right = NULL;

}

else if(eElement) //在左子树中插入

T->Left = Insert(T->Left,e);

else if(e>T->Element) //在右子树中插入

T->Right = Insert(T->Right,e);

else //e == T->Element do nothing

{

}

return T;

}

int Delete(SearchTree &p)

{

//从二叉排序树中删除结点p,并重接它的左子树或右子树

TreeNode *q,*s;

if(!p->Right) //右子树为空，重接左子树

{

q = p;

p = p->Left;

free(q);

}

else if(!p->Left) //左子树为空，重接右子树

{

q = p;

p = p->Right;

free(q);

}

else //左右子树都不为空

{

q = p;

s = p->Left;

while(s->Right)

{

q = s; //q是s的前驱结点

s = s->Right; //往右走到尽头

}

p->Element = s->Element;

if(q != p)

q->Right = s->Left;

else //q = p;

q->Left = s->Left;

free(s);

}

return 1;

}

int DeleteBST(SearchTree &T,ElementType x)//考虑这里为什么用引用？

{

//在排序二叉树T中删除关键字等于x的结点

if(!T) //不存在关键字等于x的数据元素

return -1;

else

{

if(x == T->Element) //查找成功

return Delete(T);

else if(x < T->Element)

return DeleteBST(T->Left,x); //在左子树中继续查找

else

return DeleteBST(T->Right,x); //在右子树中继续查找

}

return 1;

}

void InOderTravesal(SearchTree T)

{

//中序遍历

if(T)

{

InOderTravesal(T->Left);

printf("%d ",T->Element);

InOderTravesal(T->Right);

}

}

void removeTree(SearchTree T)

{

//销毁二叉树

if(T)

{

removeTree(T->Left);

removeTree(T->Right);

free(T);

T=NULL;

}

}

int main()

{

SearchTree T=NULL;

int a[7] = {45,24,53,45,12,24,90},i;

for(i=0; i<7; ++i)

T=Insert(T,a[i]);

InOderTravesal(T);

printf("\n");

DeleteBST(T,24);

InOderTravesal(T);

removeTree(T);

return 0;

}