數(shù)據(jù)結(jié)構(gòu)課設(shè)二叉樹的遍歷

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計說明書題目：二叉樹的遍歷學(xué)生姓名：學(xué)號：院 （系）：專業(yè)：指導(dǎo)教師：年 月日目 錄1需求分析 .02概要設(shè)計 .02.1功能設(shè)計 . .02.2算法流程圖 . .13詳細(xì)設(shè)計 .23.1創(chuàng)建二叉樹 . .23.2二叉樹的遞歸遍歷算法 . .13.3二叉樹的層次遍歷算法 . .23.4二叉樹的非遞歸遍歷算法 . .24測試數(shù)據(jù)與分析 .35算法分析 .96總結(jié).9參 考 文 獻(xiàn) .9附錄 .101 需求分析數(shù)據(jù)結(jié)構(gòu)是信息類專業(yè)最重要的專業(yè)基礎(chǔ)課程，掌握好數(shù)據(jù)結(jié)構(gòu)的知識將直接關(guān)系到后續(xù)專業(yè)課程的學(xué)習(xí)。數(shù)據(jù)結(jié)構(gòu)研究四個方面的問題：（ 1）數(shù)據(jù)的邏輯結(jié)構(gòu)，即數(shù)據(jù)之間的邏輯關(guān)系；（ 2）

2、數(shù)據(jù)的物理結(jié)構(gòu)，即數(shù)據(jù)在計算機(jī)內(nèi)的存儲方式；（ 3）對數(shù)據(jù)的加工，即基于某種存儲方式的操作算法；（ 4）算法的分析；即評價算法的優(yōu)劣。本實驗是用鏈?zhǔn)酱鎯Y(jié)構(gòu)來存儲二叉樹并進(jìn)行一系列的算法，且結(jié)點內(nèi)容的數(shù)據(jù)類型為字符型。根據(jù)題目知，程序主要是根據(jù)給定二叉樹的先序遍歷結(jié)果， 構(gòu)造出二叉樹并輸出按中，后序遍歷的結(jié)果，以及求二叉樹的葉子個數(shù)等。其中二叉樹的結(jié)點用字符表示。（ 1）創(chuàng)建二叉樹：按先序次序輸入，構(gòu)造二叉鏈表表示的二叉樹。（ 2）設(shè)計算法：先序遍歷 , 中序遍歷 , 后序遍歷。（ 3）編寫程序：設(shè)計 main() 函數(shù)調(diào)用以上步驟實現(xiàn)相關(guān)功能。本程序用Microsoft Visual Stu

3、dio 2008編寫，可以實現(xiàn)各種二叉樹的遍歷。包括先序遍歷、中序遍歷、后序遍歷的遞歸算法，先序遍歷、中序遍歷、后序遍歷的非遞歸算法以及能查找任一結(jié)點在某種遍歷序列中的前驅(qū)和后繼。2 概要設(shè)計2.1功能設(shè)計（ 1）typedef struct BTNode 定義二叉樹定義一個用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲的二叉樹，其中包括左孩子和右孩子以及數(shù)據(jù)元素的內(nèi)容。和單鏈表類似，一個二叉鏈表由頭指針唯一確定，若二叉樹為空，則頭指針指向空。并且結(jié)點內(nèi)容的數(shù)據(jù)類型為字符型。（ 2）CreateBiTree(BiTree &T) 構(gòu)建二叉樹此函數(shù)的功能是構(gòu)建二叉樹。 從鍵盤上按先序次序輸入字符構(gòu)造二叉鏈表表示的二

4、叉樹 T，其中用星號表示空樹 。（ 3）NRPreOrder(BiTree bt) 先序遍歷（非遞歸）此函數(shù)的功能是用非遞歸的方法實現(xiàn)二叉樹的先序遍歷算法。調(diào)用此函數(shù)可以獲得二叉樹的非遞歸的先序遍歷的結(jié)果。（ 4）NRInOrder(BiTree bt) 中序遍歷（非遞歸）此函數(shù)的功能是用非遞歸的方法實現(xiàn)二叉樹的中序遍歷算法。調(diào)用此函數(shù)可以獲得二叉樹的非遞歸的中序遍歷的結(jié)果。（ 5）NRPostOrder(BiTree bt) 后序遍歷（非遞歸）此函數(shù)的功能是用非遞歸的方法實現(xiàn)二叉樹的后序遍歷算法。調(diào)用此函數(shù)可以獲得二叉樹的非遞歸的后序遍歷的結(jié)果。其中 bt 是要遍歷樹的根指針，后序遍歷要求在

