二叉树的基本操作完整版,包含二叉树的所有操作,凡是你想要的都在里面--数据结构版

2021年1月25日发(作者：停止的英文)
#include
#include
#include
#include
typedef char TElemType;


//
定义结点数据为字符型

typedef int Status;






//
定义函数类型为
int
型

#define ERROR 0
#define OK 1

typedef struct BiTNode{







//
定义结构体





TElemType







data;



//
结点数值

struct BiTNode


*lchild; //
左孩子指针

struct BiTNode


*rchild; //
右孩子指针

struct BiTNode


*next;


//
下一结点指针

}BiTNode, *BiTree;

Status NumJudge(char ch[20]){

//
限制输入数据必须为大于零的整形










char ch1[20];
int num;
while(1){





}
scanf(

num=atoi(ch);






//
将字符串转换为整型

itoa(num,ch1,10);


//
将整型转换为字符串型

if(strcmp(ch,ch1)==0&&num>0)break;
else{printf(
请输入一个大于零的整数
:

return num;
}//NumJudge

Status InitBiTree(BiTree &T){

//
构造空二叉树
T




if(!(T=(BiTree)malloc(size of(BiTNode))))exit(ERROR); //
若申请空间失败则退出

T->next=NULL;
printf(
空二叉树构建成功
!nn
return OK;
}//InitBiTree

Status DestroyTree(BiTree &T,BiTree t){

//
销毁二叉树





if(T){


}
free(T);T=NULL;
printf(
二叉树销毁成功
!n

if(t){







DestroyTree(T,t->lchild);




DestroyTree(T,t->rchild);




free(t);


}







return OK;
}//DestroyTree

Status ClearBiTree(BiTree &T,int sum,int &i){

//
清空二叉树


if(T){







ClearBiTree(T->lchild,sum,i);








ClearBiTree(T->rchild,sum,i);



free(T);



i++;
}






if(i==sum){printf(
二叉树清空成功
!n




return OK;
}//ClearBiTree

Status CreateBiTree(BiTree &T,int i,int j,TElemType ch){

//
按先序次序输入二叉树中结点的值
(
一个字符
),
空格字符表示该结点为空


//
构造二叉链表示的二叉树
T




TElemType ch1;
int k;
char str[20];
if(i==0){printf(


按先序顺序建立二叉树
:< br>请按提示输入相应的数据
(
一个字符
)
，
若提
示结点 数值为空，
n


请输入空格
nn










printf(
请输入树根
:

if(i!=0&&i>=j){ printf(
请输入
%c
的左孩子
:




if(j!=0&&j>i){printf(
请输入
%c
的右孩 子
:

while(1){














//
限制输入数据必须为字符型
,
否则重新输入





















fflush(stdin);
for(k=0;k<20;k++){


str[k]=getchar();
if(str[k]=='n')break;
}
if(k==0)printf (
请输入一个字符后再按
Enter
键
:
if(k==1)break;
if(k>1)printf(
您只能输入一个字符
:
}
ch1=str[0];





//
获取输入的准确字符型数据

if(ch1==' '){T=NULL;return ERROR;}



//
输入空格则为根结点为空

if(ch1!=' '){

















if(!(T=(BiTree)malloc(sizeof(BiTNode)))) exit(ERROR);
T->data=ch1;
























//
生成根结点

ch=T->data;
i++;
CreateBiTree(T->lchild,i,j,ch);








//
构造左子树

j=i;j++;
CreateBiTree(T->rchild,i,j,ch);








//
构造右子树

}
i=0;j=0;
return OK;
}//CreateBitree

Status TreeDepth(BiTree T,int l,int &h){


//
若二叉树存在
,
返回其深度








if(T){

l=l+1;














































}
return h;
if(l>h)h=l;





































TreeDepth(T->lchild,l,h);

















TreeDepth(T->rchild,l,h);
}//TreeDepth

Status GetRootElem(BiTree T){

//
获取根结点值



printf(
该二叉树的根结点值为
: %cnn
return OK;
}//GetRootElem

Status SaveElem(BiTree T,BiTree *Q,int i){

//
根据完全二叉树中，
若本节点位置序号为
i,
则其左 孩子结点为
2i,
右孩子为
2i+1
的方法


//
保存二叉树的有效结点至指针数组
Q
特定的位置



if(T){

Q[i]=T;








SaveElem(T->lchild,Q,2*i);


SaveElem(T->rchild,Q,2*i+1);

}

return OK;
}//SaveElem

Status Lev_Traverse(BiTree T,int h){

//
按层次从上到下
,
每层从左到右的顺序显示树状二叉树


if(T==NULL){printf(
二叉树目前为空树
nn

BiTree *Q;

if(!(Q=(BiTree *)malloc(int(pow(2,h)+1) * sizeof(BiTNode))))exit(ERROR);

int i,j,n=1,k=h;

for(i=1;i<=int(pow(2,h)+1);i++){


Q[i]=NULL;}




SaveElem(T,Q,n);



//
将目前有效结点按照满二叉树的序号存储


printf(

提示
:
规定下图中的有效结点的位置序号从
1
开始按从上到下
,
从左到右的顺序
依次递增
n














for(i=1;i<=(pow(2,h)+1);i++){



//
树形显示二叉树


if(int(pow(2,h))%i==0){











}






}
printf(
printf(for(j=0;j
}
k--;
printf(
if(Q[i])printf(
if(!Q[i])printf(
for(j=0;j

printf(

printf(

i=0;j=0;

return OK;
}//Lev_Traverse


Status FirstPrint(BiTree T,int i){

//
按先序次序
(
递归
)
访问二叉树


if(i==0)printf(
先序
(
递归
)
遍历结果如 下
:n







if(T){

i++;printf(





//
访问
T


}
i=0;
return OK;
FirstPrint(T->lchild,i);


//
递归遍历左子树

FirstPrint(T->rchild,i);


//
递归遍历右子树

}//FirstPrintBiTree

Status MiddlePrint(BiTree T,int i){

//
按中序次序
(
递归
)
访问二叉树




if(i==0)printf(
中序
(
递归
)
遍历结果如下
:n
if(T){

i++;









}
i=0;
MiddlePrint(T->lchild,i);



//
递归遍历左子树

printf(





//
访问
T
MiddlePrint(T->rchild,i);


//
递归遍历右子树

return OK;
}//MiddlePrint

Status LastPrint(BiTree T,int i){

//
按后序次序
(
递归
)
访问二叉树











Status PreOrderTraverse(BiTree T){



//
按先序
(
非递归
)
遍历二叉树
T




BiTree p,S,q;
int flag=0;
if(!(S=(BiTree)malloc(sizeof(BiTNode)) ))exit(ERROR);

S->next=NULL;





//
建立空栈
S
if(i==0)pri ntf(
后序
(
递归
)
遍历结果如下
:n
if(T ){




i++;
LastPrint(T->lchild,i);


//
递归遍历左子树

LastPrint(T->rchild,i);


//
递归遍历右子树

printf(


//
访问
T
}
i=0;
return OK;
}//LastPrint

p=T;







printf(
先序
(
非递归< br>)
遍历结果如下
:n








while(1){

while(1){



















//
遍历存储并访问左子树直到根结点左孩子不存在










printf(
q=S->next;S->next=p;p->next=q;



//
当前结点进栈

if(p->lchild)p=p->lchild;

else{break;}
}
while(1){



















//
栈顶指针出 栈
,
如果当前栈顶指针的右孩子存在
则跳出循环




p=S->next;S->next=p->next;










if(!S->next&&!p->rchild){flag=1;break;}


//
如果栈空并且当前结点右孩子不
存在则遍历结束








if(p->rchild){p=p->rchild;break;}
}
if(flag==1)break;

}

printf(

return OK;
}//PreOrderTraverse

Status InOrderTraverse(BiTree T){



//
中序遍历
(
非递归
)
二叉树
T



BiTree p,S,q;
if(!(S=(BiTree)malloc(s izeof(BiTNode))))exit(ERROR);

S->next=NULL;





//
建立空栈
S

p=T;




printf(
中序
(
非递归
)
遍历结果如下< br>:n


while(p||S->next){

if( p){q=S->next;S->next=p;p->next=q;p=p->lchild;}


//
左孩子进栈



else{












p=S->next;S->next=p->next;







if(p)printf(





//
输出栈中元素




else{return ERROR;}












p=p->rchild;



}
}

printf(

return OK;
}//InOrderTraverse

Status PostOrderTraverse(BiTree T){



//
后序遍历
(
非递归
)
二叉树
T



BiTree p,S,q;
if(!(S=(BiTree)mal loc(sizeof(BiTNode))))exit(ERROR);

S->next=NULL;






//
建立空栈
S

p=T;




printf(
后序
(
非递归
)
遍历结果如下< br>:n












while(1){

while(1){





//
遍历左子树
,
若当前结点左右孩子都不存在则跳出

















}
while(S->next){











p=S->next;S->next=p->next;




//
栈顶指针出栈并访问


printf(
q=S->next;S->next=p;p->next=q;

//
当前结点进栈

if(p->lchild)p=p->lchild;






else{


}
if(p->rchild)p=p->rchild;
else{break;}



if(!S->next)break;













//
若栈空则跳出

if(p==S->next->rchild)p=S->next;



//
若当前结点为栈顶指针的右孩子
,
则继
else{

if(S->next->rchild){










//
栈顶指针右孩存在
,
指针移至栈顶指针的


}

}
p=S->next->rchild;break;



续出栈


















}





右孩子后跳出循环

}
if(!S->next)break;




//
若栈空则跳出循环

printf(
return OK;
}//PostOrderTraverse

Status GetElemSum(BiTree T){

//
计算二叉树中总结点的个数








BiTree p,*q;
int l=0,h=0;
if(!(q=(BiTree *)malloc(int(pow(2,TreeDepth(T,l,h))+1) * sizeof(BiTNode))))exit(ERROR);
int head=1,tail=2;
q[1]=T;
while(head
p=q[head++];


if(p->lchild)q[tail++]=p->lchild;








if(p->rchild)q[tail++]=p->rchild;

}

return head-1;
}//GetElemSum

Status LevelOrderPrint(BiTree T){

//
二叉树
T
存在
,
层序遍历二叉树


//
将二叉树中的结点按从上到下
,
从左到右的顺序存至指针数组
q ,
然后按次序输出




BiTree p,*q;
if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR);

int head=1,tail=2;

q[1]=T;




printf(
层序
(
非递归
)
遍历结果如下< br>:n





while(head



p=q[head++];
printf(
if(p->lchild)q[tail++]=p->lchild;
if(p->rchild)q[tail++]=p->rchild;

}

printf(

return OK;
}//LevelOrderPrint


Status GetElemNum(BiTree T,TElemType e){

//
查找元素
e
在二叉树
T
中的个数及位置


int j,i=0,num=0,*a;

















BiTree p,*q;
if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR);
if(!(a=(int *)malloc(GetElemSum(T) * sizeof(int))))exit(ERROR);

int head=1,tail=2;
q[1]=T;
while(head
p=q[head++];



if(p->data==e){num++;
a[i]=head-1;i++;}
if(p->lchild)q[tail++]=p->lchild;








if(p->rchild)q[tail++]=p->rchild;
}
printf(
元素
%c
在二叉树中的个数为
: %dn
p rintf(
元素
%c
在二叉树中的位置序号为
:
for(j=0; j
printf(
}
printf(

return num;
}//GetElemNum


Status GetLeafNum(BiTree T){

//
计算二叉树
T
中叶子个数


BiTree p,*q;







if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR);
int num=0,head=1,tail=2;
q[1]=T;
while(head
p=q[head++];


if(!p->lchild&&!p->rchild)num++;
if(p->lchild)q[tail++]=p->lchild;








if(p->rchild)q[tail++]=p->rchild;

}

return num;
}//GetLeafNum

Status LBrother(BiTree T,int sum){

//
求第
num
个结点的左兄弟











BiTree p,*q;
if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR);

int i,num,head=1,tail=2;
char str[20];
q[1]=T;
printf(
请输入要查找的位置序号
:
num=NumJudge(str);
if(num>sum){printf(
您输入的位置序号大于有效结点个数
n
while(head
p=q[head++];








if(num==tail-2)break;


if(p->lchild)q[tail++]=p->lchild;








if(p->rchild)q[tail++]=p->rchild;

}

if(num==1)printf(
位置
%d
的
%c< br>没有左兄弟
n




else{

















}
for(i=1;i
if(q[i]->lchild== q[num]||q[i]->rchild==q[num])break;
}
if(q [i]->lchild==q[num])printf(
位置
%d
的
%c
没有左兄弟
n
if(q[i]->rchild==q[num])printf(< br>位
置
%d
的
%c
的
左
兄
弟
为
: %cn

return OK;
}//LBrother

Status RBrother(BiTree T,int sum){

//
求第
num
个结点的右兄弟










BiTree p,*q;
if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR);

int i,num,head=1,tail=2;
char str[20];
q[1]=T;
printf(
请输入要查找的位置序号
:
num=NumJudge(str);
if(num>sum){printf(
您输入的位置序号大于有效结点个数
n
while(head

p=q[head++];








if(num==tail-2)break;


if(p->lchild)q[tail++]=p->lchild;








if(p->rchild)q[tail++]=p->rchild;


}
if(num==1)printf(
位置
%d
的
%c
没有右兄弟
n
for(i=1;i
if( q[i]->lchild==q[num]||q[i]->rchild==q[num])break;




else{









}



if(!q[i]->rchild||q[i]->rchild==q[num])printf(
位
置
%d
的
%c
没
有
右
兄
弟n



if(q[i]->rchild&&q[i]->lchil d==q[num])printf(
位
置
%d
的
%c
的< br>右
兄
弟
为
: %cn


}

return OK;
}//RBrother

Status Lchild(BiTree T,int sum){

//
求第
num
个结点的左孩子











BiTree p,*q;
if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR);

int num,head=1,tail=2;
char str[20];
q[1]=T;
printf(
请输入要查找的位置序号
:
num=NumJudge(str);
if(num>sum){printf(
您输入的位置序号大于有效结点个数
n
while(head
p=q[head++];








if(num==tail-2)break;


if(p->lchild)q[tail++]=p->lchild;








if(p->rchild)q[tail++]=p->rchild;


}
if(q[num]->lchild)printf(
位
置
% d
的
%c
的
左
孩
子
为
: %cn

else{printf(
位置
%d
的
%c
的左孩子不存在
n

return OK;
}//Lchild

Status Rchild(BiTree T,int sum){

//
求第
num
个结点的右孩子






BiTree p,*q;
if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR);

int num,head=1,tail=2;
char str[20];
q[1]=T;