用顺序和二叉链表作存储结构

发布网友 发布时间：2022-03-22 15:44

我来回答

共1个回答

热心网友 时间：2022-03-22 17:13

代码给你吧。功能比你要求的还要多。
如果不想要多了的功能，你应该自己会改吧，删掉点代码就行了。
VC下通过。
#include<stdio.h>
#include<stdlib.h>

typedef struct Tnode{
int data; /*输入的数据*/
struct Tnode *lchild,*rchild; /*结点的左右指针，分别指向结点的左右孩子*/
}*node,BSTnode;
searchBST(node t,int key,node f,node *p) /*查找函数*/
{
if(!t) {*p=f;return (0);} /*查找不成功*/
else if(key==t->data) {*p=t;return (1);} /*查找成功*/
else if(key<t->data) searchBST(t->lchild,key,t,p); /*在左子树中继续查找*/
else searchBST(t->rchild,key,t,p); /*在右子树中继续查找*/
}

insertBST(node *t,int key) /*插入函数*/
{
node p=NULL,s=NULL;

if(!searchBST(*t,key,NULL,&p)) /*查找不成功*/
{
s=(node)malloc(sizeof(BSTnode));
s->data=key;
s->lchild=s->rchild=NULL;
if(!p) *t=s; /*被插结点*s为新的根结点*/
else if(key<p->data) p->lchild=s;/*被插结点*s为左孩子*/
else p->rchild=s; /*被插结点*s为右孩子*/
return (1);
}
else return (0);/*树中已有关键字相同的结点，不再插入*/
}

inorderTraverse(node *t) /*中序遍历函数*/
{
if(*t){
if(inorderTraverse(&(*t)->lchild)) /*中序遍历根的左子树*/
printf("%d ",(*t)->data); /*输出根结点*/
if(inorderTraverse(&(*t)->rchild)); /*中序遍历根的右子树*/
}
return(1) ;
}

calculateASL(node *t,int *s,int *j,int i) /*计算平均查找长度*/
{
if(*t){
i++; /*i记录当前结点的在当前树中的深度*/
*s=*s+i; /*s记录已遍历过的点的深度之和*/
if(calculateASL(&(*t)->lchild,s,j,i))/*计算左子树的ASL*/
{
(*j)++; /*j记录树中结点的数目*/
if(calculateASL(&(*t)->rchild,s,j,i)) /*计算右子树的ASL*/
{i--; return(1);}
}
else return(1);
}
}
node Delete(node t,int key) /*删除函数*/
{
node p=t,q=NULL,s,f;
while(p!=NULL) /*查找要删除的点*/
{
if(p->data==key) break;
q=p;
if(p->data>key) p=p->lchild;
else p=p->rchild;
}
if(p==NULL) return t; /*查找失败*/
if(p->lchild==NULL) /*p指向当前要删除的结点*/
{
if(q==NULL) t=p->rchild; /*q指向要删结点的父母*/
else if(q->lchild==p) q->lchild=p->rchild; /*p为q的左孩子*/
else q->rchild=p->rchild;/*p为q的右孩子*/
free(p);
}
else{ /*p的左孩子不为空*/
f=p;
s=p->lchild;
while(s->rchild) /*左拐后向右走到底*/
{
f=s;
s=s->rchild;
}
if(f==p) f->lchild=s->lchild; /*重接f的左子树*/
else f->rchild=s->lchild; /*重接f的右子树*/
p->data=s->data;
free (s);
}
return t;
}
int balanceBST(node t,int *i) /*判断是否为平衡二叉树的函数*/
{
int dep1,dep2;
if(!t) return(0);
else {
dep1=balanceBST(t->lchild,i);
dep2=balanceBST(t->rchild,i);
}
if((dep1-dep2)>1||(dep1-dep2)<-1) *i=dep1-dep2;/*用i值记录是否存在不平衡现象*/
if(dep1>dep2) return(dep1+1);
else return(dep2+1);
}
void main()
{
node T=NULL;
int num;
int s=0,j=0,i=0;
int ch=0;
node p=NULL;
printf("输入一串数，每个数以空格分开，最后一个数为0作结束:");
do{
scanf("%d",&num);
if(!num) printf("完成输入!\n");
else insertBST(&T,num);
}while(num);
printf("\n\n---主程序菜单---\n"); /*主程序菜单*/
printf("\n 0: 退出" );
printf("\n 1: 中序输出");
printf("\n 2: 树的平均查找长度ASL");
printf("\n 3: 删除元素");
printf("\n 4: 判断是否平衡树");
while(ch==ch)
{
printf("\n 选择一个功能以继续:");
scanf("%d",&ch);
switch(ch){
case 0: exit(0); /*0－－退出*/
case 1: printf(" 中序遍历输出结果为:\n ");
inorderTraverse(&T); /*1－－中序遍历*/
break;
case 2: s=0;j=0;i=0;
calculateASL(&T,&s,&j,i); /*2－－计算平均查找长度*/
printf(" ASL=%d/%d",s,j);
break;
case 3: printf(" 输入一个数以删除结点:");
scanf("%d",&num); /*3－－删除某个结点*/
if(searchBST(T,num,NULL,&p))
{
T=Delete(T,num);
printf(" 删除成功!\n ");
inorderTraverse(&T);
}
else printf(" 无%d",num);
break;
case 4: i=0;
balanceBST(T,&i); /*判断是否为平衡二插树*/
if(i==0) printf(" 是平衡树");
else printf(" 不是!");
break;
default: printf("因你的输入错误，请重新输入\n");
break; /*输入无效字符*/
}
}
}

附测试数据一组。
50 33 88 22 8 60 0
1
3
33
3
12
0
经测试正确。