5、遍歷完左右子樹后，再訪問根。需要判斷根結(jié)點的左右子樹是否均遍歷過?？刹捎脴?biāo)記法，結(jié)點入棧時，配一個標(biāo)志 tag 一同入棧 1：遍歷左子樹的現(xiàn)場保護(hù)， 2：遍歷右子樹前的現(xiàn)場保護(hù)。首先將 bt 和 tag( 為 1) 入棧，遍歷左子樹；返回后，修改棧頂 tag 為 2，遍歷右子樹；最后訪問根結(jié)點。（ 6）PreOrderTraverse(BiTree T) 先序遍歷（遞歸）函數(shù)功能是用遞歸的方法對二叉樹進(jìn)行先序遍歷，調(diào)用此函數(shù)可以獲得二叉樹的遞歸的先序遍歷的結(jié)果。（ 7）InOrderTraverse(BiTree T) 中序遍歷（遞歸）函數(shù)功能是用遞歸的方法對二叉樹進(jìn)行中序遍歷，調(diào)用此函數(shù)可以

6、獲得二叉樹的遞歸的中序遍歷的結(jié)果。（ 8）PostOrderTraverse(BiTree T) 后序遍歷（遞歸）函數(shù)功能是用遞歸的方法對二叉樹進(jìn)行后序遍歷，調(diào)用此函數(shù)可以獲得二叉樹的遞歸的后序遍歷的結(jié)果。（ 9）main()主函數(shù)用 while() 與 switch(select) 語句對二叉樹的操作的算法進(jìn)行了設(shè)計?？梢詫崿F(xiàn)以上函數(shù)的功能，并能退出程序。2.2算法流程圖算法流程圖如圖1 所示 。圖 2-1算法流程圖3 詳細(xì)設(shè)計3.1 創(chuàng)建二叉樹(1) 定義二叉樹結(jié)點值的類型為字符型。(2) 結(jié)點個數(shù)不超過 10 個。(3) 按先序次序輸入，構(gòu)造二叉鏈表表示的二叉樹 T，空格表示空樹。3.2

7、 二叉樹的遞歸遍歷算法DLR(1) 訪問根結(jié)點。(2) 先序遍歷根結(jié)點的左子數(shù)。(3) 先序遍歷根結(jié)點的右子數(shù)。LDR(1) 先序遍歷根結(jié)點的左子數(shù)。(2) 訪問根結(jié)點。(3) 先序遍歷根結(jié)點的右子數(shù)。LRD(1) 先序遍歷根結(jié)點的左子數(shù)。(2) 先序遍歷根結(jié)點的右子數(shù)。(3) 訪問根結(jié)點。3.3 二叉樹的層次遍歷算法(1) 訪問該元素所指結(jié)點。(2) 若該元素所指結(jié)點的左右孩子結(jié)點非空，則該元素所指結(jié)點的左孩子指針和右孩子指針順序入隊。3.4 二叉樹的非遞歸遍歷算法（ 1）非遞歸的先序遍歷算法 a. 訪問結(jié)點的數(shù)據(jù)域。b. 指針指向 p 的左孩子結(jié)點。 c. 從棧中彈出棧頂元素。d. 指針指

8、向 p 的右孩子結(jié)點。（ 2）非遞歸的中序遍歷算法a. 指針指向 p 的左孩子結(jié)點。b. 從棧中彈出棧頂元素。c. 訪問結(jié)點的數(shù)據(jù)域。d. 指針指向 p 的右孩子結(jié)點。（ 3）非遞歸的后序遍歷算法bt 是要遍歷樹的根指針，后序遍歷要求在遍歷完左右子樹后，再訪問根。需要判斷根結(jié)點的左右子樹是否均遍歷過?？刹捎脴?biāo)記法，結(jié)點入棧時，配一個標(biāo)志 tag 一同入棧(1 ：遍歷左子樹前的現(xiàn)場保護(hù)。 2：遍歷右子樹前的現(xiàn)場保護(hù) ) 。首先將 bt 和 tag( 為 1) 入棧，遍歷左子樹；返回后，修改棧頂 tag 為 2，遍歷右子樹；最后訪問根結(jié)點。4 測試數(shù)據(jù)與分析（ 1）運行程序，進(jìn)入開始界面圖 4-1

