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

1、#include "stdio.h"#include "stdlib.h"#include "string.h"#include "math.h"typedef char TElemType; /定义结点数据为字符型typedef int Status; /定义函数类型为int型#define ERROR 0#define OK 1typedef struct BiTNode /定义结构体TElemType data; /结点数值struct BiTNode *lchild; /左孩子指针struct BiTNod

2、e *rchild; /右孩子指针struct BiTNode *next; /下一结点指针BiTNode, *BiTree;Status NumJudge(char ch20)/限制输入数据必须为大于零的整形char ch120;int num;while(1)scanf("%s",ch); num=atoi(ch); /将字符串转换为整型itoa(num,ch1,10); /将整型转换为字符串型if(strcmp(ch,ch1)=0&&num>0)break;elseprintf("请输入一个大于零的整数: ");return

3、num;/NumJudgeStatus InitBiTree(BiTree &T)/构造空二叉树Tif(!(T=(BiTree)malloc(sizeof(BiTNode)exit(ERROR); /若申请空间失败则退出T->next=NULL;printf("nt空二叉树构建成功!nn");return OK;/InitBiTreeStatus DestroyTree(BiTree &T,BiTree t)/销毁二叉树if(T)free(T);T=NULL;printf("t二叉树销毁成功!n");if(t) DestroyTre

4、e(T,t->lchild); DestroyTree(T,t->rchild); free(t); return OK;/DestroyTreeStatus 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("t二叉树清空成功!n");T=NULL; return OK;/ClearBiTreeStatus C

5、reateBiTree(BiTree &T,int i,int j,TElemType ch)/按先序次序输入二叉树中结点的值(一个字符),空格字符表示该结点为空/构造二叉链表示的二叉树TTElemType ch1;int k;char str20;if(i=0)printf("n 按先序顺序建立二叉树:请按提示输入相应的数据(一个字符)，若提示结点数值为空，n 请输入空格nn"); printf("%5s请输入树根: "," ");if(i!=0&&i>=j)printf("%5s请输入%c的

6、左孩子: "," ",ch); if(j!=0&&j>i)printf("%5s请输入%c的右孩子: "," ",ch);while(1) /限制输入数据必须为字符型,否则重新输入fflush(stdin);for(k=0;k<20;k+)strk=getchar();if(strk='n')break;if(k=0)printf("%5s请输入一个字符后再按Enter键: "," ");if(k=1)break;if(k>1)prin

7、tf("%5s您只能输入一个字符: "," ");ch1=str0; /获取输入的准确字符型数据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->rchi

8、ld,i,j,ch); /构造右子树i=0;j=0;return OK;/CreateBitreeStatus TreeDepth(BiTree T,int l,int &h) /若二叉树存在,返回其深度if(T)l=l+1; if(l>h)h=l; TreeDepth(T->lchild,l,h); TreeDepth(T->rchild,l,h);return h;/TreeDepthStatus GetRootElem(BiTree T)/获取根结点值printf("该二叉树的根结点值为: %cnn",T->data);return O

9、K;/GetRootElemStatus SaveElem(BiTree T,BiTree *Q,int i)/根据完全二叉树中，若本节点位置序号为i,则其左孩子结点为2i,右孩子为2i+1的方法/保存二叉树的有效结点至指针数组Q特定的位置if(T)Qi=T; SaveElem(T->lchild,Q,2*i);SaveElem(T->rchild,Q,2*i+1);return OK;/SaveElemStatus Lev_Traverse(BiTree T,int h)/按层次从上到下,每层从左到右的顺序显示树状二叉树if(T=NULL)printf("ntt二叉树目

10、前为空树nn");return ERROR;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+)Qi=NULL; SaveElem(T,Q,n); /将目前有效结点按照满二叉树的序号存储printf(" 提示:规定下图中的有效结点的位置序号从1开始按从上到下,从左到右的顺序依次递增n");for(i=1;i<=(pow(2,h)+1);i+) /树形显示二叉

11、树if(int(pow(2,h)%i=0)printf("n");printf("tt");for(j=0;j<pow(2,k-1)-1;j+)printf(" ");k-;if(Qi)printf("%c",Qi->data);if(!Qi)printf(" ");for(j=0;j<pow(2,k+1)-1;j+)printf(" ");printf("nn");i=0;j=0;return OK;/Lev_TraverseStatu

12、s FirstPrint(BiTree T,int i)/按先序次序(递归)访问二叉树if(i=0)printf("n先序(递归)遍历结果如下:n");if(T)i+;printf("%-5c",T->data); /访问TFirstPrint(T->lchild,i); /递归遍历左子树FirstPrint(T->rchild,i); /递归遍历右子树i=0;return OK;/FirstPrintBiTreeStatus MiddlePrint(BiTree T,int i)/按中序次序(递归)访问二叉树if(i=0)printf

13、("n中序(递归)遍历结果如下:n");if(T)i+;MiddlePrint(T->lchild,i); /递归遍历左子树printf("%-5c",T->data); /访问TMiddlePrint(T->rchild,i); /递归遍历右子树i=0;return OK;/MiddlePrintStatus LastPrint(BiTree T,int i)/按后序次序(递归)访问二叉树if(i=0)printf("n后序(递归)遍历结果如下:n");if(T)i+;LastPrint(T->lchild,

14、i); /递归遍历左子树LastPrint(T->rchild,i); /递归遍历右子树printf("%-5c",T->data); /访问Ti=0;return OK;/LastPrintStatus PreOrderTraverse(BiTree T) /按先序(非递归)遍历二叉树TBiTree p,S,q;int flag=0;if(!(S=(BiTree)malloc(sizeof(BiTNode)exit(ERROR);S->next=NULL; /建立空栈Sp=T; printf("n先序(非递归)遍历结果如下:n");w

15、hile(1)while(1) /遍历存储并访问左子树直到根结点左孩子不存在printf("%-5c",p->data);q=S->next;S->next=p;p->next=q; /当前结点进栈if(p->lchild)p=p->lchild;elsebreak;while(1) /栈顶指针出栈,如果当前栈顶指针的右孩子存在则跳出循环p=S->next;S->next=p->next; if(!S->next&&!p->rchild)flag=1;break; /如果栈空并且当前结点右孩子

16、不存在则遍历结束if(p->rchild)p=p->rchild;break;if(flag=1)break;printf("nn");return OK;/PreOrderTraverseStatus InOrderTraverse(BiTree T) / 中序遍历(非递归)二叉树TBiTree p,S,q;if(!(S=(BiTree)malloc(sizeof(BiTNode)exit(ERROR);S->next=NULL; /建立空栈Sp=T; printf("n中序(非递归)遍历结果如下:n");while(p|S->

17、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("%-5c",p->data); /输出栈中元素elsereturn ERROR; p=p->rchild;printf("nn");return OK;/InOrderTraverseStatus PostOrderTraverse(BiTree T) /后序遍历(非递归)二叉树TBiTree p

18、,S,q;if(!(S=(BiTree)malloc(sizeof(BiTNode)exit(ERROR);S->next=NULL; /建立空栈Sp=T; printf("n后序(非递归)遍历结果如下:n");while(1)while(1) /遍历左子树,若当前结点左右孩子都不存在则跳出q=S->next;S->next=p;p->next=q; /当前结点进栈if(p->lchild)p=p->lchild; elseif(p->rchild)p=p->rchild;elsebreak;while(S->next)

19、 p=S->next;S->next=p->next; /栈顶指针出栈并访问printf("%-5c",p->data);if(!S->next)break; /若栈空则跳出if(p=S->next->rchild)p=S->next; /若当前结点为栈顶指针的右孩子,则继续出栈elseif(S->next->rchild) /栈顶指针右孩存在,指针移至栈顶指针的右孩子后跳出循环p=S->next->rchild;break;if(!S->next)break; /若栈空则跳出循环printf(&

20、quot;nn");return OK;/PostOrderTraverseStatus 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;q1=T;while(head<tail)p=qhead+;if(p->lchild)qtail+=p->lchild; if(p->rchild)qtail+

21、=p->rchild;return head-1;/GetElemSumStatus LevelOrderPrint(BiTree T)/二叉树T存在,层序遍历二叉树/将二叉树中的结点按从上到下,从左到右的顺序存至指针数组q,然后按次序输出BiTree p,*q;if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode)exit(ERROR);int head=1,tail=2;q1=T; printf("n层序(非递归)遍历结果如下:n");while(head<tail)p=qhead+;printf(&q

22、uot;%-5c",p->data);if(p->lchild)qtail+=p->lchild;if(p->rchild)qtail+=p->rchild;printf("nn");return OK;/LevelOrderPrintStatus 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(ERRO

23、R);if(!(a=(int *)malloc(GetElemSum(T) * sizeof(int)exit(ERROR);int head=1,tail=2;q1=T;while(head<tail)p=qhead+;if(p->data=e)num+;ai=head-1;i+;if(p->lchild)qtail+=p->lchild; if(p->rchild)qtail+=p->rchild;printf("n元素%c在二叉树中的个数为: %dn",e,num);printf("元素%c在二叉树中的位置序号为:&quo

24、t;,e);for(j=0;j<i;j+)printf("%-4d",aj);printf("n");return num;/GetElemNumStatus GetLeafNum(BiTree T)/计算二叉树T中叶子个数BiTree p,*q;if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode)exit(ERROR);int num=0,head=1,tail=2;q1=T;while(head<tail)p=qhead+;if(!p->lchild&&!p-

25、>rchild)num+;if(p->lchild)qtail+=p->lchild; if(p->rchild)qtail+=p->rchild;return num;/GetLeafNumStatus 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 str20;q1=T;printf("请输入要查找的位置序号

26、: ");num=NumJudge(str);if(num>sum)printf("您输入的位置序号大于有效结点个数n");return ERROR;while(head<tail)p=qhead+; if(num=tail-2)break;if(p->lchild)qtail+=p->lchild; if(p->rchild)qtail+=p->rchild;if(num=1)printf("位置%d的%c没有左兄弟n",num,qnum->data); elsefor(i=1;i<num;i+

27、)if(qi->lchild=qnum|qi->rchild=qnum)break;if(qi->lchild=qnum)printf("位置%d的%c没有左兄弟n",num,qnum->data);if(qi->rchild=qnum)printf("位置%d的%c的左兄弟为: %cn",num,qnum->data,qi->lchild->data);return OK;/LBrotherStatus RBrother(BiTree T,int sum)/求第num个结点的右兄弟BiTree p,*q;

28、if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode)exit(ERROR);int i,num,head=1,tail=2;char str20;q1=T;printf("请输入要查找的位置序号: ");num=NumJudge(str);if(num>sum)printf("您输入的位置序号大于有效结点个数n");return ERROR;while(head<tail)p=qhead+; if(num=tail-2)break;if(p->lchild)qtail+=p-&g

29、t;lchild; if(p->rchild)qtail+=p->rchild;if(num=1)printf("位置%d的%c没有右兄弟n",num,qnum->data); elsefor(i=1;i<num;i+)if(qi->lchild=qnum|qi->rchild=qnum)break;if(!qi->rchild|qi->rchild=qnum)printf("位置%d的%c没有右兄弟n",num,qnum->data);if(qi->rchild&&qi->

30、;lchild=qnum)printf("位置%d的%c的右兄弟为: %cn",num,qnum->data,qi->rchild->data);return OK;/RBrotherStatus 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 str20;q1=T;printf("请输入要查找的位置序号: &q

31、uot;);num=NumJudge(str);if(num>sum)printf("您输入的位置序号大于有效结点个数n");return ERROR;while(head<tail)p=qhead+; if(num=tail-2)break;if(p->lchild)qtail+=p->lchild; if(p->rchild)qtail+=p->rchild;if(qnum->lchild)printf("位置%d的%c的左孩子为: %cn",num,qnum->data,qnum->lchild

32、->data);elseprintf("位置%d的%c的左孩子不存在n",num,qnum->data);return OK;/LchildStatus 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 str20;q1=T;printf("请输入要查找的位置序号: ");num=NumJudge(str);i

33、f(num>sum)printf("您输入的位置序号大于有效结点个数n");return ERROR;while(head<tail)p=qhead+; if(num=tail-2)break;if(p->lchild)qtail+=p->lchild; if(p->rchild)qtail+=p->rchild;if(qnum->rchild)printf("位置%d的%c的右孩子为: %cn",num,qnum->data,qnum->rchild->data);elseprintf(&qu

34、ot;位置%d的%c的右孩子不存在n",num,qnum->data);return OK;/RchildStatus Partents(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 str20;q1=T;printf("请输入要查找的位置序号: ");num=NumJudge(str);if(num>sum)printf(&q

35、uot;您输入的位置序号大于有效结点个数n");return ERROR;while(head<tail)p=qhead+; if(num=tail-2)break;if(p->lchild)qtail+=p->lchild; if(p->rchild)qtail+=p->rchild;if(num=1)printf("位置%d的%c没有双亲n",num,qnum->data); elsefor(i=1;i<num;i+)if(qi->lchild=qnum|qi->rchild=qnum)break;prin

36、tf("位置%d的%c的双亲为: %cn",num,qnum->data,qi->data);return OK;/PartentsStatus TreeDelete(BiTree &T,int sum)/删除第num个结点BiTree p,p1,*q;if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode)exit(ERROR);int i,num,head=1,tail=2,a=0,b=0;char str20;q1=T;printf("请输入要删除结点的位置序号: ");nu

37、m=NumJudge(str);if(num>sum)printf("n您输入的位置序号大于有效结点个数nn");return ERROR;if(num=1)printf("t对不起,您不能删除根结点,若想删除根结点,请选择销毁树nn");return ERROR;while(head<tail)p=qhead+;if(num=tail-2)break;if(p->lchild)qtail+=p->lchild; if(p->rchild)qtail+=p->rchild;for(i=1;i<num;i+)if(

38、qi->lchild=qnum|qi->rchild=qnum)break; printf("n您删除了如下子树:nn");Lev_Traverse(qnum,TreeDepth(qnum,a,b);if(qi->lchild=qnum)qi->lchild=NULL;if(qi->rchild=qnum)qi->rchild=NULL;p1=NULL;DestroyTree(p1,qnum);printf("n删除结点成功n"); return OK;/TreeDeleteStatus TreeInsert(BiTr

39、ee &T,int sum)/在第num个生成子树BiTree p,p1,*q;if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode)exit(ERROR);int num,head=1,tail=2,a=0,b=0;char ch=' ',str20;q1=T;printf("请输入要插入结点的位置序号: ");num=NumJudge(str);if(num>sum)printf("n您输入的位置序号大于有效结点个数nn");return ERROR;while(h

40、ead<tail)p=qhead+;if(num=tail-2)break;if(p->lchild)qtail+=p->lchild; if(p->rchild)qtail+=p->rchild;if(qnum->lchild&&qnum->rchild)printf("您输入的位置序号已有左子树和右子树,无法再此位置插入nn");return ERROR;if(qnum->lchild&&!qnum->rchild)printf("位置%d的%c处只能生成右子树,确定插入/退

41、出(y/n): ",num,qnum->data);while(1) scanf("%s",str);if(strcmp(str,"y")=0|strcmp(str,"n")=0)break;elseprintf("选择错误,请重新输入: ");if(strcmp(str,"y")=0)printf("请输入插入子树的信息: n");CreateBiTree(p1,a,b,ch);if(p1)qnum->rchild=p1;if(strcmp(str,&

42、quot;n")=0)return ERROR;if(!qnum->lchild&&qnum->rchild)printf("位置%d的%c处只能生成左子树,确定插入/退出(y/n): ",num,qnum->data);while(1) scanf("%s",str);if(strcmp(str,"y")=0|strcmp(str,"n")=0)break;elseprintf("选择错误,请重新输入: ");if(strcmp(str,"

43、y")=0)printf("请输入插入子树的信息: n");CreateBiTree(p1,a,b,ch);if(p1)qnum->lchild=p1;if(strcmp(str,"n")=0)return ERROR;if(!qnum->lchild&&!qnum->rchild) printf("请输入插入子树的信息: n");CreateBiTree(p1,a,b,ch); printf("tt你想把新建的树作为位置%d的%c处的: n",num,qnum->

44、data); printf("tt 1左子树 2右子树n");printf("ntt请输入你的选择: ");while(1) scanf("%s",str);if(strcmp(str,"1")=0|strcmp(str,"2")=0)break;elseprintf("选择错误,请重新输入: ");if(strcmp(str,"1")=0)if(p1)qnum->lchild=p1;if(strcmp(str,"2")=0)if

45、(p1)qnum->rchild=p1; printf("插入子树成功n");return OK;/TreeInsertStatus Modify(BiTree T,int sum,int &n)/修改二叉树第num个结点的值BiTree p,*q;if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode)exit(ERROR);int k,num,head=1,tail=2;char str20;q1=T;n=0;printf("请输入要修改结点的位置序号: ");num=NumJudg

46、e(str);if(num>sum)printf("n您输入的位置序号大于有效结点个数nn");return ERROR;while(head<tail)p=qhead+; if(num=tail-2)break;if(p->lchild)qtail+=p->lchild; if(p->rchild)qtail+=p->rchild;printf("%5s请输入新的结点值: "," ");while(1)fflush(stdin);for(k=0;k<20;k+)strk=getchar();

47、if(strk='n')break;if(k=0)printf("%5s请输入一个字符后再按Enter键: "," ");if(k=1)break;if(k>1)printf("%5s您只能输入一个字符: "," ");qnum->data=str0;printf("n 修改成功n");n=1;return OK;/Modifyint MainMenu() /主菜单函数system("cls");int choose;char str20;prin

48、tf("nttt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*");printf("nttt 计本102 卢荣盼 1018014052");printf("nttt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*");printf("nttt 1建立空树n");printf("nttt 2构造二叉树n");printf("nttt 3显示树状二叉树n");printf("nttt 4遍历二叉树 ->

49、>进入子菜单n");printf("nttt 5查看二叉树信息 ->>进入子菜单n");printf("nttt 6对二叉树进行操作 ->>进入子菜单n");printf("nttt 0退出程序");printf("nttt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*");printf("nttt请输入你的选择: ");while(1)scanf("%s",str);if(strcmp(str,&quo

50、t;0")=0|strcmp(str,"1")=0|strcmp(str,"2")=0|strcmp(str,"3")=0|strcmp(str,"4")=0|strcmp(str,"5")=0|strcmp(str,"6")=0)choose=atoi(str);break;elseprintf("ttt选择错误请重新输入: ");if(choose=0)printf("nnt谢谢使用本程序nn");return choos

51、e;/MainMenu()int Menu() /主菜单函数system("cls");int choose;char str20;printf("nttt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*");printf("nttt 请选择对应的选项按对应的方式遍历二叉树");printf("nttt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*");printf("ntttt1按先序(递归)遍历二叉树n");printf(&quo

52、t;ntttt2按中序(递归)遍历二叉树n");printf("ntttt3按后序(递归)遍历二叉树n");printf("ntttt4按先序(非递归)遍历二叉树n");printf("ntttt5按中序(非递归)遍历二叉树n");printf("ntttt6按后序(非递归)遍历二叉树n");printf("ntttt7按层次(非递归)遍历二叉树n");printf("ntttt0返回主菜单");printf("nttt*=*=*=*=*=*=*=*=*=

53、*=*=*=*=*=*=*=*=*=*=*n");printf("ttt请输入你的选择: ");while(1)scanf("%s",str);if(strcmp(str,"0")=0|strcmp(str,"1")=0|strcmp(str,"2")=0|strcmp(str,"3")=0|strcmp(str,"4")=0|strcmp(str,"5")=0|strcmp(str,"6")=0|strc

54、mp(str,"7")=0)choose=atoi(str);break;elseprintf("ttt选择错误请重新输入: ");return choose;/Menu()int Menu1() /查看二叉树信息菜单system("cls");int choose;char str20,str120;printf("nt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*");printf("nt 请选择对应的选项查看当前二叉树的

55、信息");printf("nt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*");printf("nt 1返回根结点值 2二叉树的深度n");printf("nt 3二叉树的总结点个数 4二叉树中度为2的结点个数n");printf("nt 5二叉树中度为1的结点个数 6二叉树中叶子结点个数n");printf("nt 7某一值的结点个数及位置 8二叉树中某结点的左孩子n");printf("nt 9二叉树中某结点的右孩子 10二叉树中某结点的左兄弟n");printf("nt 11二叉树中某结点的右兄弟 12二叉树中某结点的双亲n");printf("