二叉排序树的实现

发布网友发布时间：2022-04-25 15:18

共3个回答

懂视网时间：2022-04-14 16:16

一、二叉排序树如果要查找的数据集是有序线性表且是顺序存储的，查找可以用折半、插值、斐波那契等查找算法来实现。然后，由于有序，当我们在插入和删除操作上，就需要耗费大量的时间。下面将要学习的二叉排序树，就是一种既可以使得插入和删除效率不错，又

一、二叉排序树如果要查找的数据集是有序线性表且是顺序存储的，查找可以用折半、插值、斐波那契等查找算法来实现。然后，由于有序，当我们在插入和删除操作上，就需要耗费大量的时间。下面将要学习的二叉排序树，就是一种既可以使得插入和删除效率不错，又可以比较高效率地实现查找的算法。为此，构造一棵二叉排序树的目的并不是为了排序，而是为了提供查找和插入删除关键字的速度。 1.二叉排序树概念二叉排序树(Binary Sort Tree)，又称为二叉查找树，或者是一棵空树，或者是具有下列性质的二叉树。 ◆若它的左子树不空，则左子树上所有结点的值均小于它的根结构(双亲结点)的值; ◆若它的右子树不空，则右子树上所有结点的值均大于它的根结点(双亲结点)的值; ◆它的左、右子树也分别为二叉排序树。 2.二叉树结点结构

/*二叉树的二叉链表结点结构定义*/
typedef struct BiTNode   //结点结构
{
 int data;      //结点数据
 Struct BiTNode *lchild,*rchild; //左右孩子指针
}BiTNode,*BiTree;

二、二叉排序树操作算法 1.二叉排序树的查询操作

/*递归查找二叉排序树T中是否存在key,
 * 指针f指向T的双亲，其初始调用值为NULL
 *若查找成功，则指针p指向该数据元素结点，并返回TRUE；否则指针p指向查找路径上访问的最后一个结点并返回FALSE*/
Status SearchBST(BiTree T,int key,BiTree f,BiTree *p)
{
 if(!T)    //查找不成功(为空树)
 {
  *p=f;
  return FALSE;
 }
 else if(key==T->data) //查找成功
 {
  *p=T;
  return TRUE;
 }
 else if(keydata)
  return SearchBST(T->lchild,key,T,p); //在左子树继续查找
 else
  return SearchBST(T->rchild,key,T,p); //在右子树继续查找 
}

实例：假如有一数据集合={62,88,58,47,35,73,51,99,37,93}，查找的关键字key=93。使用二叉排序树查找算法步骤如下： ①根据二叉排序树定义将该数据集合构造成一棵二叉排序树(中序遍历);

②调用二叉排序树查询算法SearchBST(T,93,NULL,P)查询关键字，其中，SearchBST函数是一个可递归运行的函数，参数T是一个二叉树链表、key代表要查询的关键字、二叉树f指向T的双亲。当T指向根结点时，f的初值就为NULL，它在递归时有用，最后的参数p是为了查找成功后可以得到查找到的结点位置。 ③ if(!T){ .... }语句。用来判断当前二叉树是否到叶子结点，此时当前T指向根结点62的位置，由于T不为空，故该语句片段不执行。 ④esle if(key==T->data)语句。即查找到相匹配的关键字执行语句，显然93!=62，故该语句片段不执行。 ⑤else if(keydata)语句。即当要查找关键字小于当前结点时执行语句，由于93>62，故该语句片段不执行。 ⑥else{....}语句。即当即当要查找关键字大于当前结点时执行语句，93>62,所以以递归调用SearchBST(T->rchild,key,T,p)。此时，T指向了62的右孩子88，f指向88的双亲结点，即62。如图：

⑦此时第二层SearchBST,因93比88大，所以执行else{....}语句，再次递归调用SearchBST(T->rchild,key,T,p)。此时T指向了88的右孩子99。

⑧此时第三层SearchBST,因93比99小，所以执行else if(keydata)语句，再次递归调用SearchBST(T->lchild,key,T,p)。此时T指向了99的左孩子93。