9、開始運行（ 2）選擇 1，創(chuàng)建二叉樹圖 4-2創(chuàng)建二叉樹(3) 選擇 2，顯示遞歸 - 中序遍歷二叉樹圖 4-3 遞歸 - 中序遍歷二叉樹（ 4）選擇 3，遞歸 - 前序遍歷二叉樹圖 4-4 遞歸 - 前序遍歷二叉樹（ 5）選擇 4，遞歸 - 后序遍歷二叉樹圖 4-5 遞歸 - 后序遍歷二叉樹（ 6）選擇 5，非遞歸 - 后序遍歷二叉樹圖 4-6非遞歸 - 后序遍歷二叉樹（ 7）選擇 6，層次遍歷二叉樹圖 4-7層次遍歷二叉樹（ 8）選擇 7，計算二叉樹的高度圖 4-8 二叉樹的高度（ 9）選擇 8，計算二叉樹的結(jié)點的個數(shù)圖 4-9 二叉樹的結(jié)點的個數(shù)（ 10）選擇 9，計算二叉樹的葉子結(jié)點個

10、數(shù)圖 4-10二叉樹的葉子結(jié)點個數(shù)（ 11）選擇 10，交換二叉樹的所有子樹圖 4-11交換二叉樹的所有子樹（ 12）選擇 0，則退出系統(tǒng)5 算法分析本程序按遞歸遍歷所耗費的時間復(fù)雜度為O（n），其所耗費的空間復(fù)雜度也為O（n）。6 總結(jié)這次課程設(shè)計，雖然看起來很簡單，但是真的做起來的時候就發(fā)現(xiàn)了困難重重，讓我深刻的體會到了要用 C 語言做一個二叉樹的遍歷，里面需要的很多知識還是我們沒有接觸過的，所以我們需要不斷的實踐，不斷的學(xué)習(xí)，不斷的發(fā)現(xiàn)問題去思考問題。通過此這次課程設(shè)計，我掌握了二叉樹的存儲實現(xiàn)，掌握了二叉樹的遍歷思想，掌握了二叉樹的常見算法的程序?qū)崿F(xiàn)。二叉樹的高度（深度）為二叉樹中結(jié)點

11、層次的最大值，也可視為其左右字?jǐn)?shù)高度的最大值加一。遍歷二叉樹的問題可以分解成兩步，第一步是求出某種遍歷次序下第一個被訪問的結(jié)點，然后連續(xù)求出剛訪問結(jié)點的后繼結(jié)點，直至所有的結(jié)點均被訪問。參考文獻(xiàn)1 張銘 . 數(shù)據(jù)結(jié)構(gòu)與算法 . 北京：高等教育出版社， 20082 耿國華編 . 數(shù)據(jù)結(jié)構(gòu)用 C 語言描述 M. 北京：高等教育出版社， 2011.63 譚浩強著 .C+面向?qū)ο笤O(shè)計 M. 北京：清華大學(xué)出版社， 2004.64 譚浩強著 .C+程序設(shè)計 M. 北京：清華大學(xué)出版社， 2004.6附錄源程序代碼#include<stdio.h>#include<malloc.h>

12、;#defineMAXSIZE 100typedefchar DataType;typedefstructBiTNode/*二叉鏈表存儲結(jié)構(gòu)*/DataType data;structBiTNode *lchild,*rchild;BiTree;typedefBiTree* ElemType ;/*棧中數(shù)據(jù)元素類型，棧中保存結(jié)點指針*/typedefstructElemType dataMAXSIZE; int top;SeqStack;/*棧的類型定義，順序棧*/typedefstructElemType queueMAXSIZE;intfront,rear;SP;SeqStack *ini

