二叉樹遍歷課程設(shè)計

1、目錄一選題背景1二問題描述1三概要設(shè)計23.1.創(chuàng)建二叉樹23.2.二叉樹的非遞歸前序遍歷示意圖23.3.二叉樹的非遞歸中序遍歷示意圖23.4.二叉樹的后序非遞歸遍歷示意圖3四詳細(xì)設(shè)計44.1創(chuàng)建二叉樹44.2二叉樹的非遞歸前序遍歷算法44.3二叉樹的非遞歸中序遍歷算法54.4二叉樹的非遞歸后序遍歷算法5五測試數(shù)據(jù)與分析7六源代碼7總結(jié)11參考文獻(xiàn):12一選題背景二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是用指針建立二叉樹中結(jié)點之間的關(guān)系。二叉鏈存儲結(jié)構(gòu)的每個結(jié)點包含三個域，分別是數(shù)據(jù)域，左孩子指針域，右孩子指針域。因此每個結(jié)點為leftchild data rightchild 由二叉樹的定義知可把其遍歷設(shè)計成遞

2、歸算法。共有前序遍歷、中序遍歷、后序遍歷。可先用這三種遍歷輸出二叉樹的結(jié)點。然而所有遞歸算法都可以借助堆棧轉(zhuǎn)換成為非遞歸算法。以前序遍歷為例，它要求首先要訪問根節(jié)點，然后前序遍歷左子樹和前序遍歷右子樹。特點在于所有未被訪問的節(jié)點中，最后訪問結(jié)點的左子樹的根結(jié)點將最先被訪問，這與堆棧的特點相吻合。因此可借助堆棧實現(xiàn)二叉樹的非遞歸遍歷。將輸出結(jié)果與遞歸結(jié)果比較來檢驗正確性。二問題描述對任意給定的二叉樹（頂點數(shù)自定）建立它的二叉鏈表存貯結(jié)構(gòu)，并利用棧的五種基本運算（置空棧、進棧、出棧、取棧頂元素、判棧空）實現(xiàn)二叉樹的先序、中序、后序三種遍歷，輸出三種遍歷的結(jié)果。畫出搜索順序示意圖。三概要設(shè)計3.1.

3、創(chuàng)建二叉樹3.2.二叉樹的非遞歸前序遍歷示意圖 圖3.2二叉樹前序遍歷示意圖3.3.二叉樹的非遞歸中序遍歷示意圖 圖3.3二叉樹中序遍歷示意圖3.4.二叉樹的后序非遞歸遍歷示意圖 圖3.4二叉樹后序遍歷示意圖四詳細(xì)設(shè)計4.1創(chuàng)建二叉樹(1)定義二叉樹結(jié)點值的類型為字符型。#define m 50typedef struct Nodechar data;struct Node *Lchild;struct Node *Rchild;bitnode,*bitree;typedef struct(2)結(jié)點個數(shù)不超過50個。(3)按先序次序輸入，構(gòu)造二叉鏈表表示的二叉樹T，空格表示空樹。4.2二叉樹的

