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

1、 數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計說明書題目： 二叉樹的遍歷 學(xué)生姓名： 學(xué) 號： 院 （系）： 專 業(yè)： 指導(dǎo)教師： 年 月日目 錄1 需求分析12 概要設(shè)計12.1 功能設(shè)計12.2 算法流程圖23 詳細(xì)設(shè)計23.1 創(chuàng)建二叉樹23.2 二叉樹的遞歸遍歷算法33.3 二叉樹的層次遍歷算法33.4 二叉樹的非遞歸遍歷算法34 測試數(shù)據(jù)與分析35 算法分析96 總結(jié)9參 考 文 獻(xiàn)10附錄11數(shù)據(jù)結(jié)構(gòu)課程設(shè)計1 需求分析數(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）數(shù)據(jù)的物理結(jié)構(gòu)，即

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

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

4、reOrder(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是要遍歷樹的根指針，后序遍歷要求在遍歷完左右子樹后，再訪問根。需要判斷根結(jié)點(diǎn)的左右子樹是否均遍

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

6、后序遍歷（遞歸）函數(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é)點(diǎn)值的類型為字符型。(2)結(jié)點(diǎn)個數(shù)不超過10個。(3)按先序次序輸入，構(gòu)造二叉鏈表表示的二叉樹T，空格表示空樹。3.2 二叉樹的遞歸遍歷算法DLR(1)訪問根結(jié)點(diǎn)。(2)先序遍歷根結(jié)點(diǎn)的左子數(shù)。(3)先序遍歷根結(jié)點(diǎn)的右子數(shù)。LDR(1)先

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

8、后序遍歷算法bt是要遍歷樹的根指針，后序遍歷要求在遍歷完左右子樹后，再訪問根。需要判斷根結(jié)點(diǎn)的左右子樹是否均遍歷過。可采用標(biāo)記法，結(jié)點(diǎn)入棧時，配一個標(biāo)志tag一同入棧(1：遍歷左子樹前的現(xiàn)場保護(hù)。2：遍歷右子樹前的現(xiàn)場保護(hù))。首先將bt和tag(為1)入棧，遍歷左子樹；返回后，修改棧頂tag為2，遍歷右子樹；最后訪問根結(jié)點(diǎn)。4 測試數(shù)據(jù)與分析（1）運(yùn)行程序，進(jìn)入開始界面圖4-1 開始運(yùn)行（2）選擇1，創(chuàng)建二叉樹圖4-2 創(chuàng)建二叉樹(3)選擇2，顯示遞歸-中序遍歷二叉樹圖4-3 遞歸-中序遍歷二叉樹（4）選擇3，遞歸-前序遍歷二叉樹圖4-4 遞歸-前序遍歷二叉樹（5）選擇4，遞歸-后序遍歷二叉樹

9、圖4-5 遞歸-后序遍歷二叉樹（6）選擇5，非遞歸-后序遍歷二叉樹圖4-6 非遞歸-后序遍歷二叉樹（7）選擇6，層次遍歷二叉樹圖4-7 層次遍歷二叉樹（8）選擇7，計算二叉樹的高度圖4-8 二叉樹的高度（9）選擇8，計算二叉樹的結(jié)點(diǎn)的個數(shù)圖4-9 二叉樹的結(jié)點(diǎn)的個數(shù)（10）選擇9，計算二叉樹的葉子結(jié)點(diǎn)個數(shù)圖4-10 二叉樹的葉子結(jié)點(diǎn)個數(shù)（11）選擇10，交換二叉樹的所有子樹圖4-11 交換二叉樹的所有子樹（12）選擇0，則退出系統(tǒng)5算法分析 本程序按遞歸遍歷所耗費(fèi)的時間復(fù)雜度為O（n），其所耗費(fèi)的空間復(fù)雜度也為O（n）。6 總結(jié) 這次課程設(shè)計，雖然看起來很簡單，但是真的做起來的時候就發(fā)現(xiàn)了困難

10、重重，讓我深刻的體會到了要用C語言做一個二叉樹的遍歷，里面需要的很多知識還是我們沒有接觸過的，所以我們需要不斷的實踐，不斷的學(xué)習(xí)，不斷的發(fā)現(xiàn)問題去思考問題。 通過此這次課程設(shè)計，我掌握了二叉樹的存儲實現(xiàn)，掌握了二叉樹的遍歷思想，掌握了二叉樹的常見算法的程序?qū)崿F(xiàn)。二叉樹的高度（深度）為二叉樹中結(jié)點(diǎn)層次的最大值，也可視為其左右字?jǐn)?shù)高度的最大值加一。遍歷二叉樹的問題可以分解成兩步，第一步是求出某種遍歷次序下第一個被訪問的結(jié)點(diǎn)，然后連續(xù)求出剛訪問結(jié)點(diǎn)的后繼結(jié)點(diǎn)，直至所有的結(jié)點(diǎn)均被訪問。14參 考 文 獻(xiàn)1張銘.數(shù)據(jù)結(jié)構(gòu)與算法. 北京：高等教育出版社，20082 耿國華編.數(shù)據(jù)結(jié)構(gòu)用C語言描述M.北京：

11、高等教育出版社，2011.63 譚浩強(qiáng)著.C+面向?qū)ο笤O(shè)計M.北京：清華大學(xué)出版社，2004.64 譚浩強(qiáng)著.C+程序設(shè)計M.北京：清華大學(xué)出版社，2004.6附錄源程序代碼#include <stdio.h>#include <malloc.h>#define MAXSIZE 100typedef char DataType;typedef struct BiTNode/* 二叉鏈表存儲結(jié)構(gòu)*/DataType data; struct BiTNode *lchild,*rchild;BiTree;typedef BiTree* ElemType ;/* 棧中數(shù)據(jù)元素

