二叉樹的建立及遍歷

------------------------------------------------------------------------二叉樹的建立及遍歷數(shù)據(jù)結(jié)構(gòu)實驗五課程數(shù)據(jù)結(jié)構(gòu)實驗名稱二叉樹的建立及遍歷第頁專業(yè)班級學號姓名實驗日期：年月日評分一、實驗目的1．學會實現(xiàn)二叉樹結(jié)點結(jié)構(gòu)和對二叉樹的基本操作。2．掌握對二叉樹每種操作的具體實現(xiàn)，學會利用遞歸方法編寫對二叉樹這種遞歸數(shù)據(jù)結(jié)構(gòu)進行處理的算法。二、實驗要求1．認真閱讀和掌握和本實驗相關(guān)的教材內(nèi)容。2．編寫完整程序完成下面的實驗內(nèi)容并上機運行。3．整理并上交實驗報告。三、實驗內(nèi)容1．編寫程序任意輸入二叉樹的結(jié)點個數(shù)和結(jié)點值，構(gòu)造一棵二叉樹，采用三種遞歸遍歷算法(前序、中序、后序)對這棵二叉樹進行遍歷并計算出二叉樹的高度。2.編寫程序生成下面所示的二叉樹，并采用先序遍歷的非遞歸算法對此二叉樹進行遍歷。四、實驗步驟（描述實驗步驟及中間的結(jié)果或現(xiàn)象。在實驗中做了什么事情，怎么做的，發(fā)生的現(xiàn)象和中間結(jié)果）第一題#include"stdafx.h"#include"iostream.h"#include"stdlib.h"#include"stdio.h"#include<stack>usingnamespacestd;#defineNULL0#defineOK1#defineOVERFLOW-1typedefintStatus;typedefstructnode{ chardata; structnode*lchild; structnode*rchild;}*bitree;intk=0;intdepth(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=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<<T->data; inorder(T->rchild); }}voidinpre(structnode*T){ if(!T) return; else { cout<<T->data; inpre(T->lchild); inpre(T->rchild); }}voidpostorder(structnode*T){ if(!T) return; else { postorder(T->lchild); postorder(T->rchild); cout<<T->data; }}//先序非遞歸遍歷voidinpre1(structnode*T){ structnode*p; structnode*stack[20]; inttop=0; p=T; cout<<"非遞歸先序"; while(p||top!=0) { while(p) { stack[top++]=p; cout<<p->data; p=p->lchild; } p=stack[--top]; p=p->rchild; }}//中序非遞歸遍歷voidinorder1(structnode*T){ structnode*p; structnode*stack[20]; inttop=0; p=T; cout<<"非遞歸中序"; while(p||top!=0) { while(p) { stack[top++]=p; p=p->lchild; } p=stack[--top]; cout<<p->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<<endl; postorder(T);cout<<endl; inorder(T);cout<<endl; inpre1(T); cout<<endl; inorder1(T);cout<<endl; m=depth(T); cout<<"二叉樹高度為："<<m<<endl; return0;}第二題：#include"stdafx.h"#include"iostream.h"#include"stdlib.h"#include"stdio.h"#include<stack>usingnamespacestd;#defineNULL0#defineOK1#defineOVERFLOW-1typedefintStatus;typedefstructnode{ chardata; structnode*lchild; structnode*rchild;}*bitree;StatusCreate(bitree&T)//按先序次序輸入二叉樹中結(jié)點的值，!表示空樹{ chare; cout<<"輸入樹的元素："<<endl;cin>>e;if(e=='!')T=NULL; else { if(!(T=(node*)malloc(sizeof(node)))) exit(OVERFLOW); T->data=e; Create(T->lchild); Create(T->rchild); } returnOK;}//先序非遞歸遍歷voidinpre(structnode*T){ structnode*p; structnode*stack[20]; inttop=0; p=T; cout<<"非遞歸先序"; while(p||top!=0) { while(p) { stack[top++]=p; cout<<p->data; p=p->lchild; } p=stack[--top]; p=p->rchild; }}//主函數(shù)intmain(){ bitreeT;Create(T); cout<<"輸出的元素為："<<endl; inpre(T); return0;}五實驗結(jié)果第一題：輸入先序為-+a*b%cd/ef輸入后序為a+b*c%d-e/f得出結(jié)果：輸入先序為abcd輸入后序為bacd得出結(jié)果：第二題：六實驗總結(jié)1為什么頭文件只用#include<iostream>usingnamespacestd;不行，要把所寫到的程序中所包含的頭文件頭寫進去。。于是就在想，反正以后不管這些頭文件有沒用到頭寫進去，省得一大堆麻煩。2用先序建樹的時候雖然只要輸入一個字符串，但是要判斷空樹的情況。比較麻煩。我個人覺得用先序與中序聯(lián)合建樹比較簡單。因為這樣只要輸入先序與中序就可以建樹了。3對于三種遍歷的過程，要是用遞歸寫的就根據(jù)書上所給出的遍歷步驟做稍微的調(diào)整就好了。至于非遞歸的三種遍歷，中序最為簡單，用一個棧就可以完成了，思路是邊進棧邊收索左孩子，直到左孩子為空的時候才開始進行出棧輸出再收索右孩子的操作。而非遞歸的先序遍歷基本可以和中序一樣，建立一個隊列，在進棧的時候隊列也進同樣的元素，但是不與棧一起出棧。而是在最后進棧出棧結(jié)束的時候，對隊列進行出隊列操作即可。4二叉樹對于進行表達式的前綴，中綴和后綴的表示有明顯的優(yōu)勢，既方便，又容易理解。其先序，中序和后序分別對應這表達式的前綴，中綴和后綴。5在建樹與進行樹的遍歷的時候一定要理解其建樹與遍歷的整個過程。不然就會連為什么這樣做都不知道。在遍歷樹的時候最常用到的就是棧的結(jié)構(gòu)了（非遞歸）。七：思考與提高1．如何計算二叉鏈表存儲的二叉樹中度數(shù)為1的結(jié)點數(shù)？答：intcountleaf(bitreet,intcount){if(!(t->lchild)&&(t->rchild)count++;elseif((t->lchild)&&!(t->rchild))count++;countleaf(t->lchild);count