【正文】 ．將二叉樹的基本操作算法也集中放在一個文件之中。包含關(guān)于二叉樹的鏈式結(jié)構(gòu)操作的一些基本算法，如：InitBiTree、DestroyBiTree、CreateBiTree、BiTreeEmpty、BiTreeDepth、Root、PreOrderTraverse等。3．將函數(shù)的測試和主函數(shù)組合成一個文件。四、參考程序（一）基本實驗的參考程序與實驗一相同。2． 中實現(xiàn)了二叉樹的鏈式存儲結(jié)構(gòu)定義typedef struct BiTNode{TElemType data。struct BiTNode *lchild,*rchild。 /* 左右孩子指針*/}BiTNode,*BiTree。3． 中實現(xiàn)二叉樹的基本操作（ 定義）/* 二叉樹的二叉鏈表存儲( 定義)的基本操作*/Status InitBiTree(BiTree amp。T){ /* 操作結(jié)果: 構(gòu)造空二叉樹T */T=NULL。return OK。}void DestroyBiTree(BiTree amp。T){ /* 初始條件: 二叉樹T 存在。操作結(jié)果: 銷毀二叉樹T */if(T) /* 非空樹*/{if(Tlchild) /* 有左孩子*/DestroyBiTree(Tlchild)。 /* 銷毀左孩子子樹*/if(Trchild) /* 有右孩子*/DestroyBiTree(Trchild)。 /* 銷毀右孩子子樹*/free(T)。 /* 釋放根結(jié)點*/T=NULL。 /* 空指針賦0 */}}define ClearBiTree DestroyBiTreevoid CreateBiTree(BiTree amp。T){ /* :按先序次序輸入二叉樹中結(jié)點的值（可為字符型或整型，*//*在主程中定義），構(gòu)造二叉鏈表表示的二叉樹T。變量Nil 表示空（子）樹。有改動*/TElemType ch。ifdef CHARscanf(%c,amp。ch)。endififdef INTscanf(%d,amp。ch)。endifif(ch==Nil) /* 空*/T=NULL。else{T=(BiTree)malloc(sizeof(BiTNode))。if(!T)exit(OVERFLOW)。Tdata=ch。 /* 生成根結(jié)點*/CreateBiTree(Tlchild)。 /* 構(gòu)造左子樹*/CreateBiTree(Trchild)。 /* 構(gòu)造右子樹*/}}Status BiTreeEmpty(BiTree T){ /* 初始條件: 二叉樹T 存在*//* 操作結(jié)果: 若T 為空二叉樹,則返回TRUE,否則FALSE */if(T)return FALSE。elsereturn TRUE。}int BiTreeDepth(BiTree T){ /* 初始條件: 二叉樹T 存在。操作結(jié)果: 返回T 的深度*/int i,j。if(!T)return 0。if(Tlchild)i=BiTreeDepth(Tlchild)。elsei=0。if(Trchild)j=BiTreeDepth(Trchild)。elsej=0。return ij?i+1:j+1。}TElemType Root(BiTree T){ /* 初始條件: 二叉樹T 存在。操作結(jié)果: 返回T 的根*/if(BiTreeEmpty(T))return Nil。elsereturn Tdata。}TElemType Value(BiTree p){ /* 初始條件: 二叉樹T 存在，p 指向T 中某個結(jié)點*//* 操作結(jié)果: 返回p 所指結(jié)點的值*/return pdata。}void Assign(BiTree p,TElemType value){ /* 給p 所指結(jié)點賦值為value */pdata=value。}void PreOrderTraverse(BiTree T,Status(*Visit)(TElemType)){ /* 初始條件: 二叉樹T 存在,Visit 是對結(jié)點操作的應用函數(shù)。，有改動*//* 操作結(jié)果: 先序遞歸遍歷T,對每個結(jié)點調(diào)用函數(shù)Visit 一次且僅一次*/if(T) /* T 不空*/{Visit(Tdata)。 /* 先訪問根結(jié)點*/PreOrderTraverse(Tlchild,Visit)。 /* 再先序遍歷左子樹*/PreOrderTraverse(Trchild,Visit)。 /* 最后先序遍歷右子樹*/}}void InOrderTraverse(BiTree T,Status(*Visit)(TElemType)){ /* 初始條件: 二叉樹T 存在,Visit 是對結(jié)點操作的應用函數(shù)*//* 操作結(jié)果: 中序遞歸遍歷T,對每個結(jié)點調(diào)用函數(shù)Visit 一次且僅一次*/if(T){InOrderTraverse(Tlchild,Visit)。 /* 先中序遍歷左子樹*/Visit(Tdata)。 /* 再訪問根結(jié)點*/InOrderTraverse(Trchild,Visit)。 /* 最后中序遍歷右子樹*/}}void PostOrderTraverse(BiTree T,Status(*Visit)(TElemType)){ /* 初始條件: 二叉樹T 存在,Visit 是對結(jié)點操作的應用函數(shù)*//* 操作結(jié)果: 后序遞歸遍歷T,對每個結(jié)點調(diào)用函數(shù)Visit 一次且僅一次*/if(T) /* T 不空*/{PostOrderTraverse(Tlchild,Visit)。 /* 先后序遍歷左子樹*/PostOrderTraverse(Trchild,Visit)。 /* 再后序遍歷右子樹*/Visit(Tdata)。 /* 最后訪問根結(jié)點*/}}4． 中，測試二叉樹基本算法的調(diào)用/* 的主程序,利用條件編譯選擇數(shù)據(jù)類型(另一種方法) *//* 二叉樹的數(shù)據(jù)類型可以以是字符型，也可以是整型，可在程序中使用條件編譯作出判斷和控制*/define CHAR /* 字符型，本例是采用字符型作為數(shù)據(jù)類型*//* define INT /* 整型（二者選一） */include /* 與實驗一的意義相同*/ifdef CHARtypedef char TElemType。TElemType Nil=39。 39。 /* 字符型以空格符為空*/endififdef INTtypedef int TElemType。TElemType Nil=0。 /* 整型以0 為空*/endifinclude /* 二叉樹鏈式存儲結(jié)構(gòu)定義*/include /* 二叉樹基本算法和擴展算法定義*/Status visitT(TElemType e){ifdef CHARprintf(%c ,e)。endififdef INTprintf(%d ,e)。endifreturn OK。}void main(){ BiTree T。TElemType e1。/* 1基本實驗算法的驗證*/InitBiTree(T)。printf(構(gòu)造空二叉樹后,樹空否？%d(1:是0:否) 樹的深度=%d\n,BiTreeEmpty(T),BiTreeDepth(T))。e1=Root(T)。if(e1!=Nil)ifdef CHARprintf(二叉樹的根為: %c\n,e1)。endififdef INTprintf(二叉樹的根為: %d\n,e1)。endifelseprintf(樹空，無根\n)。ifdef CHARprintf(請先序輸入二叉樹(如:ab 三個空格表示a 為根結(jié)點,b 為左子樹的二叉樹)\n)。endififdef INTprintf(請先序輸入二叉樹(如:1 2 0 0 0 表示1 為根結(jié)點,2 為左子樹的二叉樹)\n)。endifCreateBiTree(T)。printf(建立二叉樹后,樹空否？%d(1:是0:否) 樹的深度=%d\n,BiTreeEmpty(T),BiTreeDepth(T))。e1=Root(T)。if(e1!=Nil)ifdef CHARprintf(二叉樹的根為: %c\n,e1)。endififdef INTprintf(二叉樹的根為: %d\n,e1)。endifelseprintf(樹空，無根\n)。printf(中序遞歸遍歷二叉樹:\n)。InOrderTraverse(T,visitT)。printf(后序遞歸遍歷二叉樹:\n)。PostOrderTraverse(T,visitT)。}五、實驗環(huán)境和實驗步驟實驗環(huán)境： 利用Visual C++集成開發(fā)環(huán)境進行本實驗的操作。（一）基本實驗的實驗步驟：1．啟動VC++。2. 新建工程/Win32 Console Application，選擇輸入位置：如“d:\”，輸入工程的名稱：如“BinTreeDemo”。按“確定”按鈕，選擇“An Empty Project”，再按“完成”按鈕，3． 選中菜單的”project”—“add to project”— “files”選擇已存在文件，確定， 拷貝到所建的工程目錄下。4. 新建文件/C/C++ Header File，選中“添加到工程的復選按鈕”，輸入文件名“”，按“確定”按鈕，在顯示的代碼編輯區(qū)內(nèi)輸入如上的參考程序。5. 新建文件/C/C++ Header File，選中“添加到工程的復選按鈕”，輸入文件名“”，按“確定”按鈕，在顯示的代碼編輯區(qū)內(nèi)輸入如上的參考程序。6. 新建文件/C++ Source File，選中“添加到工程的復選按鈕”，輸入文件名“”，按“確定”按鈕，在顯示的代碼編輯區(qū)內(nèi)輸入如上的參考程序。7．構(gòu)件、調(diào)試、運行與實驗一相同，在此不再復述。實驗四：圖的數(shù)據(jù)結(jié)構(gòu)及其應用（必做： 2 學時）一、實驗目的：. 熟練掌握圖的兩種存儲結(jié)構(gòu)(鄰接矩陣和鄰接表)的表示方法. 掌握圖的基本運算及應用. 加深對圖的理解，逐步培養(yǎng)解決實際問題的編程能力二、實驗內(nèi)容:. 采用鄰接表或鄰接矩陣方式存儲圖，實現(xiàn)圖的深度遍歷和廣度遍歷。. 用廣度優(yōu)先搜索方法找出從一頂點到另一頂點邊數(shù)最少的路徑。1．問題描述：利用鄰接表存儲結(jié)構(gòu)，設(shè)計一種圖（有向或無向），并能夠?qū)ζ溥M行如下操作：. 創(chuàng)建一個可以隨機確定結(jié)點數(shù)和?。ㄓ邢蚧驘o向）數(shù)的圖。. 根據(jù)圖結(jié)點的序號，得到該結(jié)點的值。. 根據(jù)圖結(jié)點的位置的第一個鄰接頂點的序號，以及下一個鄰接頂點的序號。. 實現(xiàn)從第v 個頂點出發(fā)對圖進行深度優(yōu)先遞歸遍歷。. 實現(xiàn)對圖作深度優(yōu)先遍歷。. 實現(xiàn)對圖進行廣度優(yōu)先非遞歸遍歷。. 編寫主程序，實現(xiàn)對各不同的算法調(diào)用。2．實現(xiàn)要求：（以鄰接表存儲形式為例）編寫圖的基本操作函數(shù):：對圖的各項操作一定要編寫成為C（C++）語言函數(shù)，組合成模塊化的形式，每個算法的實現(xiàn)要從時間復雜度和空間復雜度上進行評價。.“建立圖的鄰接表算法”：CreateGraph(ALGraph *G)操作結(jié)果：采用鄰接表存儲結(jié)構(gòu),構(gòu)造沒有相關(guān)信息的圖G.“鄰接表表示的圖的遞歸深度優(yōu)先遍歷算法”：DFSTraverse(ALGraph G,void(*Visit)(char*))初始條件：圖G 已經(jīng)存在。操作結(jié)果：返回圖的按深度遍歷的結(jié)果。.“鄰接表表示的圖的廣度優(yōu)先遍歷算法”： BFSTraverse(ALGraph G,void(*Visit)(char*))初始條件：圖G 已經(jīng)存在。操作結(jié)果：返回圖的按廣度遍歷的結(jié)果。.“鄰接表從某個結(jié)點開始的廣度優(yōu)先遍歷算法”：BFS(ALGraph G, int v)初始條件：圖G 已經(jīng)存在。操作結(jié)果：返回圖從某個結(jié)點開始的按廣度遍歷的結(jié)果。分析: 修改輸入數(shù)據(jù)，預期輸出并驗證輸出的結(jié)果，加深對有關(guān)算法的理解。三、實驗指導:本實驗以圖的鄰接表存儲結(jié)構(gòu)為例，要求完成基本要求，同時對無向圖，有向網(wǎng)，無向網(wǎng)也一并實現(xiàn)其相關(guān)的操作，課后同學們可以用鄰接矩陣式存儲結(jié)構(gòu)完成以上操作。1． 首先將圖的鏈接存儲結(jié)構(gòu)定義放在一個頭文件：。2． .3．將函數(shù)的測試和主函數(shù)組合成一個文件，.由于要用到隊列技術(shù)，對于隊列的數(shù)據(jù)結(jié)構(gòu)定義和基本操作函數(shù)的描述就可以借助實驗二的結(jié)果，不必重寫。四、參考程序:1． 頭文件。2． 是鏈式隊列的存儲結(jié)構(gòu)。3． 是鏈式隊列的基本操作。4． 定義了圖的鏈接存儲結(jié)構(gòu)（以鄰接表存儲表示）define MAX_VERTEX_NUM 20typedef enum{DG,DN,AG,AN}GraphKind。 /* {有向圖,有向網(wǎng),無向圖,無向網(wǎng)} */typedef struct ArcNode{int adjvex。 /* 該弧所指向的頂點的位置*/struct ArcNode *nextarc。 /* 指向下一條弧的指針*/InfoType *info。 /* 網(wǎng)的權(quán)值指針） */}ArcNode。 /* 表結(jié)點*/typedef struct{VertexType data。 /* 頂點信息*/ArcNode *firs