《數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)報(bào)告-二叉樹.pdf》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)報(bào)告-二叉樹.pdf（27頁珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目實(shí)驗(yàn)題目二叉樹的基本操作及運(yùn)算二叉樹的基本操作及運(yùn)算一、一、需要分析需要分析問題描述：?jiǎ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)算。問題分析：?jiǎn)栴}分析：二叉樹樹型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，對(duì)它的熟練掌握是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的基本要求。由于二叉樹的定義本身就是一種遞歸定義，所以二叉樹的一些基本操作也可采用遞歸調(diào)用的方法。處理本問題，我覺得應(yīng)該：第 1 頁 共 27 頁1、建立二叉樹；

2、2、通過遞歸方法來遍歷（先序、中序和后序）二叉樹；3、通過隊(duì)列應(yīng)用來實(shí)現(xiàn)對(duì)二叉樹的層次遍歷；4、借用遞歸方法對(duì)二叉樹進(jìn)行一些基本操作，如：求葉子數(shù)、樹的深度寬度等；5、運(yùn)用廣義表對(duì)二叉樹進(jìn)行廣義表形式的打印。算法規(guī)定：算法規(guī)定：輸入形式：為了方便操作，規(guī)定二叉樹的元素類型都為字符型，允許各種字符類型的輸入，沒有元素的結(jié)點(diǎn)以空格輸入表示，并且本實(shí)驗(yàn)是以先序順序輸入的。輸出形式：通過先序、中序和后序遍歷的方法對(duì)樹的各字符型元素進(jìn)行遍歷打印，再以廣義表形式進(jìn)行打印。對(duì)二叉樹的一些運(yùn)算結(jié)果以整型輸出。程序功能：實(shí)現(xiàn)對(duì)二叉樹的先序、中序和后序遍歷，層次遍歷。計(jì)算葉子結(jié)點(diǎn)數(shù)、樹的深度、樹的寬度，求樹的非空

3、子孫結(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ù)：測(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é)果：先序遍歷 A

