2025年二叉樹(shù)遍歷算法實(shí)踐與數(shù)據(jù)結(jié)構(gòu)深度解析教程

題目：二叉樹(shù)的遍歷和子樹(shù)互換需求分析a)中序遞歸遍歷算法、前序遞歸遍歷算法【選】b)中序遍歷非遞歸算法c)先序或后序遍歷非遞歸算法d)建立中序線索，并進(jìn)行中序遍歷和反中序遍歷6.設(shè)計(jì)一種測(cè)試用的二叉樹(shù)并創(chuàng)立對(duì)應(yīng)的內(nèi)存二叉樹(shù)，可以測(cè)試自己算法的邊界(包括樹(shù)節(jié)點(diǎn)數(shù)為0、1以及>1的不一樣情形)。概要設(shè)計(jì)闡明：本程序在遞歸調(diào)用中用到了鏈表，在操作成果：若S為空棧，則返回OK,否則返回ERROR。操作成果：刪除S的棧頂元素，并用e返回其值。}數(shù)據(jù)對(duì)象D:D是具有相似特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R:若D≠φ,則R={H},H是如下二元關(guān)系；(2)若D-{root}≠φ,則存在D-{root}={D1(3)若Dl≠φ,則D1中存在惟一的元素x1,<root,x1>∈H,且存在D1上的關(guān)系H1SH;若Dr≠D,則Dr且存在上的關(guān)系HrEH;H={<root,x1>,<root,xr>,H1,Hr};操作成果：按規(guī)定構(gòu)造二叉樹(shù)T。PreOrderTraverse_re操作成果：先序遞歸遍歷T,對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)print一次且僅一次。一操作成果：中序非遞歸遍歷T,對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)print一次且僅一次。InOrderTraverse_re(操作成果：中序遞歸遍歷T,對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)print一次且僅一次。一操作成果：先序非遞歸遍歷T,對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)print一次且僅一次。操作成果：分層遍歷二叉樹(shù)T,并輸出。InOrderTraverse_Thr(初始條件：二叉樹(shù)T在在。操作成果：中序非遞歸遍歷二叉線索樹(shù)T初始條件：結(jié)點(diǎn)p在在。操作成果：結(jié)點(diǎn)p及子樹(shù)線索化。{}4.本程序包括三個(gè)模塊1)主程序模塊{接受命令；}}2)鏈表模塊。遞歸調(diào)用時(shí)實(shí)現(xiàn)鏈表抽象數(shù)據(jù)類型。3)棧模塊。非遞歸調(diào)用時(shí)實(shí)現(xiàn)棧的抽象數(shù)據(jù)類型。1.宏定義及全局變量#defineTElemType#defineERROR0BiThrTreepre;intCreateBiTree(BiTree&voidInOrderTraverse(BiTreeT,int(*print)(TElemTypee);//中序非遞歸遍歷二叉樹(shù)voidInOrderTraverse_re(BiTreeT,int(*print)(TElemTypeevoidPreOrderTraverse(BiTreeT,int(*print)(TElemTypee));//先序非遞歸遍歷二叉樹(shù)voidInOrderThreading(BiThrTree&Thrt,BiThrTreintInOrderTraverse_Thr(BiThrTreeT,int(*print)(TEvoidInThreading(BiThrTreep);typedefstructBiTNode{PointerTagLTag,RTag;a)構(gòu)造二叉樹(shù)T{{if(!(T=(BiTNode*)malloc(sizeof(if(CreateBiTree(T->lchild))T->LTag=Link;if(CreateBiTree(T->rchild))T->RTag=Link;}}b)先序遞歸遍歷二叉數(shù)T,并輸出所有結(jié)點(diǎn)值。voidPreOrderTraverse_re(BiTreeT,i{{PreOrderTraverse_re(T->lchildPreOrderTraverse_re(T->rchild}}c)中序非遞歸遍歷二叉樹(shù)T,并輸出所有結(jié)點(diǎn)值voidInOrderTraverse(BiTreeT,i{{}}d)中序遞歸遍歷二叉樹(shù)T,并輸出所有結(jié)點(diǎn)值voidInOrderTraverse_re(BiTreeT,int(*print)(TE{InOrderTraverse_re(T->lchiInOrderTraverse_re(T->rchil}e)中序遍歷二叉樹(shù)T,并將其中序線索化，Thrt指向頭結(jié)點(diǎn)Thrt=(BiThrTree)malloc(sizeof(Thrt->LTag=Link;//建頭結(jié)點(diǎn)f)結(jié)點(diǎn)p線索化InThreading(p->lchild);//左子樹(shù)線索化if(!p->lchild)//建前驅(qū)線索if(!pre->rchild)//建后繼線索pre=p;//保持pre指向p的前驅(qū)InThreading(p->rchild);//右子樹(shù)線索化intInOrderTraverse_Thr(BiThrwhile(p->RTag==Thread&}}typedefstruct{a)創(chuàng)立一種空棧{S.base=(SElemType*)malloc(STACK_INIT_SIZE}b)棧頂插入元素{if(S.top-S.base>=S.S.base=(SElemType*)realloc(S.base,(STACK_INIT_c)棧頂刪除元素}d)判斷棧與否為空棧{}printf("*************************:**********************\n"printf("**試驗(yàn)12二叉樹(shù)的遍歷**\n");printf("**1.實(shí)現(xiàn)二叉樹(shù)的不一樣遍歷算法和二叉樹(shù)的中序線索化算法**\n");printf("**c)printf("**d)先序或后序遍歷非遞歸算法之一；**\n"):printf("**e)建立中序線運(yùn)用線索進(jìn)行中序遍歷和反中序遍歷。**\n");printf("**2.實(shí)現(xiàn)二叉樹(shù)的按層遍歷算法。**\n");printf("**********************************************************\n"printf("\n選擇操作：\n\t1.先序與中序遍歷算法\n\t2.中序線索的中序遍歷和反中序遍printf("前序遞歸創(chuàng)立二叉樹(shù)(空格表達(dá)此結(jié)點(diǎn)為空):\n");InOrderTraverse_re(printf("\n前序遞歸遍歷輸出：");PreOrderTraverse_re(T,printf("\n中序非遞歸遍歷輸出：");printf("\n前序非遞歸遍歷輸出：");PreOrderTraverse(T,case2:printf("前序遞歸創(chuàng)立二叉樹(shù)(空格表達(dá)此結(jié)點(diǎn)為空):\n");InOrderTraverse_Thr(Thrcase3:printf("前序遞歸創(chuàng)立二叉樹(shù)(空格表達(dá)此結(jié)點(diǎn)為空):\n");printf("\n按層遍歷輸出：");6.函數(shù)間調(diào)用關(guān)系作調(diào)試分析C:\C:\Users\dudu\Desktop\我的學(xué)習(xí)資料\第二學(xué)期數(shù)據(jù)結(jié)構(gòu)\作業(yè)實(shí)驗(yàn)報(bào)告二\Debug\BiTree.ex.口回實(shí)驗(yàn)12_二叉樹(shù)的遍歷**1.實(shí)現(xiàn)二又樹(shù)的不同遍歷算法和二叉樹(shù)的中序線索化算法**中序遞歸遍歷算法；先序遞歸遍歷算法：中序遍歷的非遞歸算法先序或后序遍歷非遞歸算法之一；**e)建立中序線利用線索進(jìn)行中序遍歷和反中序遍歷。**2.實(shí)現(xiàn)二叉樹(shù)的按層遍歷算法。選擇操作：1.先序與蟲(chóng)序遍歷算法2.中序線索的中序遍歷和反中序遍歷算法3.按層遍歷算法三X1.顧客需根據(jù)顧客提醒信息操作，輸入二叉樹(shù)(以空格表達(dá)空結(jié)點(diǎn)),輸入完畢后按回車鍵，C:\C:\Users\dudu\Desktop\我的學(xué)習(xí)資料\第二學(xué)期數(shù)據(jù)結(jié)構(gòu)\作業(yè)\實(shí)驗(yàn)報(bào)告二\Debug\BiTree.ex..**1.實(shí)現(xiàn)二叉樹(shù)的不同遍歷算法和二叉樹(shù)的中序線索化算法先序或啟**e)建立中序線利用線索進(jìn)行中序遍歷和反中序遍歷。**2.買現(xiàn)二叉樹(shù)的按層遍歷算法。*W***KN*K**N*KK*W**前序遞歸創(chuàng)建二叉樹(shù)(空格表示此結(jié)點(diǎn)為空):+a*h-cd-ef中序遞歸遍歷輸出：a+b*c-d前序遞歸遍歷輸出：+a*b-cd前序非遞歸遍歷輸出：+a*b-cd按層遍歷輸出：+a*h-cd按任意鍵退出…Pressanykeytocontinue一中序遞歸遍歷輸出：a+b*c-d前序遞歸遍歷輸出：+a*b-cd前序非遞歸遍歷輸出：+a*b-cd按層遍歷輸出：+a*b-cd七、附錄#defineQElemTypeBiTNodetypedefstructBiTNode{structBiTNode*#defineQElemTypeBiTNode#defineSElemTypetypedefstruct{BiThrTreepre;intCreateBiTree(BiTree&T);voidPreOrderTraverse_re(BiTreeT,void(*print)(TElemTypee);//先序遞歸遍歷二叉樹(shù)voidInOrderTraverse(BiTreeT,int(*print)(TElemTypee));//中序非遞歸遍歷二叉樹(shù)voidInOrderTraverse_re(BiTreeT,int(*print)(TElemTypee));//中序遞歸遍歷二叉樹(shù)voidPreOrderTraverse(BiTreeT,int(*print)(TElemTypee));//先序非遞歸遍歷二叉樹(shù)intprint(TElemTypee);voidInitStack(SqStack&S);voidPop(SqStack&S,SElemType&e);voidPush(SqStack&S,SElemType&e);voidInOrderThreading(BiThrTintInOrderTraverse_Thr(BiThrTreeT,int(*print)(TElemTypee));voidInThreading(BiT/*二叉樹(shù)的創(chuàng)立遞歸創(chuàng)立*/intCreateBiTree(B{if(CreateBiTree(T->lchild))T->LTag=Link;if(CreateBiTree(T->rchild))T->RTag=Link;}/************************************/*先序遞歸遍歷輸出*//************************************voidPreOrderTraverse_re(BiTreeT,int(*print)(TElemTypee))PreOrderTraverse_re(T->lchPreOrderTraverse_re(T->rchild,}}/*************************************/*中序非遞歸遍歷輸出*//*************************************voidInOrderTraverse(BiTreeT,int(*print)(TElemType{}/*******************:******************/*中序遞歸遍歷輸出*//*************************************voidInOrderTraverse_re(BiTreeT,int(*print)(TEle{InOrderTraverse_re(T->lchildInOrderTraverse_re(T->rchild}}/************************************/*按照前序非遞歸遍歷二叉樹(shù)：棧*//************************************SElemTypep=T;/p指向目前訪問(wèn)的結(jié)點(diǎn)while(pl!StackEmpty{}{}}voidInOrderThreading(BiThr//中序遍歷二叉樹(shù)T,并將其中序線索化，Thrt指向頭結(jié)點(diǎn)Thrt=(BiThrTree)malloc(sizeThrt->LTag=Link;//建頭結(jié)點(diǎn)Thrt->rchild=Thrt;//右指針回指{pre->RTag=Thread;/最終一種結(jié)點(diǎn)線索化}voidInThreading(BiTInThreading(p->lchild);//左子樹(shù)線索化if(!p->lchild)//建前驅(qū)線索if(!pre->rchild)//建后繼線索pre=p;InThreading(p->rchild);//右子樹(shù)線索化}intInOrderTraverse_Thr(BiThrT{while(p->RTag==Thread&&p->rc}}}/***************************如下為輔助函數(shù)***************************************/{}/*棧的初始化*/voidInitStack(SqStack&S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*s}voidPush(SqStack&S,SElemif(S.top-S.base>=S.s{S.base=(SElemType*)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMEN}}voidPop(SqStack&S,SElemType&e){{/*若棧為空棧，則返回OK,否則返回ERROR*/}intGetTop(SqStack{/******************************************************/*按層次次序建立一棵二叉樹(shù)*//*******************************************************voidLevelorder(BiTreeT)}BiTNode*q[20],*p;/*q[20]用于模擬隊(duì)列，存儲(chǔ)入隊(duì)的結(jié)點(diǎn)*/}/*i為隊(duì)首位置，j為隊(duì)尾位置*/if(p->lchild!=NULL)j++;}/*若隊(duì)首元素左鏈域不為空，則將其入隊(duì)列*/if(p->rchild!=NULL){j++;}/*若隊(duì)首元素右鏈域不為空，則將其入隊(duì)列*/i++;/*將隊(duì)首移到下一種位置*/{printf("***********************************************************\n");printf("**試驗(yàn)12二叉樹(shù)的遍歷**\n");printf("**1.實(shí)現(xiàn)二叉樹(shù)的不一樣遍歷算法和二叉樹(shù)的中序線索化算法**\n");printf("**a)中序遞歸遍歷算法；printf("**b)先序遞歸遍歷算法