用遞歸非遞歸兩種方法遍歷二叉樹(shù)

1、WORD格式實(shí)用文檔數(shù)據(jù)構(gòu)造雙語(yǔ)工程文檔報(bào)告用遞歸、非遞歸兩種方法遍歷二叉樹(shù)專(zhuān)業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)：指導(dǎo)教師：XX：專(zhuān)業(yè)資料整理WORD格式標(biāo)準(zhǔn)文案專(zhuān)業(yè)資料整理WORD格式實(shí)用文檔學(xué)號(hào)：目錄一、設(shè)計(jì)思想.03二、算法流程圖.04三、源代碼.06四、運(yùn)行結(jié)果.12五、遇到的問(wèn)題及解決.14六、心得體會(huì).15專(zhuān)業(yè)資料整理WORD格式標(biāo)準(zhǔn)文案專(zhuān)業(yè)資料整理WORD格式實(shí)用文檔一、設(shè)計(jì)思想1遞歸：1主函數(shù) main主程序要包括：定義的二叉樹(shù)T、建樹(shù)函數(shù)、先序遍歷函數(shù)、中序遍歷函數(shù)、后序遍歷函數(shù)。2建樹(shù)函數(shù)定義一個(gè)輸入的數(shù)是字符型的，當(dāng)ch 為空時(shí)， T 就為空值，否那么的話(huà)就分配空間給 T， T 就

