《二叉樹基本操作實(shí)驗(yàn)報(bào)告》.doc

數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫(kù)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目二叉樹的基本操作及運(yùn)算學(xué)院：化學(xué)與材料科學(xué)學(xué)院專業(yè)班級(jí)：09級(jí)材料科學(xué)與工程系 PB0920603姓名：李維谷學(xué)號(hào)：PB09206285 郵箱：指導(dǎo)教師：賈伯琪實(shí)驗(yàn)時(shí)間：2010年10月17日一、 需要分析問(wèn)題描述：實(shí)現(xiàn)二叉樹（包括二叉排序樹）的建立，并實(shí)現(xiàn)先序、中序、后序和按層次遍歷，計(jì)算葉子結(jié)點(diǎn)數(shù)、樹的深度、樹的寬度，求樹的非空子孫結(jié)點(diǎn)個(gè)數(shù)、度為2的結(jié)點(diǎn)數(shù)目、度為2的結(jié)點(diǎn)數(shù)目，以及二叉樹常用運(yùn)算。問(wèn)題分析：二叉樹樹型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，對(duì)它的熟練掌握是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的基本要求。由于二叉樹的定義本身就是一種遞歸定義，所以二叉樹的一些基本操作也可采用遞歸調(diào)用的方法。處理本問(wèn)題，我覺(jué)得應(yīng)該：1、 建立二叉樹；2、 通過(guò)遞歸方法來(lái)遍歷（先序、中序和后序）二叉樹；3、 通過(guò)隊(duì)列應(yīng)用來(lái)實(shí)現(xiàn)對(duì)二叉樹的層次遍歷；4、 借用遞歸方法對(duì)二叉樹進(jìn)行一些基本操作，如：求葉子數(shù)、樹的深度寬度等；5、 運(yùn)用廣義表對(duì)二叉樹進(jìn)行廣義表形式的打印。算法規(guī)定：輸入形式：為了方便操作，規(guī)定二叉樹的元素類型都為字符型，允許各種字符類型的輸入，沒(méi)有元素的結(jié)點(diǎn)以空格輸入表示，并且本實(shí)驗(yàn)是以先序順序輸入的。輸出形式：通過(guò)先序、中序和后序遍歷的方法對(duì)樹的各字符型元素進(jìn)行遍歷打印，再以廣義表形式進(jìn)行打印。對(duì)二叉樹的一些運(yùn)算結(jié)果以整型輸出。程序功能：實(shí)現(xiàn)對(duì)二叉樹的先序、中序和后序遍歷，層次遍歷。計(jì)算葉子結(jié)點(diǎn)數(shù)、樹的深度、樹的寬度，求樹的非空子孫結(jié)點(diǎn)個(gè)數(shù)、度為2的結(jié)點(diǎn)數(shù)目、度為2的結(jié)點(diǎn)數(shù)目。對(duì)二叉樹的某個(gè)元素進(jìn)行查找，對(duì)二叉樹的某個(gè)結(jié)點(diǎn)進(jìn)行刪除。測(cè)試數(shù)據(jù)：輸 入 一：ABCDEGF （以表示空格）,查找5,刪除E 預(yù)測(cè)結(jié)果：先序遍歷 ABCDEGF 中序遍歷 CBEGDFA 后序遍歷 CGEFDBA 層次遍歷 ABCDEFG 廣義表打印 A（B（C,D（E（,G）,F） 葉子數(shù) 3 深度 5 寬度 2 非空子孫數(shù) 6 度為2的數(shù)目 2 度為1的數(shù)目2 查找5，成功，查找的元素為E刪除E后，以廣義表形式打印A（B（C,D（,F） 輸 入 二：ABDEHCFG （以表示空格）,查找10,刪除B 預(yù)測(cè)結(jié)果：先序遍歷 ABDEHCFG 中序遍歷 DBHEAGFC 后序遍歷 DHEBGFCA 層次遍歷 ABCDEFHG 廣義表打印 A（B(D,E(H),C(F(,G)） 葉子數(shù) 3 深度 4 寬度 3 非空子孫數(shù) 7 度為2的數(shù)目 2 度為1的數(shù)目3 查找10，失敗。刪除B后，以廣義表形式打印A（，C（F（，G）二、 概要設(shè)計(jì)程序中將涉及下列兩個(gè)抽象數(shù)據(jù)類型：一個(gè)是二叉樹，一個(gè)是隊(duì)列。1、設(shè)定“二叉樹”的抽象數(shù)據(jù)類型定義：ADT BiTree數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R： 若，則，稱BiTree為空二叉樹； 若，則，H是如下二元關(guān)系：（1） 在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無(wú)前驅(qū)；（2） 若則存在且;（3） 若則中存在唯一的元素,且存在上的關(guān)系若則中存在唯一的元素,且存在上的關(guān)系；（4） 是一棵符合本定義的二叉樹，稱為根的左子樹，是一棵符合本定義的二叉樹，稱為根的有字樹基本操作： CreateBiTree&T) 操作結(jié)果：按照T的定義構(gòu)造一個(gè)二叉樹。 BiTreeDepth(& T) 初始條件：二叉樹T已存在。 操作結(jié)果：返回T的深度。BiTreeWidth(&T)初始條件：二叉樹T已存在。 操作結(jié)果：返回T的寬度。PreOderTraverse&T) 初始條件：二叉樹T已存在。 操作結(jié)果：先序遍歷打印T，InOderTraverse(&T)初始條件：二叉樹T已存在。 操作結(jié)果：中序遍歷打印T。PostOderTraverse(&T)初始條件：二叉樹T已存在。 操作結(jié)果：后序遍歷打印T。LevelTraverse(&T)初始條件：二叉樹T已存在。 操作結(jié)果：層次遍歷T。DeleteXTree(&T,TElemType x)初始條件：二叉樹已存在。 操作結(jié)果：刪除元素為x的結(jié)點(diǎn)以及其左子樹和右子樹。 CopyTree(&T)初始條件：二叉樹T已存在。 操作結(jié)果：以T為模板，復(fù)制另一個(gè)二叉樹。ADT BiTree2、設(shè)定隊(duì)列的抽象數(shù)據(jù)類型定義：ADT Queue數(shù)據(jù)對(duì)象：D=數(shù)據(jù)關(guān)系：R1=|,i=2,，n約定端為隊(duì)列頭，端為隊(duì)列尾。基本操作： InitQueue(&Q) 操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。 EnQueue(&Q,&e) 初始條件：隊(duì)列Q已存在。 操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。 DeQueue(&Q) 初始條件：隊(duì)列Q已存在。 操作結(jié)果：刪除Q的對(duì)頭元素，并返回其值。 QueueEmpty(&Q) 初始條件：隊(duì)列Q已存在。 操作結(jié)果：若Q為空隊(duì)列，則返回1，否則0。 ADT Queue3、本程序包含四個(gè)模塊1）主程序模塊void main( )初始化；先序輸入二叉樹各結(jié)點(diǎn)元素；各種遍歷二叉樹；對(duì)二叉樹進(jìn)行常見(jiàn)運(yùn)算；復(fù)制二叉樹；在復(fù)制的二叉樹上進(jìn)行二叉樹的常見(jiàn)操作；2）二叉樹模塊實(shí)現(xiàn)二叉樹的抽象數(shù)據(jù)類型和基本操作2）隊(duì)列模塊實(shí)現(xiàn)隊(duì)列的抽象數(shù)據(jù)類型及今本操作3）廣義表打印模塊以廣義表形式打印二叉樹4）二叉樹運(yùn)算模塊對(duì)二叉樹的葉子、非空子孫結(jié)點(diǎn)數(shù)目、度為2或1的結(jié)點(diǎn)數(shù)三、 詳細(xì)設(shè)計(jì)1、主程序中需要的全程量#define M 10 / 統(tǒng)計(jì)二叉樹寬度時(shí)需用數(shù)組對(duì)每層寬度進(jìn)行存儲(chǔ)，這M表示數(shù)組的長(zhǎng)度2、隊(duì)列的建立與基本操作typedef struct QNodeBiTree data; /隊(duì)列中存儲(chǔ)的元素類型struct QNode *next; /指向二叉樹結(jié)點(diǎn)的指針 QNode,*Queueptr;typedef structQueueptr front; /隊(duì)列的隊(duì)頭指針Queueptr rear; /隊(duì)列的隊(duì)尾指針LinkQueue;算法描述：為了對(duì)二叉樹進(jìn)行層次遍歷，需要“先訪問(wèn)的結(jié)點(diǎn)，其孩子結(jié)點(diǎn)必然也先訪問(wèn)”，故需運(yùn)用到隊(duì)列。而考慮到層次遍歷對(duì)隊(duì)列操作的需要，只需進(jìn)行隊(duì)列的初始化，入隊(duì)和出隊(duì)以及檢查隊(duì)列是否為空。偽碼算法：void InitQueue(LinkQueue *Q)/初始化隊(duì)列申請(qǐng)一個(gè)結(jié)點(diǎn)Q-front=Q-rear=(Queueptr)malloc(sizeof(QNode);if(!Q-front)exit(1);/存儲(chǔ)分配失敗處理Q-front-next=NULL;/構(gòu)成帶頭結(jié)點(diǎn)里的空鏈隊(duì)列void EnQueue(LinkQueue *Q,BiTree e)/插入元素為e為Q的隊(duì)尾元素Queueptr q;q=(Queueptr)malloc(sizeof(QNode);if(!q)exit(1);q-data=e;q-next=NULL;Q-rear-next=q; /元素e的結(jié)點(diǎn)入列Q-rear=q;BiTree DeQueue(LinkQueue *Q)/從隊(duì)列中刪除隊(duì)頭元素，并直接返回給調(diào)用的主函數(shù)Queueptr p;BiTree q;if(Q-front=Q-rear)/隊(duì)列為空printf(ERROR!n);exit(1);p=Q-front-next;q=p-data;Q-front-next=p-next; /刪除該結(jié)點(diǎn)if(Q-rear=p)Q-rear=Q-front;free(p);return q;/返回隊(duì)頭元素int QueueEmpty(LinkQueue *Q)/檢查隊(duì)列是否為空，若為空則返回真值，否則返回0if(Q-front=Q-rear)return 1;elsereturn 0;3、二叉樹的建立與基本操作typedef struct BiTNodeTElemType data; /二叉樹結(jié)點(diǎn)存儲(chǔ)的元素類型struct BiTNode *lchild,*rchild; /二叉樹左右孩子指針BiTNode,*BiTree;算法分析：二叉樹的基本操作是本程序的核心，考慮到二叉樹的定義就是采用遞歸定義，所以很容易想到對(duì)二叉樹的操作可通過(guò)遞歸調(diào)用來(lái)實(shí)現(xiàn)。1）二叉樹的遍歷算法描述：二叉樹中常常要求在樹中查找具有某種特征的結(jié)點(diǎn)，或者對(duì)樹中全部結(jié)點(diǎn)逐一進(jìn)行某種處理，這就需要遍歷二叉樹。即要求按某條路徑尋訪樹中的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次?；仡櫠鏄涞倪f歸定義可知，二叉樹是由3個(gè)基本單元組成：根節(jié)點(diǎn)、左子樹和右子樹。因此，若能依次遍歷這三部分，便是遍歷了整棵二叉樹。如果以L、D、R分別表示遍歷左子樹、訪問(wèn)根結(jié)點(diǎn)和遍歷右子樹，則可有DLR、LDR、LRD、DRL、RDL、RLD這6種遍歷二叉樹的方案。若限定先右后左，則只有前三種情況，分別稱之為先（根）序遍歷。中（根）序遍歷和后（根）序遍歷?；诙鏄涞倪f歸定義，可得下述遍歷二叉樹的遞歸定義算法。先序遍歷二叉樹的操作定義：若二叉樹為空，則空操作；否則（1） 訪問(wèn)根結(jié)點(diǎn)；（2） 先序遍歷左子樹；（3） 先序遍歷右子樹。偽碼算法：void PreOderTraverse(BiTree T)/采用二叉鏈表存儲(chǔ)結(jié)構(gòu)if(T)putchar(T-data);/最簡(jiǎn)單的訪問(wèn)結(jié)點(diǎn)法，輸出結(jié)點(diǎn)元素，這里先訪問(wèn)根結(jié)點(diǎn)PreOderTraverse(T-lchild);PreOderTraverse(T-rchild);中序遍歷二叉樹的操作定義：若二叉樹為空，則空操作；否則（1） 中序遍歷左子樹；（2） 訪問(wèn)根結(jié)點(diǎn)；（3） 中序遍歷右子樹。偽碼算法：void InOderTraverse(BiTree T)/采用二叉鏈表存儲(chǔ)結(jié)構(gòu)if(T)InOderTraverse(T-lchild);/先遍歷左子樹putchar(T-data);/ 最簡(jiǎn)單的訪問(wèn)結(jié)點(diǎn)法，輸出結(jié)點(diǎn)元素，這里第二訪問(wèn)根結(jié)點(diǎn)InOderTraverse(T-rchild); 后序遍歷二叉樹的操作定義：若二叉樹為空，則空操作；否則（1） 后序遍歷左子樹；（2） 后序遍歷右子樹；（3） 訪問(wèn)根結(jié)點(diǎn)。偽碼算法：void PostOderTraverse(BiTree T)/采用二叉鏈表存儲(chǔ)結(jié)構(gòu)if(T)PostOderTraverse(T-lchild);/先遍歷左子樹PostOderTraverse(T-rchild);/再遍歷右子樹putchar(T-data);/最后訪問(wèn)根結(jié)點(diǎn) 2）二叉樹的建立算法描述：對(duì)二叉樹“遍歷”基本操作已經(jīng)建立的基礎(chǔ)上，可以在便利過(guò)程中對(duì)結(jié)點(diǎn)進(jìn)行各種操作，如：在遍歷過(guò)程中生成結(jié)點(diǎn)，建立二叉樹存儲(chǔ)結(jié)構(gòu)。采用先序遍歷建立二叉樹鏈表：（1） 按先序序列輸入二叉樹中結(jié)點(diǎn)的元素，以空格表示空，直到輸入回車為止；（2） 若元素值為空，則賦值NULL；否則生成一個(gè)新的結(jié)點(diǎn)，將元素值賦值給該跟結(jié)點(diǎn)的數(shù)值域；（3） 建立該跟結(jié)點(diǎn)的左子樹；（4） 建立該根結(jié)點(diǎn)的右子樹。偽碼算法;BiTree CreateBiTree(BiTree T)/構(gòu)造二叉樹T，按先序序列輸入二叉樹中結(jié)點(diǎn)的值（一個(gè)字符），空格表示空樹char ch;if(ch=getchar()= )T=NULL;elseif(ch!=n)if(!(T=(BiTree)malloc(sizeof(BiTNode)exit(1);T-data=ch; /生成根結(jié)點(diǎn)T-lchild=CreateBiTree(T-lchild);/構(gòu)造左子樹T-rchild=CreateBiTree(T-rchild);/構(gòu)造右子樹 return T;/返回所構(gòu)造二叉樹（子）樹的地址3）二叉樹的層次遍歷算法分析：有時(shí)需要一層層訪問(wèn)二叉樹，比如判斷二叉樹是否為完全二叉樹、找出指定層中含有的葉子/度為2/度為1的結(jié)點(diǎn)等，這就需要另一種遍歷方法層次遍歷。先訪問(wèn)的結(jié)點(diǎn)，其孩子結(jié)點(diǎn)必然也先訪問(wèn)，引入隊(duì)列存儲(chǔ)已被訪問(wèn)的，但其左右孩子尚未訪問(wèn)的結(jié)點(diǎn)的指針。算法描述:（1）若結(jié)點(diǎn)不為空，則訪問(wèn)該結(jié)點(diǎn)，并將其入列；（2）接著從隊(duì)列中取已被訪問(wèn)的，但其左右孩子尚未被訪問(wèn)的；（3）訪問(wèn)該結(jié)點(diǎn)的左孩子，將其入列；（4）訪問(wèn)該結(jié)點(diǎn)的右孩子，將其入列。偽碼算法：int visit(TElemType e)/簡(jiǎn)單的結(jié)點(diǎn)訪問(wèn)函數(shù)if(e)putchar(e);/打印該結(jié)點(diǎn)元素return 1;elsereturn 0;void LevelTraverse(BiTree T)LinkQueue *Q=(LinkQueue *)malloc(sizeof(LinkQueue);BiTree p=(BiTree)malloc(sizeof(BiTNode);InitQueue(Q);/初始化隊(duì)列，隊(duì)列的元素為二叉樹的結(jié)點(diǎn)指針if(T!=NULL)if(!visit(T-data)/訪問(wèn)該結(jié)點(diǎn)exit(1);EnQueue(Q,T);/將已被訪問(wèn)的，但左右孩子沒(méi)被訪問(wèn)的結(jié)點(diǎn)入列while(!QueueEmpty(Q)/隊(duì)列不為空，則尚有未被訪問(wèn)其孩子的結(jié)點(diǎn)p=DeQueue(Q);/將該結(jié)點(diǎn)出列，返回其地址if(p-lchild!=NULL)if(!visit(p-lchild-data)/訪問(wèn)左孩子exit(1);EnQueue(Q,p-lchild);/將其入列if(p-rchild!=NULL)if(!visit(p-rchild-data)/訪問(wèn)右孩子exit(1);EnQueue(Q,p-rchild);/將其入列4）求二叉樹的深度算法描述：（1） 若結(jié)點(diǎn)不為空，則求其左子樹的深度，并返回其值h1；（2） 求其右子樹的深度，也返回其值h2；（3） 選擇左右子樹深度的最大值，將其加一（該結(jié)點(diǎn)本身深度）即為該結(jié)點(diǎn)子樹的深度。偽碼算法：int BiTreeDepth(BiTree T)/后序遍歷求樹T所指二叉樹的深度int hl=0,hr=0;if(!T)return 0;elsehl=BiTreeDepth(T-lchild);/求左子樹的深度hr=BiTreeDepth(T-rchild);/求右子樹的深度if(hl=hr)return hl+1;else return hr+1;/子樹深度的最大值再加上本身所在結(jié)點(diǎn)的深度記為子樹的深度5）求二叉樹的寬度算法描述：（1） 定義一個(gè)數(shù)組，來(lái)存放每層的結(jié)點(diǎn)數(shù)，max來(lái)存放到這層為止時(shí)的最大結(jié)點(diǎn)數(shù)；（2） 計(jì)算每一層的結(jié)點(diǎn)數(shù)將其賦值給對(duì)應(yīng)的數(shù)組元素；（3） 每層計(jì)算完后，用max與本層結(jié)點(diǎn)數(shù)比較，若max小，則將本層結(jié)點(diǎn)數(shù)賦值給max;（4） 最后返回max。偽碼算法：int BiTreeWidth(BiTree T,int i)int static nM=0;/存放各層結(jié)點(diǎn)數(shù)，M為最先預(yù)料的最大樹的最大深度int static max=0;/最大寬度if(T!=NULL)if(i=1)/若是訪問(wèn)根結(jié)點(diǎn)ni+;/第一層加1i+;/到第二層if(T-lchild)ni+;/若有左孩子則該層加1if(T-rchild)ni+;/若有右孩子則該層加1else/訪問(wèn)子樹的結(jié)點(diǎn)i+;/向下一層if(T-lchild)ni+;if(T-rchild)ni+;if(maxlchild,i);/遍歷左子樹BiTreeWidth(T-rchild,i-);/網(wǎng)上退一層后遍歷右子樹return max;6）刪除二叉樹的某個(gè)結(jié)點(diǎn)算法描述：（1）先序遍歷找到該結(jié)點(diǎn)；（2）若此結(jié)點(diǎn)為空，不必釋放；若不為空，則先釋放其左右子樹的所有結(jié)點(diǎn)的空間，再賦為空；（3）再釋放根結(jié)點(diǎn)的空間，并將這個(gè)結(jié)點(diǎn)的父節(jié)點(diǎn)指向該結(jié)點(diǎn)的指針域賦為空。偽碼算法：BiTree DeleteBiTree(BiTree t)/釋放該結(jié)點(diǎn)空間的函數(shù)if(t!=NULL)t-lchild=DeleteBiTree(t-lchild);/釋放其左子樹的空間t-rchild=DeleteBiTree(t-rchild);/釋放右子樹的空間free(t);/釋放根結(jié)點(diǎn)的空間t=NULL;/將其值賦為空return t;BiTree DeleteXTree(BiTree t,TElemType x)/先序查找到需刪結(jié)點(diǎn)位置if(t!=NULL)if(t-data=x)/判斷是否為指定結(jié)點(diǎn)DeleteBiTree(t);/釋放樹的空間t=NULL; elset-lchild=DeleteXTree(t-lchild,x); t-rchild=DeleteXTree(t-rchild,x);return t;7）復(fù)制二叉樹算法描述:（1） 先復(fù)制其左子樹；（2） 再?gòu)?fù)制其右子樹；（3） 生成一個(gè)新結(jié)點(diǎn)，將根復(fù)制。偽碼算法：BiTree GetTreeNode(TElemType item,BiTree lptr,BiTree rptr)/生成一個(gè)其元素值為item，左指針為lpttr，右指針為rptr的結(jié)點(diǎn)BiTree t;t=(BiTree)malloc(sizeof(BiTNode);t-data=item;t-lchild=lptr;t-rchild=rptr;return t;BiTree CopyTree(BiTree T)/已知二叉樹的根指針T，返回它的復(fù)制品的根指針BiTree newlptr,newrptr,newnode;if(!T)return NULL;/復(fù)制一顆空樹if(T-lchild)newlptr=CopyTree(T-lchild);/復(fù)制（遍歷）其左子樹elsenewlptr=NULL;if(T-rchild)newrptr=CopyTree(T-rchild); /復(fù)制（遍歷）其右子樹elsenewrptr=NULL;newnode=GetTreeNode(T-data,newlptr,newrptr);/生成根結(jié)點(diǎn)return newnode;4、廣義表形式打印二叉樹算法分析：為了讓打印的二叉樹更形象，更清楚的反映二叉樹各結(jié)點(diǎn)的關(guān)系，采用廣義表形式打印則可以滿足要求。算法描述：（1）打印根結(jié)點(diǎn)，若其還有孩子，則輸出“（”；（2）若有左孩子，則打印左子樹；（3）若還有右子樹，則先打印“，”區(qū)分左右孩子，再打印右子樹，并輸出“）”表示輸除完畢。偽碼算法：void print(BiTree T)/廣義表形式打印二叉樹if(T!=NULL)printf(%c,T-data);if(T-lchild!=NULL | T-rchild!=NULL)/該結(jié)點(diǎn)還有孩子printf();print(T-lchild);/廣義表打印左子樹if(T-rchild!=NULL)printf(,);print(T-rchild);/廣義表打印右子樹printf();5、二叉樹的常見(jiàn)運(yùn)算1）求二叉樹的葉子數(shù)算法描述：（1） 若該結(jié)點(diǎn)無(wú)孩子，則表示為葉子，計(jì)數(shù)器加一；（2） 若該結(jié)點(diǎn)右孩子，求其左子樹的的葉子；（3） 再求其右子樹的葉子。偽碼算法：int LeafNum(BiTree T)/統(tǒng)計(jì)葉子數(shù)int static n=0;/定義一個(gè)靜態(tài)局部變量作為計(jì)數(shù)器if(T!=NULL)if(T-lchild=NULL & T-rchild=NULL)/結(jié)點(diǎn)無(wú)孩子n+;/計(jì)數(shù)器加一LeafNum(T-lchild);/求左子樹的葉子數(shù)LeafNum(T-rchild); /求右子樹的葉子數(shù)return n;2）求不同的度的結(jié)點(diǎn)數(shù)算法描述：（1） 定義一個(gè)靜態(tài)局部數(shù)組變量來(lái)統(tǒng)計(jì)不同度的結(jié)點(diǎn)數(shù)（2） 若該結(jié)點(diǎn)既有左孩子又有右孩子則度為2的計(jì)數(shù)器加一，若該節(jié)點(diǎn)只有左孩子或只有右孩子，則度為1的結(jié)點(diǎn)數(shù)的計(jì)數(shù)器加一、（3） 在對(duì)其左右子樹進(jìn)行相同操作。偽碼算法：int *JudgeCBT(BiTree T)/統(tǒng)計(jì)不同度的結(jié)點(diǎn)數(shù)int static d3=0;/d1作為度為1的計(jì)數(shù)器，d2作為度為2的計(jì)數(shù)器if(T!=NULL)if(T-lchild!=NULL & T-rchild!=NULL)/左右孩子都有d2+;else/只有一個(gè)孩子if(T-lchild!=NULL & T-rchild=NULL)d1+;elseif(T-lchild=NULL & T-rchild!=NULL)d1+;JudgeCBT(T-lchild);/統(tǒng)計(jì)左子樹JudgeCBT(T-rchild);/統(tǒng)計(jì)右孩子return d;/返回?cái)?shù)組的指針3）求非空子孫結(jié)點(diǎn)數(shù)算法描述：（1） 定義一個(gè)靜態(tài)局部變量，作為計(jì)數(shù)器；（2） 若該節(jié)點(diǎn)的左孩子非空則加一，右孩子非空亦加一；（3） 統(tǒng)計(jì)左子樹；統(tǒng)計(jì)右子樹。偽碼算法：int BiTreeDescendant(BiTree T)/統(tǒng)計(jì)非空子孫結(jié)點(diǎn)數(shù)int static n=0;/初始化計(jì)數(shù)器if(T!=NULL)if(T-lchild)n+;if(T-rchild)n+;BiTreeDescendant(T-lchild);/統(tǒng)計(jì)左子樹BiTreeDescendant(T-rchild);/統(tǒng)計(jì)右子樹return n;4）查找二叉樹的某個(gè)位置的結(jié)點(diǎn)（先序序列）算法描述：（1） 定義一個(gè)靜態(tài)局部變量，用作記錄已查結(jié)點(diǎn)的個(gè)數(shù)；（2） 從根節(jié)點(diǎn)開始，如果相查找的位置理由元素，則打印該元素，如果想查的位置超過(guò)二叉樹本身的元素?cái)?shù)則返回出錯(cuò)。偽碼算法：int PreOderKNode(BiTree T,int k,TElemType *e)/T為二叉樹，k為帶查找的結(jié)點(diǎn)位序；e為指針帶值返回查找到的數(shù)。int static count=0;/作為計(jì)數(shù)器，記錄已查找的結(jié)點(diǎn)數(shù)if(T=NULL)return 0;count+;/訪問(wèn)結(jié)點(diǎn)，對(duì)已訪問(wèn)的結(jié)點(diǎn)進(jìn)行計(jì)數(shù)if(count=k)/判斷該結(jié)點(diǎn)是否是待查找的結(jié)點(diǎn)e=&T-data;printf(存在你想查找位置的元素，先序序列中第%d個(gè)元素是%cn,k,*e);return 1;/查找成功elseif(countk)/計(jì)數(shù)器count已經(jīng)超出k，則直接返回0，查找不成功return 0;else/在左或右子樹中查找if(PreOderKNode(T-lchild,k,e)=0)return PreOderKNode(T-rchild,k,e);return 1;6、主程序的偽碼算法：void main()BiTree T=NULL,T_1=NULL,T_2=NULL;int i=1,*n=0,*kd,k=0; char x=0;printf(請(qǐng)按先序序列輸入各結(jié)點(diǎn)n);T=CreateBiTree(T);/先序序列構(gòu)造一棵二叉樹 /遍歷二叉樹printf(先序遍歷二叉樹：n);PreOderTraverse(T);putchar(n);printf(中序遍歷二叉樹：n);InOderTraverse(T);putchar(n);printf(后序遍歷二叉樹：n);PostOderTraverse(T);putchar(n);printf(層次遍歷二叉樹：n);LevelTraverse(T);putchar(n);printf(以廣義表形式打印二叉樹:n);/廣義表形式打印二叉樹print(T);putchar(n); /二叉樹的基本操作和運(yùn)算printf(二叉樹的葉子數(shù)LeafNumber為:%dn,LeafNum(T);/統(tǒng)計(jì)葉子數(shù)printf(二叉樹的深 度Depth為:%dn,BiTreeDepth(T);/計(jì)算深度printf(二叉樹的寬 度Width為:%dn,BiTreeWidth(T,i);/計(jì)算寬度 /統(tǒng)計(jì)非空子孫結(jié)點(diǎn)數(shù)printf(二叉樹非空子孫結(jié)點(diǎn)DescendantNumber數(shù)為:%dn,BiTreeDescendant(T);kd=JudgeCBT(T);/統(tǒng)計(jì)不同度的結(jié)點(diǎn)數(shù)printf(二叉樹度為1的結(jié)點(diǎn)數(shù)為:%d，度為2的結(jié)點(diǎn)數(shù)為:%dn,kd1,kd2); /二叉樹的基本操作，刪除和查找printf(下面進(jìn)行二叉數(shù)的查找和刪除操作n);T_2=CopyTree(T);putchar(n);/運(yùn)用二叉樹的復(fù)制操作printf(復(fù)制后的T_2,以先序序列輸出:n);PreOderTraverse(T_2);putchar(n);printf(請(qǐng)輸入你想查找在在先序序列的第幾個(gè)位置的元素n);scanf(%d,&k);if(!PreOderKNode(T_2,k,e)printf(不存在你想查找的位置n);T_1=CopyTree(T);putchar(n);printf(復(fù)制后的T_1,以先序序列輸出:n); PreOderTraverse(T_1);putchar(n);getchar();printf(請(qǐng)輸入你想刪除元素值為多少的結(jié)點(diǎn)n);x=getchar();getchar();DeleteXTree(T_1,x);printf(先序遍歷二叉樹：n); PreOderTraverse(T_1);putchar(n);printf(以廣義表形式打印二叉樹:n);print(T_1);putchar(n);四、 調(diào)試分析1、 在調(diào)試過(guò)程中，在進(jìn)行二叉樹的基本操作時(shí)就出現(xiàn)錯(cuò)誤了，為了方便檢查錯(cuò)誤，故逐漸將主函數(shù)的謀部分調(diào)用的函數(shù)先屏蔽后，再運(yùn)行調(diào)試，才發(fā)現(xiàn)了錯(cuò)誤。2、 在調(diào)試過(guò)程中，為了方便對(duì)調(diào)用函數(shù)的檢查，每當(dāng)計(jì)數(shù)器變化時(shí)，就輸出該值，就可以看出是哪里的問(wèn)題。3、 在調(diào)試過(guò)程中，在運(yùn)行刪除時(shí)，程序出現(xiàn)錯(cuò)誤，當(dāng)輸入欲刪除結(jié)點(diǎn)后，程序并沒(méi)有刪除該結(jié)點(diǎn)。后來(lái)經(jīng)過(guò)調(diào)試才發(fā)現(xiàn)，因?yàn)樵谳斎雱h除元素時(shí)，是由getchar（）接收，而在查找時(shí)遺留下的回車直接被getchar（）接收，當(dāng)作NULL去運(yùn)行了。4、 在調(diào)試過(guò)程中，更改了4的錯(cuò)誤，在刪除一個(gè)結(jié)點(diǎn)后，雖然能刪除元素了，但再次打印該樹后，就發(fā)現(xiàn)每當(dāng)打印到刪除結(jié)點(diǎn)位置時(shí)，程序就報(bào)錯(cuò)。后來(lái)經(jīng)過(guò)老師和同學(xué)的幫助才發(fā)現(xiàn)，雖然將待刪結(jié)點(diǎn)的空間釋放，但并沒(méi)有把指向該結(jié)點(diǎn)的父結(jié)點(diǎn)的指針域賦空，后來(lái)更改后，程序完美運(yùn)行了。5、 從程序?qū)嶒?yàn)題的編制過(guò)程中容易看出，線性表的廣泛應(yīng)用，特別是順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的二叉樹的應(yīng)用。五、 用戶使用說(shuō)明1、 本程序的運(yùn)行環(huán)境為Windows7旗艦版操作系統(tǒng)，執(zhí)行文件為：二叉樹的基本操作及運(yùn)算.exe；2、 進(jìn)入程序后即顯示提示信息：“請(qǐng)按先序序列輸入各結(jié)點(diǎn)”以等待用戶輸入欲構(gòu)造的二叉樹的各元素值；若用戶輸入的的是一個(gè)不符合先序序列的字符串，則程序報(bào)錯(cuò)；3、 在用戶正確輸入二叉樹的元素后，程序會(huì)自動(dòng)對(duì)其先序、中序、后序和層次遍歷，并對(duì)二叉樹進(jìn)行求葉子數(shù)、深度、寬度、非空子孫結(jié)點(diǎn)數(shù)、度為1的結(jié)點(diǎn)數(shù)和度為2的結(jié)點(diǎn)數(shù)。并在自動(dòng)復(fù)制一棵樹后，出現(xiàn)“請(qǐng)輸入你想查找在先序序列的第幾個(gè)位置的元素”，等待用戶輸入欲查找的元素位置；4、 輸入查找的位置后，如果存在該位置的元素，則程序會(huì)顯示“存在你想查找位置的元素，先序序列中第x個(gè)元素是x”；然后會(huì)彈出“請(qǐng)輸入你想刪除元素值為多少的結(jié)點(diǎn)”，等待用戶輸入某個(gè)元素值；5、 輸入某個(gè)元素值后，若刪除成功則會(huì)先序遍歷和廣義表形式打印刪除后的二叉樹。6、 本程序要求在輸入二叉樹元素是一定要正確，空格不能少，也不能多，不然程序會(huì)報(bào)錯(cuò)。六、 測(cè)試結(jié)果1、 正確輸入：ABCDEGF,查找5,刪除E運(yùn)行界面：2、 正確輸入：ABDEHCFG （以表示空格）,查找10,刪除B運(yùn)行界面：以上結(jié)果與自己在進(jìn)行程序概要分析時(shí)的預(yù)測(cè)結(jié)果一致七、 心得體會(huì)這次實(shí)驗(yàn)設(shè)計(jì)讓我更加了解并更加靈活運(yùn)用到大一學(xué)到的C程序設(shè)計(jì)和這個(gè)學(xué)期學(xué)到的數(shù)據(jù)結(jié)構(gòu)。實(shí)驗(yàn)任務(wù)要求不僅要求對(duì)課本知識(shí)有較深刻的了解，同時(shí)要求程序設(shè)計(jì)者有較強(qiáng)的思維和動(dòng)手能力和更加了解編程思想和編程技巧。這次實(shí)驗(yàn)設(shè)計(jì)讓我有一個(gè)深刻的體會(huì)，那就是細(xì)節(jié)決定成敗，編程最需要的是嚴(yán)謹(jǐn)，如何的嚴(yán)謹(jǐn)都不過(guò)分，往往檢查了半天發(fā)現(xiàn)錯(cuò)誤發(fā)生在某個(gè)括號(hào)，分號(hào)，引號(hào)，或者數(shù)據(jù)類型上。在進(jìn)行編程時(shí)一定要把每個(gè)問(wèn)題都分析清楚，比如自己在編寫刪除刪除BiTree DeleteBiTree(BiTree t)，BiTree DeleteXTree(BiTree t,TElemType x)時(shí)，只是把一個(gè)指針忘記賦為空，則導(dǎo)致程序報(bào)錯(cuò)，希望以后在運(yùn)用遞歸調(diào)用時(shí)，一定要弄清各種值的傳遞關(guān)系。還有，在編寫函數(shù)時(shí)，編寫時(shí)能把每一步的結(jié)果都打印出來(lái)，這能很方便的調(diào)試程序。在編寫實(shí)驗(yàn)報(bào)告時(shí)自己無(wú)意發(fā)現(xiàn)，其實(shí)統(tǒng)計(jì)非空子孫結(jié)點(diǎn)數(shù)、不同度的結(jié)點(diǎn)數(shù)甚至葉子數(shù)的函數(shù)思想與算法十分相似，都可以編寫在一個(gè)函數(shù)里，這也說(shuō)明了實(shí)驗(yàn)報(bào)告的重要性，我們應(yīng)該在實(shí)驗(yàn)報(bào)告里多反思、總結(jié)，盡量完善自己的程序設(shè)計(jì)。 程序設(shè)計(jì)時(shí)，也不要怕遇到錯(cuò)誤，在實(shí)際操作過(guò)程中犯的一些錯(cuò)誤還會(huì)有意外的收獲，感覺(jué)課程設(shè)計(jì)很有意思。在具體操作中這學(xué)期所學(xué)的數(shù)據(jù)結(jié)構(gòu)的理論知識(shí)得到鞏固，達(dá)到課程設(shè)計(jì)的基本目的，也發(fā)現(xiàn)自己的不足之出，在以后的上機(jī)中應(yīng)更加注意，同時(shí)體會(huì)到C語(yǔ)言具有的語(yǔ)句簡(jiǎn)潔，使用靈活，執(zhí)行效率高等特點(diǎn)。發(fā)現(xiàn)上機(jī)的重要作用，特別算術(shù)表達(dá)式有了深刻的理解。最后，感謝老師在這次課程設(shè)計(jì)的悉心指導(dǎo)，祝老師身體健康，工作順利。參考文獻(xiàn)：1.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版) 嚴(yán)蔚敏 清華大學(xué)出版社 2.C程序設(shè)計(jì) 譚浩強(qiáng) 清華大學(xué)出版社 3.數(shù)據(jù)結(jié)構(gòu)題集（C語(yǔ)言版）嚴(yán)蔚敏 吳偉民 米寧 清華大學(xué)出版社 4.C程序設(shè)計(jì)學(xué)習(xí)指導(dǎo)與練習(xí)賈伯琪 中國(guó)科學(xué)技術(shù)大學(xué)出版社八、 附錄“二叉樹的基本操作及運(yùn)算”源程序代碼：#include#include#includetypedef char TElemType;char *e;#define M 10typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;typedef struct QNodeBiTree data;struct QNode *next;QNode,*Queueptr;typedef structQueueptr front;Queueptr rear;LinkQueue;void InitQueue(LinkQueue *Q)Q-front=Q-rear=(Queueptr)malloc(sizeof(QNode);if(!Q-front)exit(1);Q-front-next=NULL;void EnQueue(LinkQueue *Q,BiTree e)Queueptr q;q=(Queueptr)malloc(sizeof(QNode);if(!q)exit(1);q-data=e;q-next=NULL;Q-rear-next=q;Q-rear=q;BiTree DeQueue(LinkQueue *Q)Queueptr p;BiTree q;if(Q-front=Q-rear)printf(ERROR!n);exit(1);p=Q-front-next;q=p-data;Q-front-next=p-next;if(Q-rear=p)Q-rear=Q-front;free(p);return q;int QueueEmpty(LinkQueue *Q)if(Q-front=Q-rear)return 1;elsereturn 0;BiTree CreateBiTree(BiTree T)char ch;if(ch=getchar()= )T=NULL;elseif(ch!=n)if(!(T=(BiTree)malloc(sizeof(BiTNode)exit(1);T-data=ch;T-lchild=CreateBiTree(T-lchild);T-rchild=CreateBiTree(T-rchild);return T;void PreOderTraverse(BiTree T)if(T)putchar(T-data);PreOderTraverse(T-lchild);PreOderTraverse(T-rchild);void InOderTraverse(BiTree T)if(T)InOderTraverse(T-lchild);putchar(T-data);InOderTraverse(T-rchild);void PostOderTraverse(BiTree T)if(T)PostOderTraverse(T-lchild);PostOderTraverse(T-rchild);putchar(T-data);int visit(TElemType e)if(e)putchar(e);return 1;elsereturn 0;void LevelTraverse(BiTree T)LinkQueue *Q=(LinkQueue *)malloc(sizeof(LinkQueue);BiTree p=(BiTree)malloc(sizeof(BiTNode);InitQueue(Q);if(T!=NULL)if(!visit(T-data)exit(1);EnQueue(Q,T);while(!QueueEmpty(Q)p=DeQueue(Q);if(p-lchild!=NULL)if(!visit(p-lchild-data)exit(1);EnQueue(Q,p-lchild);if(p-rchild!=NULL)if(!visit(p-rchild-data)exit(1);EnQueue(Q,p-rchild);int BiTreeDepth(BiTree T)int hl=0,hr=0;if(!T)return 0;elsehl=BiTreeDepth(T-lchild);hr=BiTreeDepth(T-rchild);if(hl=hr)return hl+1;else return hr+1;int BiTreeWidth(BiTree T,int i)int static nM=0;int static max=0;if(T!=NULL)if(i=1)ni+;i+;if(T-lchild)ni+;if(T-rchild)ni+;elsei+;if(T-lchild)ni+;if(T-rchild)ni+;if(maxlchild,i);BiTreeWidth(T-