數據結構課設二叉樹的遍歷

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

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

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

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

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

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

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

8、向 p 的右孩子結點。（ 2）非遞歸的中序遍歷算法a. 指針指向 p 的左孩子結點。b. 從棧中彈出棧頂元素。c. 訪問結點的數據域。d. 指針指向 p 的右孩子結點。（ 3）非遞歸的后序遍歷算法bt 是要遍歷樹的根指針，后序遍歷要求在遍歷完左右子樹后，再訪問根。需要判斷根結點的左右子樹是否均遍歷過。可采用標記法，結點入棧時，配一個標志 tag 一同入棧(1 ：遍歷左子樹前的現場保護。 2：遍歷右子樹前的現場保護 ) 。首先將 bt 和 tag( 為 1) 入棧，遍歷左子樹；返回后，修改棧頂 tag 為 2，遍歷右子樹；最后訪問根結點。4 測試數據與分析（ 1）運行程序，進入開始界面圖 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，計算二叉樹的結點的個數圖 4-9 二叉樹的結點的個數（ 10）選擇 9，計算二叉樹的葉子結點個

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

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

12、;#defineMAXSIZE 100typedefchar DataType;typedefstructBiTNode/*二叉鏈表存儲結構*/DataType data;structBiTNode *lchild,*rchild;BiTree;typedefBiTree* ElemType ;/*棧中數據元素類型，棧中保存結點指針*/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)/*出棧，假設棧不空*/s->top-;

14、 intempty(SeqStack *s)if (s->top=-1)return1;elsereturn0;ElemType top(SeqStack *s)/*設棧不空 */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;/*先將結點指針壓棧，待出棧時再訪問*/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;/* 左孩子進隊列 */p->front=p->front+1;if (T->rchild!=NULL)p->queuep->front=T->rchild;/* 右孩子進隊列 */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;/*二叉樹的高度為左右子樹中較高的高度加*/*求二叉樹的所有結點個數*/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; /*求二叉樹的葉子結點個

20、數*/intleafs(BiTree *T)intnum1,num2;if (T=NULL) return0;else if (T->lchild=NULL&&T->rchild=NULL)return1;num1=leafs(T->lchild);/*求左子樹中葉子結點數*/num2=leafs(T->rchild);/*求右子樹中葉子結點數*/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.二叉樹的結點個數n" );printf("tt9.二叉樹的葉子結點個數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請輸入結點的前序序列創(chuàng)建二叉樹:0 表示空 :" );bt=createBiTree();break ; /*生成二叉樹 */case 2:printf("nt遞歸 - 中序遍歷二叉樹:&qu