4、非遞歸前序遍歷算法void preorder(bitree root) SeqStack S;bitree p;InitStack(&S);p=root;while(p!=NULL|!isempty(&S)while(p!=NULL)printf(%c,(p-data);push(&S,p);p=p-Lchild;if(!isempty(&S)pop(&S,&p);p=p-Rchild;a.訪問結(jié)點的數(shù)據(jù)域。b.指針指向p的左孩子結(jié)點。c.從棧中彈出棧頂元素。d.指針指向p的右孩子結(jié)點。4.3二叉樹的非遞歸中序遍歷算法void inorder(bitree root) SeqStack S;b

5、itree p;InitStack(&S);p=root;while(p!=NULL|!isempty(&S)if(p!=NULL)push(&S,p);p=p-Lchild;elsepop(&S,&p);printf(%c,(p-data);p=p-Rchild;a.指針指向p的左孩子結(jié)點。b.從棧中彈出棧頂元素。c.訪問結(jié)點的數(shù)據(jù)域。d.指針指向p的右孩子結(jié)點。4.4二叉樹的非遞歸后序遍歷算法void postorder(bitree root)SeqStack S;bitree p,q;InitStack(&S);p=root;while (p!=NULL | !isempty(&S)

6、if (p!=NULL) push(&S, p); p=p-Lchild; else GetTop(&S, &p); if (p-Rchild=NULL | p-Rchild=q) printf(%c,(p-data); pop(&S, &p); q=p; p=NULL; else p=p-Rchild; root是要遍歷樹的根指針，后序遍歷要求在遍歷完左右子樹后，再訪問根。需要判斷根結(jié)點的左右子樹是否均遍歷過。也可采用標(biāo)記法，結(jié)點入棧時，配一個標(biāo)志tag一同入棧(1：遍歷左子樹前的現(xiàn)場保護，2：遍歷右子樹前的現(xiàn)場保護)。首先將bt和tag(為1)入棧，遍歷左子樹；返回后，修改棧頂tag為2，

7、遍歷右子樹；最后訪問根結(jié)點。五測試數(shù)據(jù)與分析六源代碼非遞歸算法實現(xiàn)：1 新建一個工程，再在工程中新建一個頭文件，輸入下列程序：#define m 50typedef struct Nodechar data;struct Node *Lchild;struct Node *Rchild;bitnode,*bitree;typedef structbitree stackm; /*用來存放棧中元素的一維數(shù)組*/int top;SeqStack;void InitStack(SeqStack *s) /*初始化棧*/s-top=-1;int isempty(SeqStack *s)/*判斷棧是否為

8、空*/if(s-top=-1)return 1;elsereturn 0;int push(SeqStack *s,bitree x)/*進棧*/if(s-top=m-1)return(0);elses-top+;s-stacks-top=x;return(1);int pop(SeqStack *s,bitree *x)/*出棧*/if(s-top=-1)return(0);else*x=s-stacks-top;s-top-;return(1);int GetTop(SeqStack *s,bitree *x)/*去棧頂元素*/if(s-top=-1)return 0;else*x=s-s

9、tacks-top;return 1;void preorder(bitree root)/*先序遍歷二叉樹*/ SeqStack S;bitree p;InitStack(&S);p=root;while(p!=NULL|!isempty(&S)while(p!=NULL)printf(%c,(p-data);push(&S,p);p=p-Lchild;if(!isempty(&S)pop(&S,&p);p=p-Rchild;void inorder(bitree root) /*中序遍歷二叉樹*/SeqStack S;bitree p;InitStack(&S);p=root;while(

10、p!=NULL|!isempty(&S)if(p!=NULL)push(&S,p);p=p-Lchild;elsepop(&S,&p);printf(%c,(p-data);p=p-Rchild;void postorder(bitree root) /*后序遍歷二叉樹*/SeqStack S;bitree p,q;InitStack(&S);p=root;while (p!=NULL | !isempty(&S) if (p!=NULL) push(&S, p); p=p-Lchild; else GetTop(&S, &p); if (p-Rchild=NULL | p-Rchild=q)

11、 printf(%c,(p-data); pop(&S, &p); q=p; p=NULL; else p=p-Rchild; 2 再在工程中新建一個C+源文件，將它另存為以.c為擴展名的文件，輸入下列程序：#include stdio.h#include malloc.h#include order.hbitree creatbitree()char ch;bitree bt;ch=getchar();if(ch=.)bt=NULL;elsebt=(bitree)malloc(sizeof(bitnode);bt-data=ch;bt-Lchild=creatbitree();bt-Rchi

12、ld=creatbitree();return bt;void main()int a; bitree bt; printf(請輸入二叉樹的線序序列，空子樹用.表示:n); bt=creatbitree(); while(a!=0) printf(需要先序遍歷輸出請輸入1，中序遍歷請輸入2，后序遍歷請輸入3,結(jié)束輸入0:); scanf(%d,&a); switch(a) case(1): preorder(bt); break; case(2): inorder(bt); break; case(3): postorder(bt); break; case(0): break; printf(n); 總結(jié)1. “ 數(shù)據(jù)結(jié)構(gòu) ” 是計算機類各專業(yè)的核心課程，也是其他諸多類專業(yè)的重要選修課。我通過學(xué)習(xí)這門課，可以為理解、應(yīng)用和開發(fā)程序提供技術(shù)