二叉樹的基本操作實(shí)驗(yàn)

1、實(shí)驗(yàn)三 二叉樹的基本運(yùn)算一、實(shí)驗(yàn)?zāi)康?、使學(xué)生熟練掌握二叉樹的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。2、熟練掌握二叉樹的各種遍歷算法。二、實(shí)驗(yàn)內(nèi)容 問題描述 建立一棵二叉樹，試編程實(shí)現(xiàn)二叉樹的如下基本操作：1. 按先序序列構(gòu)造一棵二叉鏈表表示的二叉樹T；2. 對這棵二叉樹進(jìn)行遍歷：先序、中序、后序以及層次遍歷，分別輸出結(jié)點(diǎn)的遍歷序列；3. 求二叉樹的深度/結(jié)點(diǎn)數(shù)目/葉結(jié)點(diǎn)數(shù)目；（選做 ）4. 將二叉樹每個(gè)結(jié)點(diǎn)的左右子樹交換位置。（選做） 基本要求 從鍵盤接受輸入（先序），以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，建立二叉樹（以先序來建立）， 測試數(shù)據(jù) 如輸入：AB6D印G66F力力力（其中力表示空格字符）則輸出結(jié)果為先序：ABC

2、DEGF中序：CBEGDFA后序：CGEFDBA層序：ABCDEFG 選作內(nèi)容 采用非遞歸算法實(shí)現(xiàn)二叉樹遍歷。三、實(shí)驗(yàn)前的準(zhǔn)備工作1、掌握樹的邏輯結(jié)構(gòu)。2、掌握二叉樹的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。3、掌握二叉樹的各種遍歷算法的實(shí)現(xiàn)。一 實(shí)驗(yàn)分析本次試驗(yàn)是關(guān)于二叉樹的常見操作，主要是二叉樹的建立和遍歷。二叉樹的遍歷有多種方法，本次試驗(yàn)我采用遞歸法，遞歸法比較簡單。二 概要設(shè)計(jì)功能實(shí)現(xiàn)I.int CreatBiTree(BiTree &T)存該二叉樹2.int PreTravel(BiTree &T)3. int MidTravel(BiTree &T)4.int PostTravel(BiTree &T

3、)5.int Depth(BiTree &T) /用遞歸的方法先序建立二叉樹，并用鏈表儲(chǔ)前序遍歷中序遍歷后序遍歷計(jì)算樹的深度6.int howmuch(BiTree T,int h) 采用樹節(jié)點(diǎn)指針數(shù)組，用于存放遍歷到的元 素地址，如果有左孩子，存入地址，j加一，否則沒操作，通過訪問數(shù)組輸出層次遍歷的結(jié)果。k計(jì)算葉子數(shù)，j為總節(jié)點(diǎn)7 / 87. int exchang(BiTree &T)交換左右子樹，利用遞歸，當(dāng)有左右孩子時(shí)才交換三詳細(xì)設(shè)計(jì)#include#include typedef struct BiTNode char data;struct BiTNode *lchild,*rch

4、ild; BiTNode,*BiTree;int CreatBiTree(BiTree &T)/先序法創(chuàng)建二叉樹char ch;if(ch=getchar()= )T=NULL;elseT=(BiTNode*)malloc(sizeof(BiTNode);if(!T)exit(1);T-data=ch;CreatBiTree(T-lchild);CreatBiTree(T-rchild);return 0;int PreTravel(BiTree &T)/前序遍歷if(T)printf(%c,T-data);PreTravel(T-lchild);PreTravel(T-rchild);ret

5、urn 0;int MidTravel(BiTree &T)/中序遍歷if(T)MidTravel(T-lchild);printf(%c,T-data);MidTravel(T-rchild);return 0;int PostTravel(BiTree &T)/后序遍歷if(T)PostTravel(T-lchild);PostTravel(T-rchild);printf(%c,T-data);return 0;int howmuch(BiTree T,int h)BiTNode *Q100;/ 樹節(jié)點(diǎn)指針數(shù)組，用于存放遍歷到的元素地址if(T=NULL)printf( 空的二叉樹n);

6、Q0=T; / 存入樹根int i,k=0;int j=1; /j 為總節(jié)點(diǎn)for(i=0;ilchild!=NULL) / 如果有左孩子，存入地址，j 加一 ，否則沒操作Qj=Qi-lchild ;j+;if(Qi-rchild!=NULL) / 如果有右孩子，存入地址，j 加一 ，否則沒操作Qj=Qi-rchild ;j+;if(Qi-lchild=NULL&Qi-rchild=NULL) k+; /計(jì)算葉子數(shù) if(h=0)printf(%d, j);else if(h=1)printf(%d,k);else if(h=2)for(i=0;idata);elseprintf( 參數(shù)錯(cuò)誤)

7、;return 0;int Depth(BiTree &T)/計(jì)算樹的深度int lh , rh ;if( NULL = T )return 0 ; else lh = Depth( T-lchild ) ;rh = Depth( T-rchild ) ; return ( lh rh ? lh : rh ) + 1 ;int exchang(BiTree &T)/ 交換左右子樹if(T != NULL)if(T-lchild!=NULL&T-rchild!=NULL)/ 當(dāng)有左右孩子時(shí)才交換 char t;t=T-lchild-data;T-lchild-data=T-rchild-data

8、; T-rchild-data=t; / 交換數(shù)據(jù)exchang(T-lchild);/ 遞歸調(diào)用 exchang(T-rchild);return 0;int choose(BiTree T) / 功能選int a;scanf(%d,&a); if(a=1) printf( 先序遍歷:);PreTravel(T);else if(a=2)printf( 中序遍歷:);MidTravel(T);else if(a=3)printf( 后序遍歷:);PostTravel(T);else if(a=4)printf( 層序遍歷:);howmuch(T,2);else if(a=5)printf(

9、總節(jié)點(diǎn)數(shù)：);howmuch(T,0);else if(a=6)printf( 總?cè)~子數(shù)：);howmuch(T,1);else if(a=7)printf( 樹的深度：);printf(%d,Depth(T);else if(a=8)printf( 交換前 n);howmuch(T,2);exchang(T);printf( 交換后 n);howmuch(T,2);else if(a=9)exit(1);else printf( 沒有這個(gè)操作n);printf( 操作完成,請輸入下一個(gè)操作n);choose(T);return 0;int main() / 主函數(shù)printf( 二叉樹的基本操作n);printf( 請先建立二叉樹，按先序的方式輸入如果數(shù)據(jù)為空輸入空格n);BiTree T; / 定義二叉樹，初始化CreatBiTree(T);choose(T);return 0;四用戶手冊根據(jù)程序的提示按先序輸入二叉樹， 如果數(shù)據(jù)為空輸入空格，然后回車，輸入你 要進(jìn)行的操作的序號(hào)。1.先序遍歷、2中序遍歷、3后序遍歷、4層次遍歷、5總節(jié)點(diǎn)數(shù)、6總?cè)~子數(shù)、7樹的深度、8交換左右子樹、9結(jié)束操作五實(shí)驗(yàn)總結(jié)通過實(shí)驗(yàn)，我熟悉二叉樹樹的基本操作，掌握二叉樹的實(shí)