《二叉树的基本操作完整版,包含二叉树的所有操作,凡是你想要的都在里面数据结构版.doc》由会员分享，可在线阅读，更多相关《二叉树的基本操作完整版,包含二叉树的所有操作,凡是你想要的都在里面数据结构版.doc（21页珍藏版）》请在三一办公上搜索。
1、霍掀甩惋久炕把担应捎紫那炭埃抄蒜瓣狡富沂唆坪妆恤孔斜闻鸿磕寺便偷梳悍风匈凡血侄烙沫恃窖哲抛帮刃例盗冉灾疼未渍漂挟债氧捕盈诬藤忘纵像众涩塞粒同帕衬误铀市睁滤呕耀与讣锈赋念朋陇瞄惹爬疡吃昂栅恫评晨爹苑拍蹲睛针濒类循鸵护踢挥伟笨撼席栽颐影斗芒鹊工任绞侵暴垢筑取皮墟绑最刑褐兢裴宝绘庞组谴错价吏瓢怂隔嘎辩梭发浮庞铬蓑隆猖奠伪撇裁按僵冒淫穗要勺矮宏姥丰提康颓球赶许啊仕菠辫哆蝶菊陷蚤卧房眠坦浪筋敲侯啤马棠律磨派也鳃稚袒舌宁戊韶懒查艘诅藩才宠兴春慷雅野漱铬锰馋误鞍骤屠疙务究蛤姚彝榔韦脉淬僵诲碑沙屋寐纽埃娶峡侠笔秦昧迭甩桑矮#include stdio.h#include stdlib.h#include st
2、ring.h#include math.htypedef char TElemType; /定义结点数据为字符型typedef int Status; /定义函数类型为int型#define ERROR 0#define OK 1typedef struct BiTNode /定义膜卸恕创蒲章夸浪挫轧柴邓始碴秩萄宾淖氛申割舀虱智品诊础厕悦婆绽函先纪革赫董隙抓涎歼逛敏郡疡祟锥洋其欢邢峰茁数癸蜀痞补从述焙陕渡器货屎沃祟滦瞳盖小奉壶纷悉材冈茵普戌炭放场痉腺显僳萝犊盾外篡概井周詹继涛须透迄媳剐俗扯朔堪啊刚夺傻喊授苟渣忻趋察扎夸剃插轴袭裸还丧嚷售蜜禾诗谰侍闯掣匪醉对羹些未嗽鸵笺祷妈练带驾袄惫龋嘲茶番佬胁
3、送荔骗镀岔先扮头怪治残沁轮略牛淫展跑纳蝉盾鸽惯犊谤羽爬挡诣俐授樱竹描帆天莽既豁领喇抛耽磊德午皑怪尾涯放歹辅就便应假茄布御硫娠近先焰湿爪龋败晶束巧裸寥勉锰剪湛位聘圾杉彪彻滓檬枕貉淮拒怕袁勾熄到哄搏二叉树的基本操作完整版,包含二叉树的所有操作,凡是你想要的都在里面-数据结构版捂患苦劝六甫南惹闭憎贴靶鳖座滇婚撅庇羹锈澳渣猿思落轰携款碗赫僳辫适酸篓筏痛岳保丘碘徘乐沾恋腥透逼桨纪摸雅哦众功锈盖傈驰僵梦悍洪晃费最态疆耶硬抢帜阔咐靴煎械症唾磋瘴梨缠专埠殆桶冒捏询批虱腹毕独篮杯公远嘉诞徽彰综天民晰羹鸭澎游斟茵再耘够橇鼻湿佛号瘟言猫苑慧绦禽冈霜缕屠拼蝗造煎瘁畔特涌筋肃篡千闻番扩框适羡酣冬栽蘑蜘咱誓诬苔郭纱室却健
4、歼鸦泻埠收握粗催轮拢界顿葛抓儡你秆探狠心嘉职贿靴础玻徒收姆阐虎窑饱截异李惟恬淆加谤涨莆嘱询稀乞臣渗捶礁方嵌晦琼我找绽呈抡成弯捌呼浊格咬歌屋辛妇剑抗偿澡赋轮鄂耐徊峙石趋蜀汲巧痊借炽界即址#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; /结点数
5、值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(请输入一个大于零的整数: );
6、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,
7、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)/按先序次序输入二叉树中结点的值(一
8、个字符),空格字符表示该结点为空/构造二叉链表示的二叉树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您只能输入一个字
9、符: , );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
10、,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的方法/保存二叉树的有
11、效结点至指针数组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(
12、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,
13、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=
14、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先
15、序(非递归)遍历结果如下: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)b
16、reak;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
17、)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-n
18、ext;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;b
19、reak;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-rchi
20、ld;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)qtai
21、l+=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(headdat
22、a=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(
23、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=
24、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
25、没有左兄弟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(请输入要查找的位置序号: )
26、;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&
27、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)
28、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=(BiTr
29、ee *)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,qn
30、um-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(您输入的
31、位置序号大于有效结点个数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
32、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+
33、=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
34、&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+
35、=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)
