1、樹和森林應(yīng)用實驗實驗報告實驗?zāi)康?1)掌握樹和森林的二叉鏈表表示方法。(2)掌握樹和二叉樹的結(jié)構(gòu)及算法之間的對應(yīng)關(guān)系。(3)掌握樹的兩種遍歷算法及其應(yīng)用。實驗運行環(huán)境Visual C+實驗任務(wù)為使實驗程序簡潔直觀，下面的部分實驗程序中的一些功能實現(xiàn)仍以調(diào)用庫函數(shù)程序trees.h中的函數(shù)的形式給出，并假設(shè)該庫函數(shù)中定義了樹指針和結(jié)點類型分別為tree和tnode，以及部分常用運算，例如構(gòu)建樹（森林）、以某種方式顯示樹和森林等。各運算的名稱較為直觀，因而易于理解。讀者可自行設(shè)計自己的庫函數(shù)，也可到作者的網(wǎng)站下載。說明2：為便于數(shù)據(jù)的描述，和前面的實驗一樣，將測試數(shù)據(jù)結(jié)構(gòu)列出，并以一個文件名的形式

2、給出標(biāo)注，例如測試數(shù)據(jù)名為tree1.tre的樹，其具體結(jié)構(gòu)形式參見附錄中的樹列表中的標(biāo)有tree1.tre的樹。實驗內(nèi)容第一題：將一棵樹（或森林）轉(zhuǎn)換為二叉樹。實驗測試數(shù)據(jù)基本要求：第一組數(shù)據(jù)： tree1.tre第二組數(shù)據(jù)： tree2.tre實驗準(zhǔn)備：用廣義表來表示樹的數(shù)據(jù)，保存到文件中，通過文件流來讀入數(shù)據(jù)，并根據(jù)讀入的數(shù)據(jù)來創(chuàng)建樹第二題：求森林的高度。實驗測試數(shù)據(jù)基本要求：第一組數(shù)據(jù)： tree1.tre第二組數(shù)據(jù)： tree2.tre第一組數(shù)據(jù)： full41.cbt第二組數(shù)據(jù)： letter.cbt實驗準(zhǔn)備：遍歷每一棵樹，尋找高度的最大值?？梢栽O(shè)立一個私有成員來記錄數(shù)的高度。第三

