二叉樹的應(yīng)用舉例實驗報告(燕山大學(xué))

1、題目： 二叉樹的應(yīng)用舉例 班級： 信息一班 姓名： 馮琴琴 學(xué)號： 1 得分： 實驗三 二叉樹的應(yīng)用舉例一、 實驗?zāi)康囊髮W(xué)生必須掌握二叉樹的建立及先序、中序、后序三種遍歷方式，在此基礎(chǔ)上實現(xiàn)樹的一些簡單應(yīng)用問題二、 實驗內(nèi)容及步驟1.二叉鏈表的建立，先（中、后）序遍歷輸入：字符串序列輸出：先（中、后）序序列處理方法：通過補虛結(jié)點，使二叉樹中各實際結(jié)點均具有左右孩子，再對該二叉樹按先序遍歷進(jìn)行輸入。以字符串的形式:根、左子樹、右子樹定義一棵二叉樹：1) 空樹以空白字符#表示2) 只含一個根結(jié)點的二叉樹（圖1示）以字符串A#表示3) 一般的二叉樹，以圖2為例，以下列字符串表示：AB#C#D#4)

2、 無論先序、中序、后序遍歷二叉樹，遍歷時的搜索路線是相同的：從根節(jié)點出發(fā)，逆時針沿二叉樹外緣移動，對每個節(jié)點均途經(jīng)三次。先序遍歷：第一次經(jīng)過節(jié)點時訪問。中序遍歷：第二次經(jīng)過節(jié)點時訪問。后序遍歷：第三次經(jīng)過節(jié)點時訪問圖1 圖2 2. 統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)，計算二叉樹的深度。輸入：字符串序列輸出：葉子結(jié)點的個數(shù)，二叉樹的深度處理方法：1) 先序遍歷二叉樹。在遍歷過程中查找葉子結(jié)點，并計數(shù)。由此，需在遍歷算法中增添一個“計數(shù)”的參數(shù)，并將算法中“訪問結(jié)點”的操作改為：若是葉子，則計數(shù)器增1。2) 后序遍歷二叉樹。從二叉樹深度的定義可知，二叉樹的深度應(yīng)為其左、右子樹深度的最大值加1。由此，先分別

3、求得左、右子樹的深度，算法中“訪問結(jié)點”的操作為：求得左、右子樹深度的最大值，然后加 1 。程序：#include#include #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1typedef char TElemType ;typedef int Status ;const int MAX_TREE_SIZE =100 ;const int TREEINCREMENT= 10 ;typedef struct BiTNode /結(jié)點結(jié)構(gòu) TElemType data; BiTNode *lc

4、hild,*rchild; / 左右孩子指針 BiTNode, *BiTree;Status InitBiTree(BiTree &T) if (!(T=new BiTNode) return ERROR; T-lchild=NULL; T-rchild=NULL; return OK; /InitBiTreevoid CreateBiTree(BiTree &T) TElemType e;cine;T-data=e;if(e!=#)InitBiTree(T-lchild);InitBiTree(T-rchild);CreateBiTree(T-lchild);CreateBiTree(T-r

5、child); void visit(TElemType e)coutedata!=#)call(T-data); PreOrderTraverse ( T-lchild, visit);PreOrderTraverse ( T-rchild, visit);void InOrderTraverse (BiTree T, void(*call)(TElemType e) /中序遍歷if(T-data!=#) InOrderTraverse( T-lchild, visit);call(T-data); InOrderTraverse( T-rchild, visit);void PostOrd

6、erTraverse (BiTree T, void(*call)(TElemType e) /后序遍歷if(T-data!=#) PostOrderTraverse( T-lchild, visit); PostOrderTraverse( T-rchild, visit);call(T-data); void CountLeaf (BiTree T, int &count)if(T-data!=#) if (T-lchild-data=#)&(T-rchild-data=#) count+; / 對葉子結(jié)點計數(shù) CountLeaf( T-lchild, count); CountLeaf(

7、 T-rchild, count); int BiTreeDepth (BiTree T) int ldepth,rdepth,depth; if(T-data=#) depth=0; else ldepth=BiTreeDepth (T-lchild); rdepth=BiTreeDepth (T-rchild); depth=1+(ldepthrdepth?ldepth:rdepth); return depth;void main() BiTree T;int depth,count=0;InitBiTree(T); CreateBiTree(T);cout先序遍歷:;PreOrderT

8、raverse ( T, visit);coutendl;cout中序遍歷:; InOrderTraverse( T, visit);coutendl;cout后序遍歷:;PostOrderTraverse( T, visit);coutendl;CountLeaf (T, count);cout此二叉樹葉子節(jié)點為:;coutcount;coutendl; depth=BiTreeDepth ( T);cout此二叉樹深度為:;cout depth;coutendl;運行結(jié)果：3.中序線索二叉鏈表的建立及遍歷輸入：字符串序列輸出：結(jié)點的相關(guān)信息，中序序列處理方法: 1) 在中序遍歷過程中修改結(jié)

9、點的左、右指針域，以保存當(dāng)前訪問結(jié)點的“前驅(qū)”和“后繼”信息。2) 遍歷過程中，附設(shè)指針pre, 并始終保持指針pre指向當(dāng)前訪問的指針p所指結(jié)點的前驅(qū)。3) 中序線索二叉樹結(jié)構(gòu)對稱。其中：第一個結(jié)點是最左下的結(jié)點，最后一個結(jié)點是最右下的結(jié)點。4) 在中序線索二叉樹上找結(jié)點的(直接)后繼/前驅(qū)方法：a) 若該結(jié)點有右孩子，其后繼為其右子樹中最左下的結(jié)點；b) 若該結(jié)點無右孩子，其后繼由rchild指向：其后繼為滿足以下條件的最小子樹的根r：該結(jié)點為r的左子樹中最右下的結(jié)點。程序：#include#include #define TRUE 1#define FALSE 0#define OK 1

10、#define ERROR 0#define OVERFLOW -1typedef char TElemType ;typedef int Status ;typedef enum Link, Thread PointerThr; /Link=0指針, Thread =1線索typedef struct BiThrNode TElemType data; BiThrNode *lchild, *rchild; /左右指針 PointerThr LTag, RTag; /左右標(biāo)志 BiThrNode, *BiThrTree;Status InitBiThrTree(BiThrTree &T) i

11、f (!(T=new BiThrNode) return ERROR; T-lchild=NULL; T-rchild=NULL;T-LTag=Link;T-RTag=Link; return OK; void CreateBiThrTree(BiThrTree &T) TElemType e;cine;T-data=e;if(e!=#)InitBiThrTree(T-lchild);InitBiThrTree(T-rchild);CreateBiThrTree(T-lchild);CreateBiThrTree(T-rchild); void InThreading(BiThrTree &p

12、re, BiThrTree &p) if(p-data!=#)InThreading(pre,p-lchild);if (p-lchild-data=#)p-LTag=Thread;p-lchild = pre; if (pre-rchild-data=#)pre -RTag=Thread;pre-rchild = p; pre = p; InThreading(pre,p-rchild); Status InOrderThreading(BiThrTree &Thrt, BiThrTree &T) BiThrTree pre,p;Thrt-RTag=Thread;Thrt-rchild=Thrt;if(!T)Thrt-lchild=Thrt;elseThrt-lchild=T;pre=Thrt; p=T; InThreading(pre, p); pre-RTag = Thread; pre-rchild = Thrt; Thrt-rchild=pre; return OK; void visit(TElemType e)coutelchild; while (p-LTag!=Thread)p=p-lchild;while(p-RTag!=Thread|p-rchild!=T) visit(p-d