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

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

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

3、;T) 中序遍歷4.int PostTravel(BiTree &T) 后序遍歷5.int Depth(BiTree &T) /計(jì)算樹(shù)的深度6.int howmuch(BiTree T,int h) 采用樹(shù)節(jié)點(diǎn)指針數(shù)組，用于存放遍歷到的元素地址，如果有左孩子，存入地址，j加一 ，否則沒(méi)操作，通過(guò)訪問(wèn)數(shù)組輸出層次遍歷的結(jié)果。k計(jì)算葉子數(shù)，j為總節(jié)點(diǎn)。 H=0printf("%d", j)h=1真printf("%d",k)h=2for(i=0;i<j;i+)printf("%c",Qi->data)print

4、f("參數(shù)錯(cuò)誤")真真真假假假假7. int exchang(BiTree &T) 交換左右子樹(shù)，利用遞歸，當(dāng)有左右孩子時(shí)才交換三 詳細(xì)設(shè)計(jì)#include<stdio.h>#include<stdlib.h>typedef struct BiTNodechar data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;int CreatBiTree(BiTree &T)/先序法創(chuàng)建二叉樹(shù)char ch;if(ch=getchar()=' ')T=NULL;elseT=(

5、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);return 0;int MidTravel(BiTree &T)/中序遍歷if(T) MidTravel(

6、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;/樹(shù)節(jié)點(diǎn)指針數(shù)組，用于存放遍歷到的元素地址if(T=NULL)printf("空

7、的二叉樹(shù)n");Q0=T; /存入樹(shù)根int i,k=0;int j=1; /j為總節(jié)點(diǎn)for(i=0;i<j;i+)if(Qi->lchild!=NULL) /如果有左孩子，存入地址，j加一 ，否則沒(méi)操作Qj=Qi->lchild ;j+;if(Qi->rchild!=NULL) /如果有右孩子，存入地址，j加一 ，否則沒(méi)操作Qj=Qi->rchild ;j+;if(Qi->lchild=NULL&&Qi->rchild=NULL)k+; /計(jì)算葉子數(shù)if(h=0)printf("%d", j);else

8、 if(h=1)printf("%d",k);else if(h=2) for(i=0;i<j;i+)printf("%c",Qi->data);else printf("參數(shù)錯(cuò)誤");return 0;int Depth(BiTree &T) /計(jì)算樹(shù)的深度 int lh , rh ; if( NULL = T ) return 0 ; else lh = Depth( T->lchild ) ; rh = Depth( T->rchild ) ; return ( lh > rh ? lh :

9、 rh ) + 1 ; int exchang(BiTree &T)/交換左右子樹(shù) 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;T->rchild->data=t; /交換數(shù)據(jù)exchang(T->lchild);/ 遞歸調(diào)用 exchang(T->rchild); return 0; int choose(B

10、iTree 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("總節(jié)點(diǎn)數(shù)：");howmuch(T,0);e

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