⑨第四层SearchBST,因key等于T->data，所以执行第10~11行，此时指针p指向93所在的结点并返回True到第三层、第二层、第一层，最终返回函数True。 2.二叉排序树的插入操作所谓二叉排序树的插入，即将关键字放到树中的合适位置。 (1)二叉排序树的插入算法

/*当二叉排序树T中不存在关键字等于key的数据元素时，
 * 插入key并返回TRUE，否则返回FALSE*/
Status InsertBST(BiTree *T,int key)
{
 BiTree p,s;
 /*调用查找函数查找是否存在该关键字*/
 //a.若查找不成功
 if(!SearchBST(*T,key,NULL,&p)) 
 {
  s=(BiTree)malloc(sizeof(BiTNode)); //为结点s开辟一段内存空间
  s->data=key;     //将关键字存放到s指向结点的数据域中
  s->lchid=s->rchild=NULL;  //初始化结点s的左右指针域
  if(!p)
  *T=s;  //插入s为新的根结点
  else if(keydata)//若关键字小于p结点数据值，插入s为结点p的左孩子
  p->lchild = s; 
  else   //若关键字大于p结点数据值，插入s为结点p的右孩子
  p->rchild=s; 
 }
 /*树中已有关键字相同的结点，不再插入*/
 else
 {
  return FALSE; 
 }
}

举例：假如我们调用函数是"InsertBST(T,93);"，那么结果就是FALSE;假如调用函数为"InsertBST(T,95);"，那么一定是就是在93的结点增加一个右孩子95，并返回TRUE。需要注意的是，由于插入算法事先调用了SearchBST(*T,key,NULL,&p)查找算法且使用中序遍历二叉树，最终我们可知指针p指向的结点为93. 3.构建二叉排序树算法

/*假如有一个数据集={62,88,58,47,35,73,51,99,37,93}
 * 构建一个二叉排序树*/
int i;
int a[0]={62,88,58,47,35,73,51,99,37,93};
BiTree T=NULL;
for(i=0;i<10;i++)
{
 InsertBST(&T,a[i]);
}

4.二叉排序树删除操作算法

(1)采用递归方式对二叉排序树T查找key，找到后调用Delete函数删除该结点 /*若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点 * 并返回TRUE；否则返回FALSE*/

Status DeleteBST(BiTree *T,int key)
{
 if(!*T) //不存在关键字等于key的数据元素
  return FALSE;
 else
 {
 if(key==(*T)->data) //找到关键字等于key的数据元素
  return Delete(T); //调用Delete函数删除该结点
 else if(key<(*T)->data)
  return DeleteBST(&(*T)->lchild,key); 
 else
  return DeleteBST(&(*T)->rchild,key);
 } 
}

(2)Delete删除算法

/*从二叉排序树中删除结点p,并重接它的左或右子树*/
Status Delete(BiTree *p)
{
 BiTree q,s;
 /*情况二：删除结点p的右子树或左子树为空*/
 if((*p)->lchild==NULL)  //a.右子树空则只需重接它的左子树
 {
  q=*p; *p=(*p)->lchild; free(q);
 } 
 else if((*p)->rchild==NULL) //b.只需重接它的右子树
 【本文来自鸿网互联 (http://www.68idc.cn)】 {
  q=*p; *p=(*p)->rchild; free(q); //将指针p指向的结点
 }
 //情况三：左右子树均不为空
 else
 {
  q=*p; s=(*p)->lchild;
  while(s->rchild)  //转左，然后向右到尽头(找待删结点的前驱)
  {
   q=s; s=s->rchild;  
  }
  (*p)->data=s->data; //s指向被删结点的直接前驱
  if(q!=*p)
   q->rchild=s->lchild; //重接q的右子树
  else
   q->lchild=s->lchild; //重接q的左子树
  free(s);
 }
 return TRUE;
}

源码分析： q=*p; *p=(*p)->rchild; free(q); 作用：将指针p指向的结点赋值给新结点q，并使p指针指向的左结点，即实现了重接右子树，再释放结点q.
三、二叉排序树总结二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针即可。插入删除的时间性能比较好，而对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数。极端情况，最少为1次，即跟结点就是要找的结点，最多也不会超过树的深度，即二叉排序树的查找性能取决于二叉排序树的形状。