12、類型，棧中保存結(jié)點(diǎn)指針*/typedef struct ElemType dataMAXSIZE; int top;SeqStack;/* 棧的類型定義，順序棧*/typedef structElemType queueMAXSIZE;int front,rear;SP;SeqStack *initSeqStack() /* 初始化棧*/ SeqStack *s; /* 首先建立?？臻g，然后初始化棧頂指針*/ s=(SeqStack*)malloc(sizeof(SeqStack); s->top=-1; return s;int push(SeqStack *s,ElemType x)

13、 if(s->top=MAXSIZE-1) /* 棧滿不能入棧*/printf("棧滿"); return 0; s->top+; s->datas->top=x; return 1;void pop(SeqStack *s) /* 出棧，假設(shè)棧不空*/ s->top-; int empty(SeqStack *s) if(s->top=-1) return 1; else return 0; ElemType top(SeqStack *s) /* 設(shè)棧不空*/return (s->datas->top); /* 遞歸算法創(chuàng)

14、建二叉鏈表*/BiTree *createBiTree()DataType ch; BiTree *T; ch=getchar(); if(ch='0') return NULL; else T=(BiTree *)malloc(sizeof(BiTree); T->data=ch; T->lchild=createBiTree(); T->rchild=createBiTree(); return T; /* 中序遍歷二叉樹的遞歸算法*/void InOrder(BiTree *T) if(T) InOrder(T->lchild); printf(&

15、quot;%c",T->data); InOrder(T->rchild); /* 前序遍歷二叉樹的遞歸算法*/void PreOrder(BiTree *T)if(T)printf("%c",T->data); PreOrder(T->lchild); PreOrder(T->rchild); /* 后序遍歷二叉樹的遞歸算法*/void PostOrder (BiTree *T)if(T) PostOrder(T->lchild); PostOrder(T->rchild); printf("%c",

16、T->data); /* 中序遍歷二叉樹的非遞歸算法*/void InOrderFei(BiTree *p)SeqStack *s; s=initSeqStack(); while(1) while(p) push(s,p); p=p->lchild;/* 先將結(jié)點(diǎn)指針壓棧，待出棧時再訪問*/ if(empty(s) break; p=top(s); pop(s); printf("%c",p->data); p=p->rchild; /* 按層次遍歷*/void LevelOrder(BiTree *T) SP *p; p=(SP*)malloc(

17、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->rear+1; printf("%c",T->data); if(T->lchild!=NULL) p->queuep->front=T->lchild;/*左孩子進(jìn)隊列*/ p->fr

18、ont=p->front+1; if(T->rchild!=NULL) p->queuep->front=T->rchild;/*右孩子進(jìn)隊列*/ p->front=p->front+1; /* 求二叉樹的高度*/int height(BiTree *T)int i,j; if(!T) return 0; i=height(T->lchild);/* 求左子樹的高度*/ j=height(T->rchild);/* 求右子樹的高度*/ return i>j?i+1:j+1;/* 二叉樹的高度為左右子樹中較高的高度加*/* 求二叉樹的所

19、有結(jié)點(diǎn)個數(shù)*/int Nodes(BiTree *T) int n1,n2; if(T=NULL) return 0; else if(T->lchild=NULL&&T->rchild=NULL) return 1; else n1=Nodes(T->lchild); n2=Nodes(T->rchild); return n1+n2+1; /* 求二叉樹的葉子結(jié)點(diǎn)個數(shù)*/int leafs(BiTree *T)int num1,num2; if(T=NULL) return 0; elseif(T->lchild=NULL&&T

20、->rchild=NULL) return 1; num1=leafs(T->lchild);/* 求左子樹中葉子結(jié)點(diǎn)數(shù)*/ num2=leafs(T->rchild);/* 求右子樹中葉子結(jié)點(diǎn)數(shù)*/ return num1+num2; /* 交換二叉樹的所有左右子樹*/void exchange(BiTree *T) BiTree *temp=NULL; if(T->lchild=NULL&&T->rchild=NULL) return; elsetemp=T->lchild; T->lchild=T->rchild; T-&g

21、t;rchild=temp; if(T->lchild) exchange(T->lchild); if(T->rchild) exchange(T->rchild);/* 交換后二叉樹的遍歷*/void Display(BiTree *T)printf("t交換后二叉樹按中序遍歷輸出:");InOrder(T);printf("n"); printf("t交換后二叉樹按前序遍歷輸出:");PreOrder(T);printf("n"); printf("t交換后二叉樹按后序遍歷輸

22、出:");PostOrder(T);printf("n");void menu() printf("n");printf("t*n"); printf("tt1.遞歸-創(chuàng)建二叉鏈表n");printf("tt2.遞歸-中序遍歷二叉樹n");printf("tt3.遞歸-前序遍歷二叉樹n");printf("tt4.遞歸-后序遍歷二叉樹n");printf("tt5.非遞歸-中序遍歷二叉樹n");printf("tt6

23、.層次-遍歷二叉樹n"); printf("tt7.二叉樹的高度n"); printf("tt8.二叉樹的結(jié)點(diǎn)個數(shù)n"); printf("tt9.二叉樹的葉子結(jié)點(diǎn)個數(shù)n");printf("tt10.交換二叉樹的所有左右子樹n");printf("tt0.退出系統(tǒng)n");printf("t*n");printf("nt請選擇:"); void main() BiTree *bt; bt=NULL; int n,m=1;while(m) menu(); scanf("%d",&n); getchar();switch(n) case 1:printf("nt請輸入結(jié)點(diǎn)的前序序列創(chuàng)建二叉樹:0表示空:"); bt=createBi