3、題：按層次方式遍歷森林。實驗測試數(shù)據(jù)基本要求：第一組數(shù)據(jù)： tree1.tre第二組數(shù)據(jù)： tree2.tre實驗準(zhǔn)備：先訪問第一層結(jié)點，并將它放入隊列中，并反復(fù)從隊列中取結(jié)點，訪問其孩子結(jié)點，直至訪問到葉子結(jié)點。第四題：輸出一個森林中每個結(jié)點的值及其對應(yīng)的層次數(shù)。實驗測試數(shù)據(jù)基本要求：第一組數(shù)據(jù)： tree1.tre第二組數(shù)據(jù)： tree2.tre實驗準(zhǔn)備：使用遞歸函數(shù)來訪問森林，同時輸出層次數(shù)及結(jié)點值，使用形參來傳遞當(dāng)前層次數(shù)第五題：輸出一個森林的廣義表形式，如下圖中的森林的輸出為：(a(b(c,d,e,f)，g(h,i,j)，k(l,m,n)，o(p(q)，r(s(t(u)，v(w(x,

4、y,z) 實驗測試數(shù)據(jù)基本要求：第一組數(shù)據(jù)： tree1.tre第二組數(shù)據(jù)： tree2.tre實驗準(zhǔn)備：使用遞歸函數(shù)調(diào)用，若當(dāng)前節(jié)點有左孩子，則先輸出 (再訪問下一節(jié)點，若當(dāng)前節(jié)點的右指針不為空，則先輸出,再訪問下一結(jié)點。實驗測試數(shù)據(jù)實驗程序#include using namespace std;typedef char ElemType;#define MAX 200typedef struct CSNode ElemType data; struct CSNode *firstchild , *nejtsibling ; CSNode , *CSTree;typedef struct

5、BTNode ElemType data; struct BTNode *lchild , *rchild ; BTNode,*BTree;class FOREST public : FOREST(); CSTree returnT(); /輸出森林的根結(jié)點 BTree returnBT(); /輸出森林的根結(jié)點 CSTree creat(CSTree &T); /創(chuàng)建森林 BTree change(CSTree &T,BTree &BT1); /將森林轉(zhuǎn)換成為二叉樹 void first(CSTree &T,int i); /第一題：按照先序遍歷的方式來輸出樹林每個結(jié)點的值以及層次 void

6、 second(CSTree &T); /第五題：輸出一個森林的廣義表形式 void third(const CSTree &T); /第三題：按層次方式遍歷森林。 void fourth(BTree &BT); /第四題：按照先序遍歷的方式來輸出二叉樹每個結(jié)點的值 int higth(const CSTree &T); /第二題：求森林的高度 private : CSTree T; /森林的頭結(jié)點 BTree BT; /二叉樹的頭結(jié)點 int high; /森林的高度 ;FOREST : FOREST() high = 0; T = NULL; BT = NULL; CSTree FORES

7、T : returnT() return T; BTree FOREST : returnBT() return BT; CSTree FOREST : creat(CSTree &T) int a ,b; T = new CSNode; cinT-dataab; if(a = 1) T-firstchild = NULL; else creat(T-firstchild); if(b = 1) T-nejtsibling = NULL; else creat(T-nejtsibling); return T;BTree FOREST : change(CSTree &T,BTree &BT)

8、 if(!T) BT = NULL; return NULL; BT = new BTNode; BT - data = T - data; if(!T-firstchild) BT-lchild = NULL; else change(T-firstchild,BT-lchild); if(!T-nejtsibling) BT-rchild = NULL; else change(T-nejtsibling,BT-rchild); return BT; void FOREST : first(CSTree &T,int i) if(!T) return ; coutdata ifirstch

9、ild) first(T-firstchild,i+1); if(T-nejtsibling) first(T-nejtsibling,i); void FOREST : second(CSTree &T) if(!T) return ; coutdata; if(T-firstchild) coutfirstchild); if(T-nejtsibling) coutnejtsibling); else cout nejtsibling ; while(i!=j) CSTree q; q = Sj+; cout data firstchild; while(q) Si+ = q; q = q

10、 - nejtsibling; void FOREST : fourth(BTree &BT) if(!BT) return ; coutdatalchild) fourth(BT-lchild); if(BT-rchild) fourth(BT-rchild); int FOREST : higth(const CSTree &T) int hs,hb; if(!T) return 0; hs = higth(T-firstchild) ; hb = higth(T-nejtsibling); high = (hs + 1) hb ? (hs + 1) : hb; return high;

11、int main() FOREST f_1,f_2,f_3,f_4,f_5; int chioce; coutendl;cout數(shù)據(jù)結(jié)構(gòu)實驗五-樹和森林應(yīng)用實驗endl;coutendl;cout第1題: 將一棵樹（或森林）轉(zhuǎn)換為二叉樹endl;cout第2題: 求森林的高度endl;cout第3題: 按層次方式遍歷森林endl;cout第4題: 輸出一個森林中每個結(jié)點的值及其對應(yīng)的層次數(shù)endl;cout第5題: 輸出一個森林的廣義表形式endl;cout退出程序:0endl; coutendl; cout請選擇一道題chioce; switch (chioce) case 1: cout請

12、輸入森林的元素endl; CSTree p1; BTree p; p1 = f_1.returnT();p = f_1.returnBT(); p1 = f_1.creat(p1); p = f_1.change(p1,p); cout按照二叉樹先序遍歷的結(jié)果是：endl; f_1.fourth(p); coutendl; break; case 2: cout請輸入森林的元素endl; CSTree p2; p2 = f_2.returnT(); p2 = f_2.creat(p2); cout森林的高度是：; coutf_2.higth(p2); coutendl; break; case 3: cout請輸入森林的元素endl; CSTree p3; p3 = f_3.returnT(); p3 = f_3.creat(p3); cout按照層次遍歷的結(jié)果是：endl; f_3.third(p3); coutendl; break; case 4: cout請輸入森林的元素endl; CSTree p4; p4 = f_3.returnT(); p4 = f_3.creat(p4); cout按照森林先序遍歷輸出的結(jié)果是輸出endl; cout一個森林中每個結(jié)點的值及其對應(yīng)的層次數(shù)：endl; f_3.first(p4,1); coutendl; brea