7.4 二叉排序树查找
7.4 二叉排序树查找
前面介绍的3种查找方法都是用线性表作为表的组织形式，其中以对分查找效率最高。但由于对分查找要求表中记录按关键字有序排列，且不能用链表作为存储结构，因此，当表的插入或删除操作频繁时，为了维护表的有序性，需要移动表中很多记录。这种由移动记录引起的额外时间开销，就会抵消对分查找的优点。若要对动态查找表进行高效率的查找，可采用几种特殊的二叉树作为表的组织形式。本节介绍在二叉排序树上进行查找和修改操作的方法。
7.4.1 二叉排序树的基本概念
二叉排序树是一种特殊的二叉树，在一般二叉树中，区分左子树和右子树，但节点的值是无序的，而在二叉排序树中，不仅区分左子树和右子树，而且整个树的节点是有序的。
二叉排序树又称二叉查找树，它或者是一棵空树，或者是一棵具有如下特性的非空二叉树：
· 若它的左子树非空，则左子树上所有节点的关键字均小于根节点的关键字。
· 若它的右子树非空，则右子树上所有节点的关键字均大于（若允许具有相同的关键字的节点存在，则大于等于）根节点的关键字。
· 左、右子树本身又各是一棵二叉排序树。
如图7-5所示的二叉树是一棵二叉排序树。
如同二叉树一样，二叉排序树可以采用顺序存储结构和二叉链存储结构，通常采用后者。二叉排序树的二叉链存储结构的节点类型定义如下：
|
图7-5 二叉排序树 |
{
KeyType key;
ElemType data;
struct tnode *lchild,*rchild;
} BSTNode;
其中，key表示关键字域；data表示其他数据域；lchild和rchild分别表示左指针域和右指针域，分别存储左孩子节点和右孩子节点（左右子树的根节点）的地址。
7.4.2 二叉排序树的插入
先在二叉排序树bt中查找关键字为k的节点*p，用f指回其双亲节点，若*p为NULL，则表示插入关键字为k的节点作为*f的左或右孩子节点，创建关键字为k的节点*p，再插入*p节点。
int BSTInsert(BSTNode *&bt,KeyType k)
{
BSTNode *f,*p=bt;
while(p!=NULL)
{
if(p->key==k)
return(0);
f=p; /*f指向*p节点的双亲节点*/
if(p->key>k)
p=p->lchild; /*在左子树中查找*/
else
p=p->rchild; /*在右子树中查找*/
}
p=(BSTNode *)malloc(sizeof(BSTNode)); /*建立新节点*/
p->key=k;
p->lchild=p->rchild=NULL;
if(bt==NULL) /*原树为空时，*p作为根节点插入*/
bt=p;
else if(k<f->key)
f->lchild=p; /*插入*p作为*f的左孩子*/
else
f->rchild=p; /*插入*p作为*f的右孩子*/
return(1);
}
例如，在图7-5所示的二叉排序树bt中插入关键字为“7”的节点过程是：bt≠NULL，k=7，先与二叉排序树bt的根节点关键字“10”进行比较，7<10，插入到左子树bt1中；
|
图7-6 插入节点后的二叉排序树 |
7.4.3 二叉排序树的删除
在二叉排序树bt中删除关键字为k的节点。其过程如下：
（1）首先在二叉排序树中查找关键字为k的节点p，用f指向其双亲节点。
（2）若*p节点无左子树，则用*p节点的右孩子节点替换它，其过程是，若*p是*f的左孩子节点，则将*p的右孩子节点作为*f的左孩子节点；若*p是*f的右孩子节点，则将*p的右孩子节点作为*f的左孩子节点。这里包含了*p为叶子节点的情况。
（3）若*p节点无右子树，则用*p节点的左孩子替换它，其过程是，若*p是*f的左孩子节点，则将*p的左孩子节点作为*f的左孩子节点，若*p是*f的右孩子节点，则将*p的左孩子节点作为*f的左孩子节点。
（4）若*p节点既有左子树又有右子树，则可以用*p节点的左子树的最右下节点替换它，也可以用*p节点的右子树的最左下节点替换它，这里采用前者。其过程是，查找*p左子树的最右下节点*r，用f1指向*r的双亲节点，找到的*r一定无右子树，采用前面类似的方式先删除*r，然后用*r替换*p。
int BSTDelete(BSTNode *&bt,KeyType k)
{
BSTNode *p=bt,*f,*r,*f1;
f=NULL; /*p指向待比较的节点，f指向*p的双亲节点*/
while(p!=NULL && p->key!=k) /*查找值域为x的节点*/
{
f=p;
if(p->key>k)
p=p->lchild; /*在左子树中查找*/
else
p=p->rchild; /*在右子树中查找*/
}
if(p==NULL) /*未找到key域为k的节点*/
return(0);
else if(p->lchild==NULL) /**p为被删节点，若无左子树*/
if(f==NULL) /**p是根节点，则用右孩子节点替换它*/
bt=p->rchild;
else if(f->lchild==p) /**p是双亲节点的左孩子节点，则用其右孩子节点替换它*/
{
f->lchild=p->rchild;
free(p);
}
else if(f->rchild==p) /**p是双亲节点的右孩子节点，则用其右孩子节点替换它*/
{
f->rchild=p->rchild;
free(p);
}
else if(p->rchild==NULL) /**p为被删节点，若它无右子树*/
{
if(f==NULL) /**p是根节点，则用左孩子节点替换它*/
bt=p->lchild;
if(f->lchild==p) /**p是双亲节点的左孩子节点，则用其左孩子节点替换它*/
{
f->lchild=p->lchild;
free(p);
}
else if(f->rchild==p) /**p是双亲节点的右孩子节点，则用其左孩子节点替换它*/
{
f->rchild=p->lchild;
free(p);
}
}
else /**p为被删节点，若它有左子树和右子树*/
{
f1=p;r=p->lchild; /*查找*p左子树中的最右下节点*r*/
while(r->rchild!=NULL) /**r一定是无右子树的节点，*f1作为r的双亲节点*/
{
f1=r;
r=r->rchild;
}
if(f1->lchild==r) /**r是*f1的左孩子节点，删除*r*/
f1->lchild=r->rchild;
else if(f1->rchild==r) /**r是*f1的右孩子节点，删除*r*/
f1->rchild=r->lchild;
r->lchild=p->lchild; /*以下语句是用*r替代*p*/
r->rchild=p->rchild;
if(f==NULL) /**f为根节点*/
bt=r; /*被删节点是根节点*/
else if(f->lchild==p) /**p是*f的左孩子节点*/
f->lchild=r;
else /**p是*f的右孩子节点*/
f->rchild=r;
free(p);
}
return(1);
}
|
图7-7 删除后的二叉排序树 |
就平均时间性能而言，二叉排序树上的查找和对分查找差不多。但就维护表的有序性而言，前者更有效，因为无须移动记录，只需修改指针即可完成对二叉排序树的插入和删除操作，且其平均的执行时间均为O(log2n)。
7.4.4 二叉排序树的查找
在二叉排序树bt中查找关键字为k的节点，并返回其指针。根据二叉排序树的特性，查找节点采用不回溯的方法：若k等于当前节点的关键字，则返回；若k小于当前节点的关键字，则在左子树中查找；若k大于当前节点的关键字，则在右子树中查找。
BSTNode *BSTSearch(BSTNode *bt,KeyType k)
{
BSTNode *p=bt;
while(p!=NULL && p->key!=k)
{
if(k<p->key)
p=p->lchild; /*沿左子树查找*/
else
p=p->rchild; /*沿右子树查找*/
}
return(p);
}
例如，在图7-5所示的二叉排序树bt中查找关键字为9的节点过程是：bt≠NULL，k=9，先与二叉排序树bt的根节点关键字10进行比较，9<10，在其左子树bt1中查找；bt1≠NULL，与二叉排序树bt1（为*bt节点的左子树）的根节点关键字6进行比较，9>6，在其右子树bt2中查找；bt2≠NULL，与二叉排序树bt2（为*bt1节点的右子树）的根节点关键字8进行比较，9>8，在其右子树bt3中查找；bt3≠NULL，与二叉排序树bt3（为*bt2节点的右子树）的根节点关键字9进行比较，9=9，查找成功并返回*bt3节点的指针。