4、BDEHCFG中序遍歷 DBHEAGFC后序遍歷 DHEBGFCA層次遍歷 ABCDEFHG廣義表打印 A（B(D,E(H),C(F(,G)）葉子數(shù) 3 深度 4 寬度 3 非空子孫數(shù) 7度為 2 的數(shù)目 2 度為 1 的數(shù)目 3查找 10，失敗。第 2 頁 共 27 頁刪除 B 后，以廣義表形式打印A（，C（F（，G）二、二、概要設(shè)計(jì)概要設(shè)計(jì)程序中將涉及下列兩個(gè)抽象數(shù)據(jù)類型：一個(gè)是二叉樹，一個(gè)是隊(duì)列。1 1、設(shè)定“二叉樹”的抽象數(shù)據(jù)類型定義：、設(shè)定“二叉樹”的抽象數(shù)據(jù)類型定義：ADTADT BiTree數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 D D：D 是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R R：若

5、D ，則R ，稱 BiTree 為空二叉樹；若D ，則R H，H 是如下二元關(guān)系：（1）在 D 中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系 H 下無前驅(qū)；（2）若D root,則存在D rootDl,Dr,且Dl Dr;（3）若Dl,則Dl中存在唯一的元素xl,root,xlH,且存在Dl上的關(guān)系Hl H;若Dr,則Dr中存在唯一的元素xr,root,xrH,且存在Dr上的關(guān)系Hr H;H root,xl,root,xr,Hl,Hr；（4）Dl,Hl是一棵符合本定義的二叉樹，稱為根的左子樹，Dr,Hr是一棵符合本定義的二叉樹，稱為根的有字樹基本操作：基本操作：CreateBiTree&T)

6、操作結(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。第 3 頁 共 2

7、7 頁DeleteXTree(&T,TElemType x)初始條件：二叉樹已存在。操作結(jié)果：刪除元素為x 的結(jié)點(diǎn)以及其左子樹和右子樹。CopyTree(&T)初始條件：二叉樹 T 已存在。操作結(jié)果：以 T 為模板，復(fù)制另一個(gè)二叉樹。ADTADT BiTree2 2、設(shè)定隊(duì)列的抽象數(shù)據(jù)類型定義：、設(shè)定隊(duì)列的抽象數(shù)據(jù)類型定義：ADTADT Queue數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：D=aiai BiTree,i N 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R1=|ai1,aiD,i=2,，n約定a1端為隊(duì)列頭，an端為隊(duì)列尾?；静僮鳎夯静僮鳎篒nitQueue(&Q)操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。EnQueue(&Q,&e)

8、初始條件：隊(duì)列 Q 已存在。操作結(jié)果：插入元素e 為 Q 的新的隊(duì)尾元素。DeQueue(&Q)初始條件：隊(duì)列 Q 已存在。操作結(jié)果：刪除 Q 的對(duì)頭元素，并返回其值。QueueEmpty(&Q)初始條件：隊(duì)列 Q 已存在。操作結(jié)果：若 Q 為空隊(duì)列，則返回 1，否則 0。ADT ADT Queue3 3、本程序包含四個(gè)模塊、本程序包含四個(gè)模塊1）主程序模塊voidvoid main()初始化；先序輸入二叉樹各結(jié)點(diǎn)元素；各種遍歷二叉樹；對(duì)二叉樹進(jìn)行常見運(yùn)算；復(fù)制二叉樹；在復(fù)制的二叉樹上進(jìn)行二叉樹的常見操作；2）二叉樹模塊實(shí)現(xiàn)二叉樹的抽象數(shù)據(jù)類型和基本操作2）隊(duì)列模塊實(shí)現(xiàn)隊(duì)列的抽象數(shù)據(jù)類型及今本

9、操作3）廣義表打印模塊以廣義表形式打印二叉樹4）二叉樹運(yùn)算模塊對(duì)二叉樹的葉子、非空子孫結(jié)點(diǎn)數(shù)目、度為2 或 1 的結(jié)點(diǎn)數(shù)三、三、詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì)第 4 頁 共 27 頁1 1、主程序中需要的全程量、主程序中需要的全程量#define M 10/統(tǒng)計(jì)二叉樹寬度時(shí)需用數(shù)組對(duì)每層寬度進(jìn)行存儲(chǔ)，這M 表示數(shù)組的長(zhǎng)度2 2、隊(duì)列的建立與基本操作、隊(duì)列的建立與基本操作typedeftypedef strucstruct QNodeBiTree data;/隊(duì)列中存儲(chǔ)的元素類型struct QNode*next;/指向二叉樹結(jié)點(diǎn)的指針QNode,*Queueptr;typedeftypedef struct

10、structQueueptr front;/隊(duì)列的隊(duì)頭指針Queueptr rear;/隊(duì)列的隊(duì)尾指針LinkQueue;算法描述：算法描述：為了對(duì)二叉樹進(jìn)行層次遍歷，需要“先訪問的結(jié)點(diǎn)，其孩子結(jié)點(diǎn)必然也先訪問”，故需運(yùn)用到隊(duì)列。而考慮到層次遍歷對(duì)隊(duì)列操作的需要，只需進(jìn)行隊(duì)列的初始化，入隊(duì)和出隊(duì)以及檢查隊(duì)列是否為空。偽碼算法偽碼算法：voidvoid InitQueue(LinkQueue*Q)/初始化隊(duì)列申請(qǐng)一個(gè)結(jié)點(diǎn)Q-front=Q-rear=(Queueptr)malloc(sizeofsizeof(QNode);if if(!Q-front)exit(1);/存儲(chǔ)分配失敗處理Q-fro

11、nt-next=NULL;/構(gòu)成帶頭結(jié)點(diǎn)里的空鏈隊(duì)列voidvoid EnQueue(LinkQueue*Q,BiTree e)/插入元素為 e 為 Q 的隊(duì)尾元素Queueptr q;q=(Queueptr)malloc(sizeofsizeof(QNode);if 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 if(Q-front=Q-rear)/隊(duì)列為

12、空printf(ERROR!n);exit(1);p=Q-front-next;第 5 頁 共 27 頁q=p-data;Q-front-next=p-next;/刪除該結(jié)點(diǎn)if if(Q-rear=p)Q-rear=Q-front;free(p);returnreturn q;/返回隊(duì)頭元素intint QueueEmpty(LinkQueue*Q)/檢查隊(duì)列是否為空，若為空則返回真值，否則返回0if if(Q-front=Q-rear)returnreturn 1;elseelsereturnreturn 0;3 3、二叉樹的建立與基本操作、二叉樹的建立與基本操作typedef struc

13、ttypedef struct BiTNodeTElemType data;/二叉樹結(jié)點(diǎn)存儲(chǔ)的元素類型structstruct BiTNode*lchild,*rchild;/二叉樹左右孩子指針BiTNode,*BiTree;算法分析：算法分析：二叉樹的基本操作是本程序的核心，考慮到二叉樹的定義就是采用遞歸定義，所以很容易想到對(duì)二叉樹的操作可通過遞歸調(diào)用來實(shí)現(xiàn)。1 1）二叉樹的遍歷）二叉樹的遍歷算法描述：算法描述：二叉樹中常常要求在樹中查找具有某種特征的結(jié)點(diǎn)，或者對(duì)樹中全部結(jié)點(diǎn)逐一進(jìn)行某種處理，這就需要遍歷二叉樹。即要求按某條路徑尋訪樹中的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。

14、回顧二叉樹的遞歸定義可知，二叉樹是由 3 個(gè)基本單元組成：根節(jié)點(diǎn)、左子樹和右子樹。因此，若能依次遍歷這三部分，便是遍歷了整棵二叉樹。如果以L、D、R 分別表示遍歷左子樹、訪問根結(jié)點(diǎn)和遍歷右子樹，則可有DLR、LDR、LRD、DRL、RDL、RLD 這 6 種遍歷二叉樹的方案。若限定先右后左，則只有前三種情況，分別稱之為先（根）序遍歷。中（根）序遍歷和后（根）序遍歷。基于二叉樹的遞歸定義，可得下述遍歷二叉樹的遞歸定義算法。先序遍歷二叉樹的操作定義：若二叉樹為空，則空操作；否則（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹。偽碼算法：偽碼算法：voidvoid PreOderTrav

15、erse(BiTree T)/采用二叉鏈表存儲(chǔ)結(jié)構(gòu)if if(T)putchar(T-data);/最簡(jiǎn)單的訪問結(jié)點(diǎn)法，輸出結(jié)點(diǎn)元素，這里先訪問根結(jié)點(diǎn)PreOderTraverse(T-lchild);第 6 頁 共 27 頁P(yáng)reOderTraverse(T-rchild);中序遍歷二叉樹的操作定義：若二叉樹為空，則空操作；否則（1）中序遍歷左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷右子樹。偽碼算法：偽碼算法：voidvoid InOderTraverse(BiTree T)/采用二叉鏈表存儲(chǔ)結(jié)構(gòu)if if(T)InOderTraverse(T-lchild);/先遍歷左子樹putchar(T

16、-data);/最簡(jiǎn)單的訪問結(jié)點(diǎn)法，輸出結(jié)點(diǎn)元素，這里第二訪問根結(jié)點(diǎn)InOderTraverse(T-rchild);后序遍歷二叉樹的操作定義：若二叉樹為空，則空操作；否則（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點(diǎn)。偽碼算法：偽碼算法：voidvoid PostOderTraverse(BiTree T)/采用二叉鏈表存儲(chǔ)結(jié)構(gòu)if if(T)PostOderTraverse(T-lchild);/先遍歷左子樹PostOderTraverse(T-rchild);/再遍歷右子樹putchar(T-data);/最后訪問根結(jié)點(diǎn)2 2）二叉樹的建立）二叉樹的建立算法描述：算法描述：

17、對(duì)二叉樹“遍歷”基本操作已經(jīng)建立的基礎(chǔ)上，可以在便利過程中對(duì)結(jié)點(diǎn)進(jìn)行各種操作，如：在遍歷過程中生成結(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)的左子樹；第 7 頁 共 27 頁（4）建立該根結(jié)點(diǎn)的右子樹。偽碼算法偽碼算法;BiTree CreateBiTree(BiTree T)/構(gòu)造二叉樹 T，按先序序列輸入二叉樹中結(jié)點(diǎn)的值（一個(gè)字符），空格表示空樹charchar ch;if if(ch=getcha

18、r()=)T=NULLNULL;elseelseif if(ch!=n)if 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)造右子樹returnreturn T;/返回所構(gòu)造二叉樹（子）樹的地址3 3）二叉樹的層次遍歷）二叉樹的層次遍歷算法分析：算法分析：有時(shí)需要一層層訪問二叉樹，比如判斷二叉樹是否為完全二叉樹、找出指定層中含有的葉子/度為 2/度為 1 的結(jié)點(diǎn)等，這就需要另一

19、種遍歷方法層次遍歷。先訪問的結(jié)點(diǎn)，其孩子結(jié)點(diǎn)必然也先訪問，引入隊(duì)列存儲(chǔ)已被訪問的，但其左右孩子尚未訪問的結(jié)點(diǎn)的指針。算法描述算法描述:（1）若結(jié)點(diǎn)不為空，則訪問該結(jié)點(diǎn)，并將其入列；（2）接著從隊(duì)列中取已被訪問的，但其左右孩子尚未被訪問的；（3）訪問該結(jié)點(diǎn)的左孩子，將其入列；（4）訪問該結(jié)點(diǎn)的右孩子，將其入列。偽碼算法：偽碼算法：intint visit(TElemType e)/簡(jiǎn)單的結(jié)點(diǎn)訪問函數(shù)if if(e)putchar(e);/打印該結(jié)點(diǎn)元素returnreturn 1;elseelsereturnreturn 0;voidvoid LevelTraverse(BiTree T)Lin

20、kQueue*Q=(LinkQueue*)malloc(sizeof(sizeof(LinkQueue);BiTree p=(BiTree)malloc(sizeofsizeof(BiTNode);第 8 頁 共 27 頁InitQueue(Q);/初始化隊(duì)列，隊(duì)列的元素為二叉樹的結(jié)點(diǎn)指針if if(T!=NULL)if if(!visit(T-data)/訪問該結(jié)點(diǎn)exit(1);EnQueue(Q,T);/將已被訪問的，但左右孩子沒被訪問的結(jié)點(diǎn)入列whilewhile(!QueueEmpty(Q)/隊(duì)列不為空，則尚有未被訪問其孩子的結(jié)點(diǎn)p=DeQueue(Q);/將該結(jié)點(diǎn)出列，返回其地址i

21、f if(p-lchild!=NULL)if if(!visit(p-lchild-data)/訪問左孩子exit(1);EnQueue(Q,p-lchild);/將其入列if if(p-rchild!=NULL)if if(!visit(p-rchild-data)/訪問右孩子exit(1);EnQueue(Q,p-rchild);/將其入列4 4）求二叉樹的深度）求二叉樹的深度算法描述：算法描述：（1）若結(jié)點(diǎn)不為空，則求其左子樹的深度，并返回其值h1；（2）求其右子樹的深度，也返回其值h2；（3）選擇左右子樹深度的最大值，將其加一（該結(jié)點(diǎn)本身深度）即為該結(jié)點(diǎn)子樹的深度。偽碼算法：偽碼算法：

22、intint BiTreeDepth(BiTree T)/后序遍歷求樹 T 所指二叉樹的深度intint hl=0,hr=0;if if(!T)return 0;elseelsehl=BiTreeDepth(T-lchild);/求左子樹的深度hr=BiTreeDepth(T-rchild);/求右子樹的深度if(hl=hr)return hl+1;else returnelse return hr+1;/子樹深度的最大值再加上本身所在結(jié)點(diǎn)的深度記為子樹的深度5 5）求二叉樹的寬度）求二叉樹的寬度第 9 頁 共 27 頁算法描述：算法描述：（1）定義一個(gè)數(shù)組，來存放每層的結(jié)點(diǎn)數(shù)，max 來存放

23、到這層為止時(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。偽碼算法：偽碼算法：inint BiTreeWidth(BiTree T,int i)int staticint static nM=0;/存放各層結(jié)點(diǎn)數(shù)，M 為最先預(yù)料的最大樹的最大深度int staticint static max=0;/最大寬度if if(T!=NULLNULL)if if(i=1)/若是訪問根結(jié)點(diǎn)ni+;/第一層加 1i+;/到第二層if if(T-lchild)ni+;/若有左

24、孩子則該層加 1if if(T-rchild)ni+;/若有右孩子則該層加 1elseelse/訪問子樹的結(jié)點(diǎn)i+;/向下一層if(if(T-lchild)ni+;if if(T-rchild)ni+;if if(maxlchild,i);/遍歷左子樹BiTreeWidth(T-rchild,i-);/網(wǎng)上退一層后遍歷右子樹returnreturn max;6 6）刪除二叉樹的某個(gè)結(jié)點(diǎn)）刪除二叉樹的某個(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)的

25、指針域賦為空。偽碼算法：偽碼算法：BiTree DeleteBiTree(BiTree t)/釋放該結(jié)點(diǎn)空間的函數(shù)第 10 頁 共 27 頁if if(t!=NULL)t-lchild=DeleteBiTree(t-lchild);/釋放其左子樹的空間t-rchild=DeleteBiTree(t-rchild);/釋放右子樹的空間free(t);/釋放根結(jié)點(diǎn)的空間t=NULLNULL;/將其值賦為空returnreturn t;BiTree DeleteXTree(BiTree t,TElemType x)/先序查找到需刪結(jié)點(diǎn)位置if if(t!=NULLNULL)if if(t-data=

26、x)/判斷是否為指定結(jié)點(diǎn)DeleteBiTree(t);/釋放樹的空間t=NULLNULL;elseelset-lchild=DeleteXTree(t-lchild,x);t-rchild=DeleteXTree(t-rchild,x);returnreturn t;7 7）復(fù)制二叉樹）復(fù)制二叉樹算法描述算法描述:（1）先復(fù)制其左子樹；（2）再復(fù)制其右子樹；（3）生成一個(gè)新結(jié)點(diǎn)，將根復(fù)制。偽碼算法：偽碼算法：BiTree GetTreeNode(TElemType item,BiTree lptr,BiTree rptr)/生成一個(gè)其元素值為 item，左指針為 lpttr，右指針為 rpt

27、r 的結(jié)點(diǎn)BiTree t;t=(BiTree)malloc(sizeofsizeof(BiTNode);t-data=item;t-lchild=lptr;t-rchild=rptr;returnreturn t;BiTree CopyTree(BiTree T)/已知二叉樹的根指針 T，返回它的復(fù)制品的根指針BiTree newlptr,newrptr,newnode;if if(!T)第 11 頁 共 27 頁return NULLreturn NULL;/復(fù)制一顆空樹if if(T-lchild)newlptr=CopyTree(T-lchild);/復(fù)制（遍歷）其左子樹elseels

28、enewlptr=NULL;if if(T-rchild)newrptr=CopyTree(T-rchild);/復(fù)制（遍歷）其右子樹elseelsenewrptr=NULLNULL;newnode=GetTreeNode(T-data,newlptr,newrptr);/生成根結(jié)點(diǎn)returnreturn newnode;4 4、廣義表形式打印二叉樹、廣義表形式打印二叉樹算法分析：算法分析：為了讓打印的二叉樹更形象，更清楚的反映二叉樹各結(jié)點(diǎn)的關(guān)系，采用廣義表形式打印則可以滿足要求。算法描述：算法描述：（1）打印根結(jié)點(diǎn)，若其還有孩子，則輸出“（”；（2）若有左孩子，則打印左子樹；（3）若還有右

29、子樹，則先打印“，”區(qū)分左右孩子，再打印右子樹，并輸出“）”表示輸除完畢。偽碼算法：偽碼算法：voidvoid print(BiTree T)/廣義表形式打印二叉樹if if(T!=NULLNULL)printf(%c,T-data);if if(T-lchild!=NULLNULL|T-rchild!=NULLNULL)/該結(jié)點(diǎn)還有孩子printf();print(T-lchild);/廣義表打印左子樹if if(T-rchild!=NULL)printf(,);print(T-rchild);/廣義表打印右子樹printf();5 5、二叉樹的常見運(yùn)算、二叉樹的常見運(yùn)算1 1）求二叉樹的葉

30、子數(shù)）求二叉樹的葉子數(shù)算法描述：算法描述：（1）若該結(jié)點(diǎn)無孩子，則表示為葉子，計(jì)數(shù)器加一；（2）若該結(jié)點(diǎn)右孩子，求其左子樹的的葉子；（3）再求其右子樹的葉子。偽碼算法：偽碼算法：第 12 頁 共 27 頁intint LeafNum(BiTree T)/統(tǒng)計(jì)葉子數(shù)int staticint static n=0;/定義一個(gè)靜態(tài)局部變量作為計(jì)數(shù)器if if(T!=NULL)if if(T-lchild=NULLNULL&T-rchild=NULLNULL)/結(jié)點(diǎn)無孩子n+;/計(jì)數(shù)器加一LeafNum(T-lchild);/求左子樹的葉子數(shù)LeafNum(T-rchild);/求右子樹的葉子數(shù)re

31、turnreturn n;2 2）求不同的度的結(jié)點(diǎn)數(shù)）求不同的度的結(jié)點(diǎn)數(shù)算法描述：算法描述：（1）定義一個(gè)靜態(tài)局部數(shù)組變量來統(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)行相同操作。偽碼算法：偽碼算法：intint*JudgeCBT(BiTree T)/統(tǒng)計(jì)不同度的結(jié)點(diǎn)數(shù)int staticint static d3=0;/d1作為度為 1 的計(jì)數(shù)器，d2作為度為 2 的計(jì)數(shù)器if if(T!=NULL)if if(T-lchild!=NULLNULL&T-rchild!=NU

32、LLNULL)/左右孩子都有d2+;elseelse/只有一個(gè)孩子if if(T-lchild!=NULLNULL&T-rchild=NULLNULL)d1+;elseelseif(T-lchild=NULLNULL&T-rchild!=NULLNULL)d1+;JudgeCBT(T-lchild);/統(tǒng)計(jì)左子樹JudgeCBT(T-rchild);/統(tǒng)計(jì)右孩子returnreturn d;/返回?cái)?shù)組的指針3 3）求非空子孫結(jié)點(diǎn)數(shù)）求非空子孫結(jié)點(diǎn)數(shù)算法描述：算法描述：（1）定義一個(gè)靜態(tài)局部變量，作為計(jì)數(shù)器；（2）若該節(jié)點(diǎn)的左孩子非空則加一，右孩子非空亦加一；（3）統(tǒng)計(jì)左子樹；統(tǒng)計(jì)右子樹。第 1

33、3 頁 共 27 頁偽碼算法：偽碼算法：intint BiTreeDescendant(BiTree T)/統(tǒng)計(jì)非空子孫結(jié)點(diǎn)數(shù)int staticint static n=0;/初始化計(jì)數(shù)器if if(T!=NULL)if if(T-lchild)n+;if if(T-rchild)n+;BiTreeDescendant(T-lchild);/統(tǒng)計(jì)左子樹BiTreeDescendant(T-rchild);/統(tǒng)計(jì)右子樹returnreturn n;4 4）查找二叉樹的某個(gè)位置的結(jié)點(diǎn)（先序序列）查找二叉樹的某個(gè)位置的結(jié)點(diǎn)（先序序列）算法描述：算法描述：（1）定義一個(gè)靜態(tài)局部變量，用作記錄已查結(jié)點(diǎn)的個(gè)數(shù)；（2）從根節(jié)點(diǎn)開始，如果相查找的位置理由元素，則打印該元素，如果想查的位置超過二叉樹本身的元素?cái)?shù)則返回出錯(cuò)。偽碼算法：偽碼算法：intint PreOderKNode(BiTree T,int