热心网友时间：2022-04-14 13:24

#include <alloc.h>

#define ERROR 0;
#define FALSE 0;
#define TRUE 1;
#define OK 1;

typedef int ElemType;
typedef int Status;
typedef int KeyType;

#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)< (b))
#define LQ(a,b) ((a)<=(b))

typedef struct BinaryTree

{
ElemType data;
struct BinaryTree *l;
struct BinaryTree *r;
}*BiTree,BiNode;

BiNode * new()
{
return( (BiNode *)malloc(sizeof(BiNode)) );
}

CreateSubTree(BiTree *T,ElemType *all,int i)
{
if ((all[i]==0)||i>16)
{
*T=NULL;
return OK;
}
*T=new();
if(*T==NULL) return ERROR;
(*T)->data=all[i];
CreateSubTree(&((*T)->l),all,2*i);
CreateSubTree(&((*T)->r),all,2*i+1);
}

CreateBiTree(BiTree *T)
{
ElemType all[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,};
CreateSubTree(T,all,1);
}

printelem(ElemType d)
{
printf("%d\n",d);
}

PreOrderTraverse(BiTree T,int (*Visit)(ElemType d))
{
if(T){
if(Visit(T->data))
if(PreOrderTraverse(T->l,Visit))
if(PreOrderTraverse(T->r,Visit)) return OK;
return ERROR;
} else return OK;
}

InOrderTraverse(BiTree T,int (*Visit)(ElemType d))
{
if(T){
if(InOrderTraverse(T->l,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->r,Visit)) return OK;
return ERROR;
}else return OK;
}

Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){

if(!T) {*p=f;return FALSE;}
else if EQ(key,T->data){ *p=T;return TRUE;}
else if LT(key,T->data) SearchBST(T->l,key,T,p);
else SearchBST(T->r,key,T,p);
}

Status InsertBST(BiTree *T,ElemType e){
BiTree p;
BiTree s;
if(!SearchBST(*T,e,NULL,&p)){
s=(BiTree)malloc(sizeof(BiNode));
s->data=e;s->l=s->r=NULL;
if(!p) *T=s;
else if (LT(e,p->data)) p->l=s;
else p->r=s;
return TRUE;
}
else return FALSE;
}

void Delete(BiTree *p){
BiTree q,s;
if(!(*p)->r){
q=(*p);
(*p)=(*p)->l;
free(q);
}
else if(!(*p)->l){
q=(*p);
(*p)=(*p)->r;
free(q);
}
else {

/* q=(*p);
s=(*p)->l;
while(s->r) {q=s; s=s->r;}
(*p)->data=s->data;
if(q!=(*p) ) q->r=s->l;
else q->l=s->l;
free(s);
*/

q=s=(*p)->l;
while(s->r) s=s->r;
s->r=(*p)->r;
free(*p);
(*p)=q;

}
}

Status DeleteBST(BiTree *T,KeyType key){
if (!(*T) )
{return FALSE;}
else{
if ( EQ(key,(*T)->data)) Delete(T);
else if ( LT(key,(*T)->data)) DeleteBST( &((*T)->l), key);
else DeleteBST( &((*T)->r),key);
return TRUE;
}
}

main()
{
BiTree root;
BiTree sroot=NULL;
int i;
int a[10]={45,23,12,3,33, 27,56,90,120,62};
system("cls");
CreateBiTree(&root);
printf("PreOrderTraverse:\n");
PreOrderTraverse(root,printelem);
printf("InOrderTraverse:\n");
InOrderTraverse(root,printelem);
for(i=0;i<10;i++)
InsertBST(&sroot,a[i]);
printf("InOrderTraverse:\n");
InOrderTraverse(sroot,printelem);
for(i=0;i<3;i++)
DeleteBST(&sroot,a[i]);
printf("Now sroot has nodes:\n");
InOrderTraverse(sroot,printelem);getch();
}

热心网友时间：2022-04-14 14:42

C++实现行不?