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

實(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) （必做題）問題描述建立一棵二叉樹，試編程實(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ù)如輸入：ABCDEGF（其中表示空格字符）則輸出結(jié)果為 先序：ABCDEGF中序：CBEGDFA后序：CGEFDBA層序：ABCDEFG選作內(nèi)容采用非遞歸算法實(shí)現(xiàn)二叉樹遍歷。三、 算法設(shè)計(jì) 1、 主要思想：根據(jù)二叉樹的圖形結(jié)構(gòu)創(chuàng)建出二叉樹的數(shù)據(jù)結(jié)構(gòu)，然后用指針對樹進(jìn)行操作，重點(diǎn)掌握二叉樹的結(jié)構(gòu)和性質(zhì)。2、 本程序包含四個(gè)模塊：（1） 結(jié)構(gòu)體定義 （2） 創(chuàng)建二叉樹 （3） 對樹的幾個(gè)操作 （4） 主函數(shù)四、 調(diào)試分析這是一個(gè)比較簡單程序，調(diào)試過程中并沒有出現(xiàn)什么問題，思路比較清晰五、 實(shí)驗(yàn)結(jié)果六、 總結(jié)此次上機(jī)實(shí)驗(yàn)對二叉樹進(jìn)行了以一次實(shí)際操作，讓我對二叉樹有了更深的了解，對二叉樹的特性有了更熟悉的認(rèn)知，讓我知道了二叉樹的重要性和便利性，這對以后的編程有更好的幫助。七、源程序#include#includeusing namespace std;#define TElemType char#define Status int#define OK 1#define ERROR 0typedef struct BiTNodeTElemType data;struct BiTNode * lchild, *rchild;BiTNode,* BiTree;Status CreateBiTree(BiTree &T)TElemType ch;cin ch;if (ch = #)T = NULL;elseif (!(T = (BiTNode *)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data = ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);return OK;Status PreOrderTraverse(BiTree T)if (T)cout data;if (PreOrderTraverse(T-lchild)if (PreOrderTraverse(T-rchild)return OK;return ERROR;elsereturn OK;Status InOrderTraverse(BiTree T)if (T)InOrderTraverse(T-lchild);cout data;InOrderTraverse(T-rchild);return OK;Status PostOrderTraverse(BiTree T)if (T)PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);cout data;return OK;Status leOrderTraverse(BiTree T)std:queue Q;if (T = NULL)return ERROR;elseQ.push(T);while (!Q.empty()T = Q.front();Q.pop();cout data;if (T-lchild != NULL)Q.push(T-lchild);if (T-rchild != NULL) Q.push(T-rchild);return OK;Status change(BiTree T)BiTree temp = NULL;if (T-lchild = NULL & T-rchild = NULL)return OK;elsetemp = T-lchild;T-lchild = T-rchild;T-rchild = temp;if (T-lchild)change(T-lchild);if (T-rchild)change(T-rchild);return OK;int FindTreeDeep(BiTree T)int deep = 0;if (T)int lchilddeep = FindTreeDeep(T-lchild);int rchilddeep = FindTreeDeep(T-rchild);deep = lchilddeep = rchilddeep ? lchilddeep + 1 : rchilddeep + 1;return deep;int main()BiTree T;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