。實(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) （必做題）[問(wèn)題描述]建立一棵二叉樹，試編程實(shí)現(xiàn)二叉樹的如下基本操作：1. 按先序序列構(gòu)造一棵二叉鏈表表示的二叉樹 T；對(duì)這棵二叉樹進(jìn)行遍歷：先序、中序、后序以及層次遍歷，分別輸出結(jié)點(diǎn)的遍歷序列；求二叉樹的深度/結(jié)點(diǎn)數(shù)目/葉結(jié)點(diǎn)數(shù)目；(選做)將二叉樹每個(gè)結(jié)點(diǎn)的左右子樹交換位置。（選做）[基本要求]從鍵盤接受輸入（先序），以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，建立二叉樹（以先序來(lái)建立），[測(cè)試數(shù)據(jù)]如輸入：ABCффDEфGффFффф（其中ф表示空格字符）則輸出結(jié)果為先序：ABCDEGF中序：CBEGDFA后序：CGEFDBA層序：ABCDEFG[選作內(nèi)容]采用非遞歸算法實(shí)現(xiàn)二叉樹遍歷。三、 算法設(shè)計(jì)1、 主要思想：根據(jù)二叉樹的圖形結(jié)構(gòu)創(chuàng)建出二叉樹的數(shù)據(jù)結(jié)構(gòu)，然后用指針對(duì)樹進(jìn)行操作，重點(diǎn)掌握二叉樹的結(jié)構(gòu)和性質(zhì)。2、 本程序包含四個(gè)模塊：（1）結(jié)構(gòu)體定義精選資料，歡迎下載。2）創(chuàng)建二叉樹3）對(duì)樹的幾個(gè)操作4）主函數(shù)四、 調(diào)試分析這是一個(gè)比較簡(jiǎn)單程序，調(diào)試過(guò)程中并沒(méi)有出現(xiàn)什么問(wèn)題，思路比較清晰五、 實(shí)驗(yàn)結(jié)果六、 總結(jié)此次上機(jī)實(shí)驗(yàn)對(duì)二叉樹進(jìn)行了以一次實(shí)際操作，讓我對(duì)二叉樹有了更深的了解，對(duì)二叉樹的特性有了更熟悉的認(rèn)知，讓我知道了二叉樹的重要性和便利性，這對(duì)以后的編程有更好的幫助。七、源程序#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;}elsereturnOK;}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{Q.push(T);while(!Q.empty()){T=Q.front();Q.pop();cout<<T->data;if(T->lchild!=NULL)Q.push(T->lchild);if(T->rchild!=NULL)Q.push(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>=rchilddeep?lchilddeep+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;cout<<" 二叉樹深度為："<<FindTreeDeep(T)<<endl;cout<<