實(shí)驗(yàn)三、二叉樹的基本操作實(shí)驗(yàn)三、二叉樹的基本操作實(shí)驗(yàn)三、二叉樹的基本操作xxx公司實(shí)驗(yàn)三、二叉樹的基本操作文件編號：文件日期：修訂次數(shù)：第1.0次更改批準(zhǔn)審核制定方案設(shè)計，管理制度實(shí)驗(yàn)三二叉樹的基本運(yùn)算一、實(shí)驗(yàn)?zāi)康?、使學(xué)生熟練掌握二叉樹的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。2、熟練掌握二叉樹的各種遍歷算法。二、實(shí)驗(yàn)內(nèi)容題目一：二叉樹的基本操作實(shí)現(xiàn)（必做題）[問題描述]建立一棵二叉樹，試編程實(shí)現(xiàn)二叉樹的如下基本操作：

1.按先序序列構(gòu)造一棵二叉鏈表表示的二叉樹T；

2.對這棵二叉樹進(jìn)行遍歷：先序、中序、后序以及層次遍歷，分別輸出結(jié)點(diǎn)的遍歷序列；

3.求二叉樹的深度/結(jié)點(diǎn)數(shù)目/葉結(jié)點(diǎn)數(shù)目；(選做)

4.將二叉樹每個結(jié)點(diǎn)的左右子樹交換位置。（選做）[基本要求]從鍵盤接受輸入（先序），以二叉鏈表作為存儲結(jié)構(gòu)，建立二叉樹（以先序來建立），[測試數(shù)據(jù)]如輸入：ABCффDEфGффFффф（其中ф表示空格字符）

則輸出結(jié)果為先序：ABCDEGF

中序：CBEGDFA

后序：CGEFDBA層序：ABCDEFG[選作內(nèi)容]采用非遞歸算法實(shí)現(xiàn)二叉樹遍歷。算法設(shè)計主要思想：根據(jù)二叉樹的圖形結(jié)構(gòu)創(chuàng)建出二叉樹的數(shù)據(jù)結(jié)構(gòu)，然后用指針對樹進(jìn)行操作，重點(diǎn)掌握二叉樹的結(jié)構(gòu)和性質(zhì)。本程序包含四個模塊：結(jié)構(gòu)體定義（2）創(chuàng)建二叉樹（3）對樹的幾個操作（4）主函數(shù)調(diào)試分析這是一個比較簡單程序，調(diào)試過程中并沒有出現(xiàn)什么問題，思路比較清晰實(shí)驗(yàn)結(jié)果總結(jié)此次上機(jī)實(shí)驗(yàn)對二叉樹進(jìn)行了以一次實(shí)際操作，讓我對二叉樹有了更深的了解，對二叉樹的特性有了更熟悉的認(rèn)知，讓我知道了二叉樹的重要性和便利性，這對以后的編程有更好的幫助。七、源程序#include<iostream>#include<queue>usingnamespacestd;#defineTElemTypechar#defineStatusint#defineOK1#defineERROR0typedefstructBiTNode{ TElemTypedata; structBiTNode*lchild,*rchild;}BiTNode,*BiTree;StatusCreateBiTree(BiTree&T){ TElemTypech; cin>>ch; if(ch=='#') T=NULL; else { if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } returnOK;}StatusPreOrderTraverse(BiTreeT){ if(T) { cout<<T->data; if(PreOrderTraverse(T->lchild)) if(PreOrderTraverse(T->rchild)) returnOK; returnERROR; } else returnOK;}StatusInOrderTraverse(BiTreeT){ if(T) { InOrderTraverse(T->lchild); cout<<T->data; InOrderTraverse(T->rchild); } returnOK;}StatusPostOrderTraverse(BiTreeT){ if(T) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); cout<<T->data; } returnOK;}StatusleOrderTraverse(BiTreeT){ std::queue<BiTree>Q; if(T==NULL)returnERROR; else{ (T); while(!()) { T=(); (); cout<<T->data; if(T->lchild!=NULL) (T->lchild); if(T->rchild!=NULL) (T->rchild); } } returnOK;}Statuschange(BiTreeT){ BiTreetemp=NULL; if(T->lchild==NULL&&T->rchild==NULL) returnOK; else{ temp=T->lchild; T->lchild=T->rchild; T->rchild=temp; } if(T->lchild) change(T->lchild); if(T->rchild) change(T->rchild); returnOK;}intFindTreeDeep(BiTreeT){ intdeep=0; if(T){ intlchilddeep=FindTreeDeep(T->lchild); intrchilddeep=FindTreeDeep(T->rchild); deep=lchilddeep>=rchilddeeplchilddeep+1:rchilddeep+1; } returndeep;}intmain(){ BiTreeT; CreateBiTree(T); cout<<"先序遍歷順序?yàn)椋?; PreOrderTraverse(T); cout<<endl; cout<<"中序遍歷順序?yàn)椋?; InOrderTraverse(T); cout<<endl; cout<<"后序遍歷順序?yàn)椋?; PostOrderTraverse(T); cout<<endl; cout<<"層序遍歷順序?yàn)椋?; leOrderTraverse(T); cout<<endl;