數(shù)據(jù)結(jié)構(gòu)二叉樹的遞歸算法實驗報告

1、.齊魯工業(yè)大學實驗報告 成績 課程名稱 數(shù)據(jù)結(jié)構(gòu) 指導教師 單健芳 實驗日期 院（系） 信息學院 專業(yè)班級 計科（嵌入）14-1 實驗地點 學生姓名 高晨悅 學號 2 同組人 無 實驗項目名稱 二叉樹的遞歸算法 一、實驗目的和要求1.實現(xiàn)二叉樹的先序，中序與后序遍歷的遞歸算法與非遞歸算法。2.求二叉樹的結(jié)點個數(shù)，葉子結(jié)點個數(shù)，二叉樹的高度，度為2的結(jié)點個數(shù)。二、實驗環(huán)境 微型計算機vc 6.0三、實驗內(nèi)容1.實現(xiàn)二叉樹的先序，中序與后序遍歷的遞歸算法與非遞歸算法。2.求二叉樹的結(jié)點個數(shù)，葉子結(jié)點個數(shù)，二叉樹的高度，度為2的結(jié)點個數(shù)。四、實驗步驟一實驗內(nèi)容1.實現(xiàn)二叉樹的先序，中序與后序遍歷的遞

2、歸算法與非遞歸算法。2.求二叉樹的結(jié)點個數(shù)，葉子結(jié)點個數(shù)，二叉樹的高度，度為2的結(jié)點個數(shù)。二程序的設計思想1實現(xiàn)二叉樹的先序，中序與后序遍歷的遞歸算法與非遞歸算法。先構(gòu)造二叉樹，根據(jù)先序遍歷的思想，輸入根后，再輸入左子樹，直至左子樹為空則輸入上一層右字樹。（1）二叉樹的非遞歸遍歷是用顯示棧來存儲二叉樹的結(jié)點指針，先序遍歷時，按二叉樹前序遍歷的順序訪問結(jié)點，并將結(jié)點的指針入棧，直到棧頂指針指向結(jié)點的左指針域為空時取出棧頂指針并刪除棧頂指針，訪問剛?cè)〕龅闹羔樦赶虻慕Y(jié)點的右指針指向的結(jié)點并將其指針入棧，如此反復執(zhí)行則為非遞歸操作。（2）二叉樹的遞歸遍歷：若二叉樹為空，則空操作先序遍歷：（a）訪問根結(jié)

3、點； （b）先序遍歷左子樹；（c）先序遍歷右子樹。中序遍歷 ：（a）中序遍歷左子樹； （b）訪問根結(jié)點；（c）中序遍歷右子樹后序遍歷： （a）后序遍歷左子樹； （b）后序遍歷右子樹； （c）訪問根結(jié)點。2.求二叉樹的結(jié)點個數(shù)，葉子結(jié)點個數(shù)，二叉樹的高度，度為2的結(jié)點個數(shù)。（1）求二叉樹的葉子結(jié)點個數(shù)：先分別求得左右子樹中個葉子結(jié)點的個數(shù)，再計算出兩者之和即為二叉樹的葉子結(jié)點數(shù)。（2）二叉樹的結(jié)點個數(shù)之和：先分別求得左子樹右子樹中結(jié)點之和，再計算兩者之和即為所求。（3）二叉樹的高度：首先判斷二叉樹是否為空，若為空則此二叉樹高度為0,。否則，就先分別求出左右子樹的深度進行比較，取較大的樹加一即為所

4、求。（4）二叉樹的度為2的結(jié)點個數(shù)：計算有左右孩子的結(jié)點個數(shù)，即為度為2的結(jié)點個數(shù)。三編程過程中遇到的問題及解決辦法（1）后續(xù)遍歷的非遞歸函數(shù)涉及到回溯的方法，開始設計的方案想的太過于簡單，所以形成了死循環(huán)，總是在最后的節(jié)點處不停地循環(huán)，后改成回溯后，該問題得到解決。（2）計算二叉樹中度為2的結(jié)點個數(shù)中，返回循環(huán)的時候不論根結(jié)點有沒有左右子樹，但個人設計時，根總是會將自己默認為有左右子樹，自行增加1.后在同學幫助下才看到自己的這個失誤。四程序的閃光點(自我評價)1.程序模塊化，各個函數(shù)分開描述，方便觀察2.關鍵處有注釋3.建立二叉樹時，用先序提示輸入，比較人性化。 五程序源代碼(以文件為單位提

5、供)#include#include#define Maxsize 100typedef struct TREEstruct TREE *lTree;struct TREE *rTree;char data;Tree;void InitTree(Tree*);/初始化樹void CreatTree(Tree*);/創(chuàng)建二叉樹void PreTraverse(Tree*);/先序遍歷遞歸void PreOrderTraverse(Tree*);/先序遍歷非遞歸void InTraverse(Tree *tree);/中序遍歷遞歸void InOrderTraverse(Tree *tree);/

