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

#include stdio.h#include stdlib.h#include string.h#include math.htypedef char TElemType; /定义结点数据为字符型typedef int Status; /定义函数类型为int型#define ERROR 0#define OK 1typedef struct BiTNode /定义结构体TElemType data; /结点数值struct BiTNode *lchild; /左孩子指针struct BiTNode *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&num0)break;elseprintf(请输入一个大于零的整数: );return 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) DestroyTree(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 CreateBiTree(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的左孩子: , ,ch); if(j!=0&ji)printf(%5s请输入%c的右孩子: , ,ch);while(1) /限制输入数据必须为字符型,否则重新输入fflush(stdin);for(k=0;k1)printf(%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-rchild,i,j,ch); /构造右子树i=0;j=0;return OK;/CreateBitreeStatus TreeDepth(BiTree T,int l,int &h) /若二叉树存在,返回其深度if(T)l=l+1; if(lh)h=l; TreeDepth(T-lchild,l,h); TreeDepth(T-rchild,l,h);return h;/TreeDepthStatus GetRootElem(BiTree T)/获取根结点值printf(该二叉树的根结点值为: %cnn,T-data);return OK;/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二叉树目前为空树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+) /树形显示二叉树if(int(pow(2,h)%i=0)printf(n);printf(tt);for(j=0;jdata);if(!Qi)printf( );for(j=0;jdata); /访问TFirstPrint(T-lchild,i); /递归遍历左子树FirstPrint(T-rchild,i); /递归遍历右子树i=0;return OK;/FirstPrintBiTreeStatus MiddlePrint(BiTree T,int i)/按中序次序(递归)访问二叉树if(i=0)printf(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,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);while(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; /如果栈空并且当前结点右孩子不存在则遍历结束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-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,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) 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(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(headlchild)qtail+=p-lchild; if(p-rchild)qtail+=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(headdata);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(ERROR);if(!(a=(int *)malloc(GetElemSum(T) * sizeof(int)exit(ERROR);int head=1,tail=2;q1=T;while(headdata=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在二叉树中的位置序号为:,e);for(j=0;ji;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(headlchild&!p-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(请输入要查找的位置序号: );num=NumJudge(str);if(numsum)printf(您输入的位置序号大于有效结点个数n);return ERROR;while(headlchild)qtail+=p-lchild; if(p-rchild)qtail+=p-rchild;if(num=1)printf(位置%d的%c没有左兄弟n,num,qnum-data); elsefor(i=1;ilchild=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;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(numsum)printf(您输入的位置序号大于有效结点个数n);return ERROR;while(headlchild)qtail+=p-lchild; if(p-rchild)qtail+=p-rchild;if(num=1)printf(位置%d的%c没有右兄弟n,num,qnum-data); elsefor(i=1;ilchild=qnum|qi-rchild=qnum)break;if(!qi-rchild|qi-rchild=qnum)printf(位置%d的%c没有右兄弟n,num,qnum-data);if(qi-rchild&qi-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(请输入要查找的位置序号: );num=NumJudge(str);if(numsum)printf(您输入的位置序号大于有效结点个数n);return ERROR;while(headlchild)qtail+=p-lchild; if(p-rchild)qtail+=p-rchild;if(qnum-lchild)printf(位置%d的%c的左孩子为: %cn,num,qnum-data,qnum-lchild-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);if(numsum)printf(您输入的位置序号大于有效结点个数n);return ERROR;while(headlchild)qtail+=p-lchild; if(p-rchild)qtail+=p-rchild;if(qnum-rchild)printf(位置%d的%c的右孩子为: %cn,num,qnum-data,qnum-rchild-data);elseprintf(位置%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(numsum)printf(您输入的位置序号大于有效结点个数n);return ERROR;while(headlchild)qtail+=p-lchild; if(p-rchild)qtail+=p-rchild;if(num=1)printf(位置%d的%c没有双亲n,num,qnum-data); elsefor(i=1;ilchild=qnum|qi-rchild=qnum)break;printf(位置%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(请输入要删除结点的位置序号: );num=NumJudge(str);if(numsum)printf(n您输入的位置序号大于有效结点个数nn);return ERROR;if(num=1)printf(t对不起,您不能删除根结点,若想删除根结点,请选择销毁树nn);return ERROR;while(headlchild)qtail+=p-lchild; if(p-rchild)qtail+=p-rchild;for(i=1;ilchild=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(BiTree &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(numsum)printf(n您输入的位置序号大于有效结点个数nn);return ERROR;while(headlchild)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处只能生成右子树,确定插入/退出(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,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,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-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(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=NumJudge(str);if(numsum)printf(n您输入的位置序号大于有效结点个数nn);return ERROR;while(headlchild)qtail+=p-lchild; if(p-rchild)qtail+=p-rchild;printf(%5s请输入新的结点值: , );while(1)fflush(stdin);for(k=0;k1)printf(%5s您只能输入一个字符: , );qnum-data=str0;printf(n 修改成功n);n=1;return OK;/Modifyint MainMenu() /主菜单函数system(cls);int choose;char str20;printf(nttt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*);printf(nttt 计本102 卢荣盼 1018014052);printf(nttt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*);printf(nttt 1建立空树n);printf(nttt 2构造二叉树n);printf(nttt 3显示树状二叉树n);printf(nttt 4遍历二叉树 -进入子菜单n);printf(nttt 5查看二叉树信息 -进入子菜单n);printf(nttt 6对二叉树进行操作 -进入子菜单n);printf(nttt 0退出程序);printf(nttt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*);printf(nttt请输入你的选择: );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)choose=atoi(str);break;elseprintf(ttt选择错误请重新输入: );if(choose=0)printf(nnt谢谢使用本程序nn);return choose;/MainMenu()int Menu() /主菜单函数system(cls);int choose;char str20;printf(nttt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*);printf(nttt 请选择对应的选项按对应的方式遍历二叉树);printf(nttt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*);printf(ntttt1按先序(递归)遍历二叉树n);printf(ntttt2按中序(递归)遍历二叉树n);printf(ntttt3按后序(