二叉樹的建立及遍歷94239

《二叉樹的建立及遍歷94239》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

1、數(shù)據(jù)結構實驗五課程數(shù)據(jù)結構實驗名稱二叉樹的建立及遍歷第頁專業(yè)班級學號姓名實驗日期：年月日評分一、實驗目的1．學會實現(xiàn)二叉樹結點結構和對二叉樹的基本操作。2．掌握對二叉樹每種操作的具體實現(xiàn)，學會利用遞歸方法編寫對二叉樹這種遞歸數(shù)據(jù)結構進行處理的算法。二、實驗要求1．認真閱讀和掌握和本實驗相關的教材內(nèi)容。2．編寫完整程序完成下面的實驗內(nèi)容并上機運行。3．整理并上交實驗報告。三、實驗內(nèi)容1．編寫程序任意輸入二叉樹的結點個數(shù)和結點值，構造一棵二叉樹，采用三種遞歸遍歷算法(前序、中序、后序)對這棵二叉樹進行遍歷并計算出二叉樹的高度。2.編寫程序生成下面所示的二叉樹，并采用先序遍歷的非遞歸算法對此二叉樹進

2、行遍歷。四、實驗步驟（描述實驗步驟及中間的結果或現(xiàn)象。在實驗中做了什么事情，怎么做的，發(fā)生的現(xiàn)象和中間結果）第一題#include"stdafx.h"#include"iostream.h"#include"stdlib.h"#include"stdio.h"#includeusingnamespacestd;#defineNULL0#defineOK1#defineOVERFLOW-1typedefintStatus;typedefstructnode{chardata;structnode*lchild;structnode*rchild;}*bitree;intk=0;in

3、tdepth(bitreeT)//樹的高度{if(!T)return0;else{intm=depth(T->lchild);intn=depth(T->rchild);return(m>n?m:n)+1;}}//先序，中序建樹structnode*create(char*pre,char*ord,intn){structnode*T;intm;T=NULL;if(n<=0){returnNULL;}else{m=0;T=new(structnode);T->data=*pre;T->lchild=T->rchild=NULL;while(ord[m]!=*pre)m++;T->lchild=

4、create(pre+1,ord,m);T->rchild=create(pre+m+1,ord+m+1,n-m-1);returnT;}}//中序遞歸遍歷voidinorder(structnode*T){if(!T)return;else{inorder(T->lchild);cout<data;inorder(T->rchild);}}voidinpre(structnode*T){if(!T)return;else{cout<data;inpre(T->lchild);inpre(T->rchild);}}voidpostorder(structnode*T){if(!

5、T)return;else{postorder(T->lchild);postorder(T->rchild);cout<data;}}//先序非遞歸遍歷voidinpre1(structnode*T){structnode*p;structnode*stack[20];inttop=0;p=T;cout<<"非遞歸先序";while(p

6、

7、top!=0){while(p){stack[top++]=p;cout<data;p=p->lchild;}p=stack[--top];p=p->rchild;}}//中序非遞歸遍歷voidinorder1(structnode*T){

8、structnode*p;structnode*stack[20];inttop=0;p=T;cout<<"非遞歸中序";while(p

9、

10、top!=0){while(p){stack[top++]=p;p=p->lchild;}p=stack[--top];cout<data;p=p->rchild;}}//主函數(shù)intmain(){bitreeT;charpre[30],ord[30];intn,m;gets(pre);gets(ord);n=strlen(pre);T=create(pre,ord,n);inpre(T);cout<

11、