6、中序遍歷非遞歸void PostTraverse(Tree *tree);/后序遍歷遞歸void LastOrderTraverse(Tree *tree);/后序遍歷非遞歸int DepthTree(Tree *tree);/計算樹的深度int LeafsTree(Tree *tree);/計算葉子結(jié)點個數(shù)int NodesTree(Tree *tree);/計算結(jié)點個數(shù)int Twochild(Tree*tree);/計算度為二的結(jié)點個數(shù)void main()int H,L;Tree tree;/Tree m;InitTree(&tree);CreatTree(&tree);cout先序遍

7、歷遞歸為:;PreTraverse(&tree);/先序遍歷遞歸cout先序遍歷非遞歸:;PreOrderTraverse(&tree);/先序遍歷非遞歸coutendl;cout中序遍歷遞歸為:;InTraverse(&tree);/中序遍歷遞歸cout中序遍歷非遞歸:;InOrderTraverse(&tree);/中序遍歷非遞歸coutendl;cout后序遍歷遞歸為:;PostTraverse(&tree);/后序遍歷遞歸cout后序遍歷非遞歸:;LastOrderTraverse(&tree);/后序遍歷非遞歸coutendl; cout樹的深度為:; H=DepthTree(&tr

8、ee);coutHendl;cout葉子結(jié)點個數(shù):;L=LeafsTree(&tree); coutLendl;cout結(jié)點個數(shù)：;coutNodesTree(&tree)endl;cout度為二的結(jié)點個數(shù);L=Twochild(&tree);coutLlTree=NULL;tree-rTree=NULL;tree-data=0;void CreatTree(Tree *tree)/創(chuàng)建樹int n=0,m=0,i=0;if(tree-data=0)couttree-data;cout節(jié)點datan;if(n=1)Tree *lTree=(Tree*)malloc(sizeof(Tree);t

9、ree-lTree=lTree;lTree-lTree=NULL;lTree-rTree=NULL;lTree-data=0;CreatTree(tree-lTree);cout節(jié)點datai;if(i=0);else if(i=1)Tree *rTree=(Tree*)malloc(sizeof(Tree);tree-rTree=rTree;rTree-lTree=NULL;rTree-rTree=NULL;rTree-data=0;CreatTree(tree-rTree);else if(n=0)cout節(jié)點datam; if(m=0);else if(m=1)Tree *rTree=(

10、Tree*)malloc(sizeof(Tree);tree-rTree=rTree;rTree-lTree=NULL;rTree-rTree=NULL;rTree-data=0;CreatTree(tree-rTree);void PreTraverse(Tree*tree)/先序遍歷遞歸if(tree!=NULL)coutdatalTree!=NULL)PreTraverse(tree-lTree);PreTraverse(tree-rTree);else if(tree-rTree!=NULL)PreTraverse(tree-rTree);else;void PreOrderTrave

11、rse(Tree *tree)/先序遍歷非遞歸Tree *S80=NULL;int top =0;while (tree!=NULL)|(top)if (tree!=NULL)coutdatalTree;elsetree = Stop;top-;tree = tree-rTree;void InTraverse(Tree *tree)/中序遍歷遞歸if(tree!=NULL)if(tree-lTree!=NULL)InTraverse(tree-lTree);coutdatarTree);else if(tree-rTree!=NULL)coutdatarTree);elsecoutdatal

12、Tree;elsetree = Dtop;top-;coutdatarTree;void PostTraverse(Tree *tree)/后序遍歷遞歸if(tree!=NULL)if(tree-lTree!=NULL)PostTraverse(tree-lTree);PostTraverse(tree-rTree);coutdatarTree!=NULL)PostTraverse(tree-rTree);coutdata ;elsecoutdatalTree;if(top!=0)p=stacktop-rTree;if(p=NULL)coutdatarTree!=NULL)if(stackto

13、p-rTree-data=stacktop+1-data)coutdatarTree;elsep=NULL;int DepthTree(Tree *tree) /深度函數(shù) int u,v; if (tree=NULL) return 0; u=DepthTree(tree-lTree); v=DepthTree(tree-rTree); if (uv) return (u+1); return (v+1); int LeafsTree(Tree *tree)/子葉個數(shù)函數(shù) int num1,num2; if(tree=NULL) return 0; else if(tree-lTree=NUL

14、L&tree-rTree=NULL) return 1; else num1=LeafsTree(tree-lTree); num2=LeafsTree(tree-rTree); return(num1+num2); int NodesTree(Tree *tree)/結(jié)點個數(shù)函數(shù) int num1,num2; if(tree=NULL) return 0; if(tree-lTree=NULL&tree-rTree=NULL) return 1; else num1=NodesTree(tree-lTree); num2=NodesTree(tree-rTree); return(num1+num2+1); int Twochild(Tree*tree)/度為2的 int n=0; if(tre