二叉樹的非遞歸和遞歸遍歷C語言詳解

1、最易懂的二叉樹的遞歸和非遞歸實(shí)驗(yàn)代碼創(chuàng)建一顆用作實(shí)驗(yàn)的二叉樹1先根（序）遍歷2中根（序）遍歷4后根（序）遍歷5測(cè)試主函數(shù)7創(chuàng)建一顆用作實(shí)驗(yàn)的二叉樹/當(dāng)然，你要先定義一個(gè)節(jié)點(diǎn)類型typedef struct NODE int val; struct NODE* left; struct NODE* right;node_t,*node_p;/*從根節(jié)點(diǎn)開始依次安裝圖解完成樹的創(chuàng)建，葉子節(jié)點(diǎn)兩個(gè)子樹為空(null)*/node_t* CreatExTree() node_p root; root=malloc(sizeof(node_t); if(root=NULL) exit(1); root-

2、>val='A' root->left=malloc(sizeof(node_t); root->left->val='B' root->left->left=malloc(sizeof(node_t); root->left->left->val='D' root->left->left->left=NULL; root->left->left->right=NULL; root->left->right=malloc(sizeof(node_

3、t); root->left->right->val='E' root->left->right->left=NULL; root->left->right->right=NULL; root->right=malloc(sizeof(node_t); root->right->val='C' root->right->right=NULL; root->right->left=malloc(sizeof(node_t); root->right->lef

4、t->val='F' root->right->left->left=NULL; root->right->left->right=NULL; return root;當(dāng)然，這是最笨的一種生成特定二叉樹的方法先根（序）遍歷所謂先根遍歷，也就是從先遍歷根節(jié)點(diǎn)，然后遍歷左子樹，最后右子樹。遞歸的代碼非常簡(jiǎn)單：void RootFirstTrav(node_p root) /*遞歸的出口*/if(root=NULL) return;/*處理根節(jié)點(diǎn)*/printf("%c ",root->val);/*處理左右子樹*/

5、 RootFirstTrav(root->left); RootFirstTrav(root->right);/*主函數(shù)調(diào)用測(cè)試*/int main() node_p s; s=CreatExTree(); RootFirstTrav(s); return 0;遞歸調(diào)用看起來并沒什么難點(diǎn)，接下來就看看非遞歸調(diào)用的style：在給出代碼之前，先分析一下我們的循環(huán)。為了再訪問完左子樹后，還能倒回去訪問右子樹，我們不得不保存當(dāng)前的節(jié)點(diǎn)。這里用到一個(gè)叫做堆棧的數(shù)據(jù)結(jié)構(gòu)，當(dāng)然這里我們用數(shù)組模擬它。定義一個(gè)數(shù)組：#define MAX_NODE 100Node_p stacMAX_NODE=0

6、;Int topele=-1 /定義一個(gè)索引下標(biāo)過程描述：我們遇到第一個(gè)根節(jié)點(diǎn)，處理，保存第一個(gè)節(jié)點(diǎn)數(shù)組情況為A00000topele=0;我們?cè)L問A的左子樹，不為空，處理，入棧AB0000topele=1再繼續(xù)訪問左子樹，不為空，處理，入棧ABD000topele=2再繼續(xù)訪問左子樹，為空，出棧，取出棧頂元素B；AB0000topele=0處理B的右子樹E，E的左子樹不為空，不入棧，處理右子樹，為空，不入棧。再出棧，取元素A，處理A的右子樹C，C的左子樹不為空，入棧，處理C。然后，處理C的左子樹F，F(xiàn)的左右子樹為空，去棧頂元素C，處理C的右子樹，在取棧頂元素，棧為空，遍歷結(jié)束。代碼描述：vo

7、id RootFirstTrav_(node_p root) node_p stacMAX_NODE; int topele=-1; if(root=NULL) exit(1); node_p p1;p1=root;/循環(huán)出口，堆棧為空 while(p1!=NULL|topele!=-1) while(p1!=NULL) /*處理數(shù)據(jù)*/ printf("%c ",p1->val); stac+topele=p1; p1=p1->left; if(topele!=-1) p1=stactopele->right; 中根（序）遍歷遞歸比較簡(jiǎn)單就直接上遞歸的代

8、碼了void RootSecondTrav(node_p root) if(root=NULL) return; RootSecondTrav(root->left); printf("%c ",root->val); RootSecondTrav(root->right);非遞歸調(diào)用與先根不同的是根節(jié)點(diǎn)的處理時(shí)機(jī)；也就是說入棧的時(shí)候不處理，等出棧的時(shí)候在處理：void RootSecondTrav_(node_p root) node_p stacMAX_NODE; int topele=-1; if(root=NULL) exit(1); while(

9、root!=NULL | topele!=-1) while(root!=NULL) stac+topele=root; root=root->left; if(topele!=-1) root=stactopele-; printf("%c ",root->val); root=root->right; 后根（序）遍歷依然先上遞歸代碼：void RootLastTrav(node_p root) if(root=NULL) return; RootLastTrav(root->left); RootLastTrav(root->right);

10、 printf("%c ",root->val);非遞歸代碼：后序遍歷的非遞歸代碼實(shí)現(xiàn)起來最為復(fù)雜。后序遍歷的順序是，左子樹，右子樹，根節(jié)點(diǎn)。如何從右子樹到根節(jié)點(diǎn)，是一個(gè)難點(diǎn)。這里采用一個(gè)標(biāo)志位flag，來標(biāo)識(shí)訪問的次數(shù)，來區(qū)分是從左子樹，還是右邊子樹返回的。下面的表格表示一個(gè)堆棧的結(jié)構(gòu)，第一列表示stac元素，第二列表示flag元素A1 A1B1 A1B1D1 topele=2A1B1D2 A1B12 A1B2A1B2E1->2 A2C1F1->2 A2C2依次輸出void RootLastTrav_(node_p root) /*定義一個(gè)結(jié)構(gòu)體，即帶標(biāo)

11、志位的堆棧*/ typedef struct STAC node_p stac; int flag; stac_f; /*定義堆棧數(shù)組*/ stac_f StacMAX_NODE; int topele=-1; if(root=NULL) exit(1); while(root!=NULL|topele!=-1) while(root!=NULL) /*第一次遍歷根節(jié)點(diǎn)*/ topele+; Stactopele.stac=root; Stactopele.flag=1; root=root->left; /*如果元素不為空，且是第二次遍歷，則處理元素*/ while(topele!=-

12、1&&Stactopele.flag=2) root=Stactopele-.stac; printf("%c ",root->val); if(topele!=-1) Stactopele.flag=2; root=Stactopele.stac->right; 測(cè)試主函數(shù)int main() node_p s; printf("創(chuàng)建實(shí)驗(yàn)二叉樹n"); s=CreatExTree(); printf("n"); printf("先序遍歷n"); RootFirstTrav(s); putchar(10); RootFirstTrav_(s); putchar(10); printf("中序遍歷n"); RootSecondTrav(s)