2、指向它的結(jié)點(diǎn)，然后左指針域指向左孩子，右指針指向右孩子，假設(shè)還有，繼續(xù)調(diào)用 , 依次循環(huán)下去，直到 ch 遇到空時(shí)，完畢。最后要返回建立的二叉樹(shù) T。3先序遍歷函數(shù)根據(jù)先序遍歷規(guī)那么，當(dāng) T 為非空時(shí)，先輸出結(jié)點(diǎn)處的數(shù)據(jù)，指針指向左、右孩子，依次進(jìn)展下去。(4) 中序遍歷函數(shù)根據(jù)中序遍歷規(guī)那么，當(dāng) T 為非空時(shí)，先左指針指向左孩子數(shù)據(jù)，然后輸出結(jié)點(diǎn)處的數(shù)據(jù)，再右指針指向右孩子，依次進(jìn)展下去。(5 后序遍歷函數(shù)根據(jù)后序遍歷規(guī)那么，當(dāng) T 為非空時(shí)，先右指針指向右孩子，然后左指針指向左孩子，最后輸出結(jié)點(diǎn)處的數(shù)據(jù)，依次進(jìn)展下去。2. 非遞歸：1跟遞歸遍歷二叉樹(shù)的前提一樣，首先應(yīng)該創(chuàng)立一個(gè)二叉樹(shù)，同樣

3、使用先序遞歸的方式創(chuàng)立二叉樹(shù)。2然后是中序，先序，后序非遞歸遍歷二叉樹(shù)。3中序非遞歸遍歷二叉樹(shù)的思想是：首先是根節(jié)點(diǎn)壓棧，當(dāng)根節(jié)點(diǎn)的左子樹(shù)不是空的時(shí)候，左子樹(shù)壓棧。直到左子樹(shù)為空的時(shí)候，不再壓棧。將棧頂元素出棧，訪問(wèn)棧頂元素，并將棧頂?shù)挠易訕?shù)進(jìn)棧。當(dāng)右子樹(shù)的左子樹(shù)不是空的時(shí)候，左子樹(shù)一直進(jìn)棧，直到左子樹(shù)為空，那么不再進(jìn)棧。重復(fù)上面的操作，直到?？盏臅r(shí)候。(4) 先序非遞歸遍歷二叉樹(shù)的思想是：首先是根節(jié)點(diǎn)進(jìn)棧，然后當(dāng)棧不為空的時(shí)候，將棧頂元素出棧，然后訪問(wèn)。同時(shí)將出棧元素的右子樹(shù)進(jìn)棧，左子樹(shù)進(jìn)棧。重復(fù)上面的操作，直到棧為空。(5 后序非遞歸遍歷二叉樹(shù)的思想：首先是根節(jié)點(diǎn)進(jìn)棧，當(dāng)根節(jié)點(diǎn)的左子樹(shù)不為

4、空的時(shí)候，左子樹(shù)進(jìn)棧，直到左為空的時(shí)候，左子樹(shù)不再進(jìn)棧。指針指向的是右子樹(shù)，當(dāng)右子樹(shù)為空的時(shí)候，直接訪問(wèn)根節(jié)點(diǎn)。當(dāng)右子樹(shù)不為空的時(shí)候，那么右子樹(shù)的指針進(jìn)棧，當(dāng)右子樹(shù)的左子樹(shù)不為空的時(shí)候，那么左也進(jìn)棧，直到左為空。重復(fù)上面的操作，直到棧為空的時(shí)候，那么遍歷樹(shù)完成。專(zhuān)業(yè)資料整理WORD格式標(biāo)準(zhǔn)文案專(zhuān)業(yè)資料整理WORD格式實(shí)用文檔二、算法流程圖1. 遞歸專(zhuān)業(yè)資料整理WORD格式標(biāo)準(zhǔn)文案專(zhuān)業(yè)資料整理WORD格式實(shí)用文檔2. 非遞歸專(zhuān)業(yè)資料整理WORD格式標(biāo)準(zhǔn)文案專(zhuān)業(yè)資料整理WORD格式實(shí)用文檔三、源代碼1. 遞歸#include "stdio.h"#include "co

5、nio.h"#include <stdlib.h>#include<stack>typedef struct nodechar data;struct node *lchild, *rchild;BinTnode;typedef BinTnode * BinTree; /定義二叉樹(shù)類(lèi)型的指針/* 先序創(chuàng)立二叉樹(shù)*/int CreateBinTree(BinTree *T)char ch;*T=(BinTree)malloc(sizeof(BinTnode);if(!*T) printf("overflow");doch=getchar();

6、if(ch=' ') *T=NULL; return 0;else(*T)->data=ch;CreateBinTree(&(*T)->lchild);CreateBinTree(&(*T)->rchild);return 1;while(ch!='0');/* 中序遞歸遍歷*/void InorderTransverse(BinTree s)if (s)專(zhuān)業(yè)資料整理WORD格式標(biāo)準(zhǔn)文案專(zhuān)業(yè)資料整理WORD格式實(shí)用文檔InorderTransverse(s->lchild);printf("%c", s

7、->data);InorderTransverse(s->rchild);/ 先序遞歸遍歷二叉樹(shù)void PreOrderTranverseTree(BinTree s)if (s)printf("%c", s->data);PreOrderTranverseTree(s->lchild);PreOrderTranverseTree(s->rchild);/ 后序遞歸遍歷二叉樹(shù)void PostOrderTranverseTree(BinTree s)if (s)PreOrderTranverseTree(s->lchild);PreOr

8、derTranverseTree(s->rchild);printf("%c", s->data);/* 主方法 */void main()BinTreeT;printf("請(qǐng)按照先序的順序輸入要?jiǎng)?chuàng)立的樹(shù):n");CreateBinTree(&T); /*中序序列創(chuàng)立二叉樹(shù)*/printf("中序遞歸遍歷的序列是:");InorderTransverse(T);printf("n");/ 先序遞歸遍歷printf("先序遞歸遍歷的序列是:");PreOrderTranvers

9、eTree(T);printf("n");/ 后序遞歸遍歷printf("后序遞歸遍歷的序列是:");PostOrderTranverseTree(T);printf("n");專(zhuān)業(yè)資料整理WORD格式標(biāo)準(zhǔn)文案專(zhuān)業(yè)資料整理WORD格式實(shí)用文檔2. 非遞歸#include "stdio.h"#include "conio.h"#include <stack>#include <stdlib.h>typedef struct nodechar data;struct node

10、 *lchild, *rchild;BinTnode;typedef BinTnode * BinTree; / 定義二叉樹(shù)類(lèi)型的指針 typedef structBinTree data100;int top;SeqStack;void initStack(SeqStack *S)S->top =-1;void Push(SeqStack *S,BinTree x)if(S->top=100-1)printf("the stack is overflow");else S->top=S->top+1;S->dataS->top=x;in

11、t Pop(SeqStack *S,BinTree *p)if(S->top=-1)printf("the stack is underflow");return 0;else *p=S->dataS->top;-S->top;return 1;專(zhuān)業(yè)資料整理WORD格式標(biāo)準(zhǔn)文案專(zhuān)業(yè)資料整理WORD格式實(shí)用文檔int EmptyStack(SeqStack S)if(S.top=-1) return 1;else return 0; /*棧不空的情況*/int GetTop(SeqStack S,BinTree *p)if(S.top=-1)print

12、f("the stack is empty");return 0;else *p=S.dataS.top;return 1;char visit(BinTree p)return (*p).data;/* 創(chuàng)立二叉樹(shù) */int CreateBinTree(BinTree *T)char ch;*T=(BinTree)malloc(sizeof(BinTnode);if(!*T) printf("overflow");elsedoch=getchar();if(ch!=' ')*T=NULL;return 0;else(*T)->d

13、ata=ch;CreateBinTree(&(*T)->lchild);CreateBinTree(&(*T)->rchild);return 1;while(ch!='0');/* 中序非遞歸遍歷*/void InorderTransverse(BinTree T)SeqStack S;BinTreep;initStack(&S);/初始化棧printf("中序非遞歸序列是:");專(zhuān)業(yè)資料整理WORD格式標(biāo)準(zhǔn)文案專(zhuān)業(yè)資料整理WORD格式實(shí)用文檔Push(&S,T); /根指針進(jìn)棧T為指向二叉樹(shù)的指針while(!

14、EmptyStack(S)/棧不是空的情況while(GetTop(S,&p) && p)Push(&S,p->lchild);/gettop得到的結(jié)果也必須是一棵子樹(shù)才行, 進(jìn)棧應(yīng)該進(jìn)的是樹(shù)根的指針Pop(&S,&p);if(!EmptyStack(S)/printf("%c",visit(p);Pop(&S,&p);printf("%c",visit(p);Push(&S,p->rchild);/* 先序非遞歸遍歷*/void PreorderTransverse(B

15、inTree T)SeqStack S;BinTreep;initStack(&S);/初始化棧Push(&S,T); /根指針進(jìn)棧T為指向二叉樹(shù)的指針printf("先序非遞歸序列是:");while(!EmptyStack(S)Pop(&S,&p);/根節(jié)點(diǎn)出棧if(p!=NULL)printf("%c",visit(p);Push(&S,p->rchild);Push(&S,p->lchild);/* 后序非遞歸遍歷*/void PostorderTransverse(BinTree T)

16、SeqStack S;BinTreep,q;initStack(&S);/初始化棧p=T;printf("后序非遞歸序列是:");while(p |!EmptyStack(S)/跳出while循環(huán)的原因是因?yàn)樽笞訕?shù)或者右子樹(shù)為空了if(p!=q)while(p!=NULL)Push(&S,p);if(p->lchild!=NULL)p=p->lchild;elsep=p->rchild;專(zhuān)業(yè)資料整理WORD格式標(biāo)準(zhǔn)文案專(zhuān)業(yè)資料整理WORD格式實(shí)用文檔if(EmptyStack(S) break;GetTop(S,&q);if(q-&

17、gt;rchild=p)/進(jìn)棧的是右子樹(shù)Pop(&S,&p);printf("%c",visit(p);p=q;elsep=q->rchild;/* 主方法 */void main()BinTreeT;printf("請(qǐng)按照先序的順序輸入創(chuàng)立的樹(shù):n");/* 創(chuàng)立樹(shù) */CreateBinTree(&T);/ 中序非遞歸遍歷InorderTransverse(T);printf("n");/ 先序非遞歸遍歷PreorderTransverse(T);printf("n");/ 后序非

18、遞歸遍歷PostorderTransverse(T);四、運(yùn)行結(jié)果1. 遞歸輸入專(zhuān)業(yè)資料整理WORD格式標(biāo)準(zhǔn)文案專(zhuān)業(yè)資料整理WORD格式實(shí)用文檔結(jié)果2. 非遞歸輸入專(zhuān)業(yè)資料整理WORD格式標(biāo)準(zhǔn)文案專(zhuān)業(yè)資料整理WORD格式實(shí)用文檔結(jié)果五、遇到的問(wèn)題及解決經(jīng)過(guò)一個(gè)星期的寫(xiě)代碼，我遇到了很多問(wèn)題，并一一解決了，比方：1.創(chuàng)立二叉樹(shù)時(shí)： void createBiTree(BiTNode*T) 和 void createBiTree(BiTNode*&T)沒(méi)分清楚區(qū)別。后來(lái)查找資料找到void createBiTree(BiTNode *T)是將結(jié)點(diǎn)的指針地址傳遞到函數(shù)中進(jìn)展處理void createBiTree(BiTNode *&T是將結(jié)點(diǎn)指針的引用傳遞到函數(shù)處理。才理解清楚。專(zhuān)業(yè)資料整理WORD格式標(biāo)