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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)實驗報告班級：學(xué)號：姓名：計算機科學(xué)與技術(shù)學(xué)院 題目：二叉樹的遍歷一、設(shè)計內(nèi)容 從鍵盤接受輸入先序序列，以二叉鏈表作為存儲結(jié)構(gòu)，建立二叉樹（以先序來建立）并對其進(jìn)行遍歷。然后將遍歷結(jié)果輸出。先序、中序、后序遍歷要求采用遞歸和非遞歸實現(xiàn)。ABCDGEF對于如右圖所示的二叉樹，其擴展的先序遍歷序列為：A B D . G . . C E . . F . .（其中小圓點表示空子樹）當(dāng)輸入擴展的先序遍歷序列：A B D . G . . C E . . F . . 輸出應(yīng)該為：層次遍歷：A B C D E F G 先序遍歷：A B D G C E F中序遍歷：D G B

2、A E C F 后續(xù)遍歷：G D B E F C A 二、設(shè)計目的1. 達(dá)到熟練掌握C+語言的基本知識和技能；2. 能夠利用所學(xué)的基本知識和技能，解決簡單的面向?qū)ο蟪绦蛟O(shè)計問題。三、系統(tǒng)分析與設(shè)計（確定程序功能模塊）1.定義二叉鏈表存儲結(jié)構(gòu)2.以先序遍歷建立二叉鏈表，CreateBiTree(BiTree *bt)3.實現(xiàn)先序遍歷二叉樹的遞歸算法， PreOrder(BiTree bt)4實現(xiàn)中序遍歷二叉樹的遞歸算法， InOrder(BiTree bt)5.實現(xiàn)后序遍歷二叉樹的遞歸算法， PostOrder(BiTree bt)6.實現(xiàn)先序遍歷二叉樹的非遞歸算法，NRPreOrder (Bi

3、Tree bt)7.實現(xiàn)中序遍歷二叉樹的非遞歸算法，NRInOrder (BiTree bt)8.實現(xiàn)后序遍歷二叉樹的非遞歸算法，NRPostOrder (BiTree bt)9.實現(xiàn)層次遍歷二叉樹的遞歸算法，LevelOrder (BiTree bt)10.調(diào)用各個函數(shù)輸出遍歷結(jié)果四、源程序代碼#include "iostream.h"#include "stdio.h"#include "malloc.h"typedef struct Node/*聲明二叉樹二叉鏈表節(jié)點的結(jié)構(gòu)！*/ char data; struct Node *

4、lchild; struct Node *rchild;BiTNode,*BiTree;typedef struct /*定義結(jié)構(gòu)體（將棧中元素的數(shù)據(jù)類型定義為指針和標(biāo)志flag合并的結(jié)構(gòu)體類型）*/BiTree link;int flag;stacktype;/*函數(shù)聲明*/void Visite(char a);void CreateBiTree(BiTree *bt);void PreOrder(BiTree bt);void InOrder(BiTree bt);void PostOrder(BiTree bt);void NRPreOrder (BiTree bt);void NRI

5、nOrder (BiTree bt);void NRPostOrder (BiTree bt);void LevelOrder (BiTree bt);/*定義函數(shù)（訪問節(jié)點的數(shù)據(jù)域）*/void Visite(char a) cout<<a<<" "/*層次遍歷二叉樹*/void LevelOrder (BiTree bt)BiTree queue50;int front,rear;if (bt=NULL)return;front=-1;rear=0;queuerear=bt;while (front !=rear)front +;Visite (

6、queuefront->data);if (queuefront->lchild!=NULL)rear+;queuerear=queuefront->lchild;if (queuefront->rchild!=NULL)rear+;queuerear=queuefront->rchild;/*先序遍歷建立二叉樹*/void CreateBiTree(BiTree *bt)char ch;ch=getchar();if (ch='.') *bt=NULL;else *bt=(BiTree) malloc(sizeof(BiTNode); (*bt)

7、->data=ch; CreateBiTree(&(*bt)->lchild); CreateBiTree(&(*bt)->rchild);/*遞歸先序遍歷二叉樹bt*/void PreOrder(BiTree bt) if(bt=NULL) return;cout<<bt->data<<" "PreOrder (bt->lchild);PreOrder (bt->rchild);/*遞歸中序遍歷二叉樹bt*/void InOrder(BiTree bt)if(bt=NULL) return;InO

8、rder (bt->lchild);cout<<bt->data<<" "InOrder (bt->rchild);/*遞歸后序遍歷二叉樹bt*/void PostOrder(BiTree bt)if(bt=NULL) return;PostOrder (bt->lchild);PostOrder (bt->rchild);cout<<bt->data<<" "/*非遞歸先序遍歷二叉樹bt*/ void NRPreOrder (BiTree bt)BiTree stack

9、20,p;int top;if (bt=NULL)return;top=0;p=bt;while(!(p=NULL&&top=0)while (p!=NULL)Visite (p->data);if (top <20-1)stacktop=p;top+;elsecout<<"溢出！"return;p=p->lchild;if (top<=0)return;elsetop-;p=stacktop;p=p->rchild; /*非遞歸中序遍歷二叉樹bt*/void NRInOrder (BiTree bt)BiTree

10、stack20,p;int top;if (bt=NULL)return;top=0;p=bt;while(!(p=NULL&&top=0)while (p!=NULL)if (top <20-1)stacktop=p;top+;elsecout<<"溢出！"return;p=p->lchild;if (top<=0)return;elsetop-;p=stacktop;Visite (p->data);p=p->rchild;/*非遞歸后序遍歷二叉樹bt*/void NRPostOrder (BiTree bt)s

11、tacktype stack50;BiTree p;int top,sign;if (bt=NULL)return;top=-1;p=bt;while (!(p=NULL&&top=-1)if (p!=NULL)top+;stacktop.link=p;stacktop.flag=1;p=p->lchild;elsep=stacktop.link;sign=stacktop.flag;top-;if (sign=1)top+;stacktop.link=p;stacktop.flag=2;p=p->rchild;else Visite (p->data);p=

12、NULL;/*主函數(shù)*/void main()cout<<"請輸入序列："<<endl;BiTree bt;CreateBiTree(&bt);cout<<"n層次遍歷:"LevelOrder (bt);cout<<"nn先序、中序、后序遍歷的遞歸實現(xiàn):"cout<<"n先序遍歷:"PreOrder(bt);cout<<"n中序遍歷:"InOrder(bt);cout<<"n后序遍歷:"PostOrder(bt);cout<<"nn先序、中序、后序遍歷的非遞歸實現(xiàn):"cout<<"n先序遍歷:"NRPreOrder (bt);cout<<"n中序遍歷:"NRInOrder (bt);cout<<"n后序遍歷:"NRPostOrder (bt);cout<<"nn&qu