二叉排序树是一种有重要应用意义的数据类型，在二叉排序树上能有效地进行查找操作。同时采用适当算法，根据一组关键字值可以方便地建立与之相应的二叉排序树。按照一定规则在二叉排序树上插入、删除结点仍能保持二叉排序树的性质。

（1）二叉排序树的插入操作

如何建立一棵二叉排序树以及如何在二叉排序树中插入一个新结点呢，实际上，只要解决了插入问题，建树过程就是从空树开始逐次插入新结点的操作，需要注意的是插入一个结点后的二叉树仍然为一棵二叉排序树。

具体做法是：动态生成一个新结点，若二叉排序树为空，则结点作为根结点插入；若非空，则用新结点的关键字值与根结点的关键字比较，若小于根结点的关键字值，新结点应插入左子树，否则，应插入右子树。在左子树或右子树上进行同样的操作，实际上这是一个递归过程。最后新结点的插入位置是二叉排序树中某结点的空指针位置。新结点是作为二叉排序树的叶结点插入，所以新结点插入时它的左、右指针均为空指针。

二叉排序树中插入新结点的非递归算法

	#include <stdio.h>	#include <stdlib.h>	#define MAX 5	#define NULL 0	Bnode * btInsert(int x, Bnode *root);	 	void main()	{	 int i;	 int a[MAX]={60, 40, 70, 20, 80};	 Bnode * root=NULL;	 	 for(i=0;i<MAX;i++)	 root=btInsert(a[i],root);	 /*通过循环调用插入函数，把a[i]逐次插入root为根的二叉排序树中*/	}	Bnode * btInsert(int x, Bnode *root)	/*root为二叉排序树的根指针，x为新结点的关键字值*/	{	 Bnode *p, *q;	 int flag=0; /*是否完成插入的标志*/	 p=(Bnode *)malloc(sizeof(Bnode));	 p->key=x ; /*为新结点关键字赋值*/	 p->right=p->left=NULL; /*新结点要作为叶结点插入*/	 if(root==NULL)	 {	 root=p;	 return p;	 }	 q=root;	 while(flag==0) /*flag==1标志完成插入*/	 {	 if(q->key>x)	 {	 if(q->left!=NULL)	 q=q->left;	 else	 {	 q->left=p; /*在左子树插入*/	 flag=1;	 }	 }	 else	 {	 if(q->right!=NULL)	 q=q->right;	 else	 {	 q->right=p; /*在右子树插入*/	 flag=1;	 }	 }	 }	 return root;	}

对于给定的一个数据元素的集合，循环调用上述二叉排序树的非递归插入算法，便可构造出一棵二叉排序树。图8-6 是对关键字序列{60，40，70，20，80}，按所给关键字的顺序用插入法构造一棵二叉排序树的过程。

构造二叉排序树的过程示意图

第一个关键字60为根结点，第二个关键字40小于60，所以应为根结点的左孩子，第三个关键字70大于根结点60，因此应为其右孩子。接下来，20先和根结点60比较，小于60，则20应在根的左子树上，继续与左子树的根结点40比较，20小于40，应为40这个结点的左孩子。以此类推，可得出一棵二叉排序树。

用二叉排序树的插入算法动态生成的二叉排序树，树的形状、高度不仅仅依赖于关键字值的大小和数量，还与记录输入的先后次序有关系。如上例中的关键字序列{60，40，70，20，80}，若按{20，40，60，70，80}的次序输入的话，得到的二叉排序树如图8-7所示。

构造二叉排序树的过程示意图

同插入结点一样，要求删除一个结点后的二叉树仍然为一棵二叉排序树。图8-8为删除二叉排序树中不同位置结点的示例。图8-8 （a）为要删除结点的二叉排序树，分下面四种情况来考虑：

（1）若待删除的是叶子结点，直接删除即可。如图8-8（b）所示。

（2）若待删除结点只有右子树，而没有左子树，可以直接将其右子树的根结点放到被删除结点的位置上。如图8-8（c）所示。

（3）若待删除结点只有左子树，而没有右子树，可以直接将其左子树的根结点放到被删除结点的位置上。如图8-8（d）所示。

（4）若待删除结点p既有左子树又有右子树，首先找出p结点的右子树中关键字最小的结点，设为s，因为它最小，所以s没有左子树。此时，用结点s取代结点p的位置，而用s的右子树的根结点（连带该根结点的后代）取代s结点的位置，如图8-8（e）所示。

在二叉排序树中删除结点示意图

在二叉排序树中删除结点示意图

可以证明，二叉排序树的平均查找长度为O（log2n）。在二叉排序树上可以方便地进行结点的插入和删除，因此，对于经常要进行插入和删除运算的查找表，采用二叉排序树是最佳的选择。