13、tSeqStack()/*初始化棧 */SeqStack *s;/*首先建立?？臻g，然后初始化棧頂指針*/s=(SeqStack*)malloc(sizeof (SeqStack);s->top=-1;returns;intpush(SeqStack *s,ElemType x)if (s->top=MAXSIZE-1) /* 棧滿不能入棧 */ printf( " 棧滿 " );return0;s->top+;s->datas->top=x;return1;voidpop(SeqStack *s)/*出棧，假設(shè)棧不空*/s->top-;

14、 intempty(SeqStack *s)if (s->top=-1)return1;elsereturn0;ElemType top(SeqStack *s)/*設(shè)棧不空 */return (s->datas->top);/*遞歸算法創(chuàng)建二叉鏈表*/BiTree *createBiTree()精選范本 ,供參考！DataType ch;BiTree *T;ch=getchar();if (ch= '0' )returnNULL;else T=(BiTree *)malloc(sizeof(BiTree);T->data=ch;T->lchild

15、=createBiTree();T->rchild=createBiTree();returnT; /*中序遍歷二叉樹的遞歸算法*/voidInOrder(BiTree *T)if (T)InOrder(T->lchild);printf("%c" ,T->data);InOrder(T->rchild);/*前序遍歷二叉樹的遞歸算法*/voidPreOrder(BiTree *T)if (T)printf("%c" ,T->data);PreOrder(T->lchild);PreOrder(T->rchild

16、);/*后序遍歷二叉樹的遞歸算法*/voidPostOrder (BiTree *T)if (T)PostOrder(T->lchild); PostOrder(T->rchild);printf("%c" ,T->data);/*中序遍歷二叉樹的非遞歸算法*/voidInOrderFei(BiTree *p)SeqStack *s; s=initSeqStack(); while (1)while (p) push(s,p); p=p->lchild;/*先將結(jié)點指針壓棧，待出棧時再訪問*/if (empty(s)break ;p=top(s);

17、pop(s); printf("%c",p->data); p=p->rchild;/*按層次遍歷 */voidLevelOrder(BiTree *T) SP *p;精選范本 ,供參考！p=(SP*)malloc(sizeof (SP);p->front=0;p->rear=0;if (T!=NULL)p->queuep->front=T;p->front=p->front+1;while (p->front!=p->rear)T=p->queuep->rear;p->rear=p->re

18、ar+1;printf("%c" ,T->data);if (T->lchild!=NULL)p->queuep->front=T->lchild;/* 左孩子進(jìn)隊列 */p->front=p->front+1;if (T->rchild!=NULL)p->queuep->front=T->rchild;/* 右孩子進(jìn)隊列 */p->front=p->front+1; /*求二叉樹的高度*/intheight(BiTree *T)int i,j;if (!T)return0;i=height(T-

19、>lchild);/*求左子樹的高度*/j=height(T->rchild);/*求右子樹的高度*/returni>j?i+1:j+1;/*二叉樹的高度為左右子樹中較高的高度加*/*求二叉樹的所有結(jié)點個數(shù)*/intNodes(BiTree *T)intn1,n2;if (T=NULL) return0;elseif (T->lchild=NULL&&T->rchild=NULL)return1;elsen1=Nodes(T->lchild);n2=Nodes(T->rchild);returnn1+n2+1; /*求二叉樹的葉子結(jié)點個

20、數(shù)*/intleafs(BiTree *T)intnum1,num2;if (T=NULL) return0;else if (T->lchild=NULL&&T->rchild=NULL)return1;num1=leafs(T->lchild);/*求左子樹中葉子結(jié)點數(shù)*/num2=leafs(T->rchild);/*求右子樹中葉子結(jié)點數(shù)*/returnnum1+num2; /*交換二叉樹的所有左右子樹*/voidexchange(BiTree *T) BiTree *temp=NULL;精選范本 ,供參考！if (T->lchild=NUL

21、L&&T->rchild=NULL)return ;else temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;if (T->lchild) exchange(T->lchild);if (T->rchild) exchange(T->rchild);/*交換后二叉樹的遍歷*/voidDisplay(BiTree *T)printf("t交換后二叉樹按中序遍歷輸出:" );InOrder(T);printf("n" );printf(&

22、quot;t交換后二叉樹按前序遍歷輸出:" );PreOrder(T);printf("n" );printf("t交換后二叉樹按后序遍歷輸出:" );PostOrder(T);printf("n" );voidmenu()printf("n" );printf("t*n");printf("tt1.遞歸 - 創(chuàng)建二叉鏈表n" );printf("tt2.遞歸 - 中序遍歷二叉樹n" );printf("tt3.遞歸 - 前序遍歷二叉樹

23、n" );printf("tt4.遞歸 - 后序遍歷二叉樹n" );printf("tt5.非遞歸 - 中序遍歷二叉樹n" );printf("tt6.層次 - 遍歷二叉樹 n" );printf("tt7.二叉樹的高度 n" );printf("tt8.二叉樹的結(jié)點個數(shù)n" );printf("tt9.二叉樹的葉子結(jié)點個數(shù)n" );printf("tt10.交換二叉樹的所有左右子樹n" );printf("tt0.退出系統(tǒng) n" );printf("t*n");printf("nt請選擇 :" );voidmain()BiTree *bt; bt=NULL;intn,m=1;while (m)menu(); scanf("%d",&n); getchar();switch (n)case 1:printf("nt請輸入結(jié)點的前序序列創(chuàng)建二叉樹:0 表示空 :" );bt=createBiTree();break ; /*生成二叉樹 */case 2:printf("nt遞歸 - 中序遍歷二叉樹:&qu