1、word二叉樹(shù)的根本操作摘要：本次課程設(shè)計(jì)通過(guò)對(duì)二叉樹(shù)的一系列操作主要練習(xí)了二叉樹(shù)的建立、四種遍歷方式：先序遍歷、中序遍歷、后序遍歷和層序遍歷以及節(jié)點(diǎn)數(shù)和深度的統(tǒng)計(jì)等算法。增加了對(duì)二叉樹(shù)這一數(shù)據(jù)結(jié)構(gòu)的理解，掌握了使用c語(yǔ)言對(duì)二叉樹(shù)進(jìn)行一些根本的操作。關(guān)鍵字：遞歸、二叉樹(shù)、層序遍歷、子樹(shù)交換一、程序簡(jiǎn)介本程序名為“二叉樹(shù)根本操作的實(shí)現(xiàn)，其主要為練習(xí)二叉樹(shù)的根本操作而開(kāi)發(fā)，其中包含了建立、遍歷、統(tǒng)計(jì)葉子結(jié)點(diǎn)和深度等一系列操作。其中定義二叉鏈表來(lái)表示二叉樹(shù)，用一個(gè)字符類型的數(shù)據(jù)來(lái)表示每一個(gè)節(jié)點(diǎn)中存儲(chǔ)的數(shù)據(jù)。由于沒(méi)有進(jìn)行圖形界面的設(shè)計(jì)，用戶可以通過(guò)程序中的遍歷二叉樹(shù)一功能來(lái)查看操作的二叉樹(shù)。二、功能模

2、塊2.1功能模塊圖2.2功能模塊詳解2.2.1建立二叉樹(shù)輸入要建立的二叉樹(shù)的擴(kuò)展二叉樹(shù)的先序遍歷序列，來(lái)建立二叉樹(shù)，建立成功會(huì)給出提示。2.2.2遍歷二叉樹(shù)執(zhí)行操作之后會(huì)有四個(gè)選項(xiàng)可供選擇：先序遍歷、中序遍歷、后序遍歷、層序遍歷。輸入對(duì)應(yīng)的序號(hào)即可調(diào)動(dòng)相關(guān)函數(shù)輸出相應(yīng)的遍歷序列。2.2.3統(tǒng)計(jì)葉子節(jié)點(diǎn)樹(shù)執(zhí)行之后輸出葉子結(jié)點(diǎn)的個(gè)數(shù)。2.2.4求二叉樹(shù)深度執(zhí)行之后輸出二叉樹(shù)的深度。2.2.5子樹(shù)交換交換成功那么會(huì)給出提示，用戶可通過(guò)遍歷二叉樹(shù)來(lái)觀察子樹(shù)交換之后的二叉樹(shù)。三、數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)3.1二叉鏈表的設(shè)計(jì)1. typedef struct BiNode 

3、0; 2.     char data;  3.     struct BiNode* lchild;  /左孩子4.     struct BiNode* rchild;  /右孩子5. BiTree;  用一個(gè)字符型保存節(jié)點(diǎn)數(shù)據(jù)，分別定義兩個(gè)struct BiNode類型的指針來(lái)指向左孩子和右孩子。在BiTree.h中實(shí)現(xiàn)相關(guān)的功能。

4、3.2隊(duì)列的實(shí)現(xiàn)1. typedef struct   2.     ElemType* data;  3.     int head;/隊(duì)頭指針  4.     int tail;/隊(duì)尾指針  5.  SqQueue;  隊(duì)列主要用于二叉樹(shù)遍歷過(guò)程中的層序遍歷，從根節(jié)點(diǎn)開(kāi)始分別將左右孩子放入隊(duì)列，然后從對(duì)頭開(kāi)始輸出。

5、隊(duì)列的相關(guān)操作封裝在SqQueue.h中，包括入隊(duì)、出隊(duì)、判斷隊(duì)列是否為空等操作。四、全局函數(shù)的設(shè)計(jì)本程序中應(yīng)用了一些全局函數(shù)，本著用到那個(gè)函數(shù)就把哪個(gè)函數(shù)設(shè)為全局函數(shù)的原那么，抽象出了以下全局函數(shù)：4.1全局函數(shù)列表（1） BiTree* createBinaryTree(BiTree* b)本函數(shù)用于建立二叉樹(shù)（2） void Traverse(BiTree* b)本函數(shù)用于遍歷二叉樹(shù)（3） void PreOrderTraverse(BiTree* b)本函數(shù)用于前序遍歷二叉樹(shù)（4） void InOrderTraverse(BiTree* b)本函數(shù)用于中序遍歷二叉樹(shù)（5） void

6、PostOrderTraverse(BiTree* b)本函數(shù)用于后序遍歷二叉樹(shù)（6） void LevelOrderTraverse(BiTree* b)本函數(shù)用于層序遍歷二叉樹(shù)（7） void getLeavesNum(BiTree* b)本函數(shù)用于統(tǒng)計(jì)葉子結(jié)點(diǎn)個(gè)數(shù)（8） int getHeight(BiTree* b)本函數(shù)用于求二叉樹(shù)的深度（9） void swap(BiTree* b)本函數(shù)用子樹(shù)交換（10） void displayMenu()本函數(shù)用于展示菜單4.2全局函數(shù)在具體系統(tǒng)中的分布BiTree.h此文件為二叉樹(shù)的頭文件，包含上述所有全局函數(shù)五、功能實(shí)現(xiàn)二叉樹(shù)的根本操作這

7、個(gè)程序的主要功能就是建立二叉樹(shù)，然后運(yùn)用先序、中序等遍歷方法遍歷二叉樹(shù)，然后還有統(tǒng)計(jì)二叉樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)、求二叉樹(shù)的深度以及進(jìn)行子樹(shù)的交換。5.1二叉樹(shù)的根本操作流程圖如下菜單界面如下：5.2二叉樹(shù)的根本操作的代碼如下二叉樹(shù)的建立1. /按照前序輸入二叉樹(shù)結(jié)點(diǎn)的值，“#表示空  2. BiTree* createBinaryTree(BiTree* b)   3.     char ch;/定義變量用于儲(chǔ)存輸入的字符  4.   

8、60; scanf("%c", &ch);  5.     if (ch = '#')   6.         b = NULL;  7.       8.     else 

9、0; 9.         if (b = (BiTree*)malloc(sizeof(BiTree) != NULL) /如果內(nèi)存分配成功就執(zhí)行下面操作  10.             /生成根節(jié)點(diǎn)  11.       &

10、#160;     b->data = ch;  12.             /構(gòu)造左子樹(shù)  13.             b->lchild=createBinaryTree(b->lchild);  1

11、4.             /構(gòu)造右子樹(shù)  15.             b->rchild=createBinaryTree(b->rchild);  16.           17.  &

12、#160;    18.     return b;  19.   5.2.2二叉樹(shù)的遍歷如下圖選擇遍歷后有三種方案可供選擇：（1） 前序遍歷1. void PreOrderTraverse(BiTree* b)   2.     if (b = NULL)   3.     &

13、#160;   return;  4.       5.     /首先打印結(jié)點(diǎn)數(shù)據(jù)  6.     printf("%c ", b->data);  7.     /再先序遍歷左子樹(shù)  8.     PreOrderTra

14、verse(b->lchild);  9.     /最后先序遍歷右子樹(shù)  10.     PreOrderTraverse(b->rchild);  11.   （2） 中序遍歷1. /中序遍歷  2. void InOrderTraverse(BiTree* b)   3.     if (b 

15、;= NULL)   4.         return;  5.       6.     /首先中序遍歷左子樹(shù)  7.     InOrderTraverse(b->lchild);  8.     /再打印結(jié)點(diǎn)數(shù)據(jù) &

16、#160;9.     printf("%c ", b->data);  10.     /最后中序遍歷右子樹(shù)  11.     InOrderTraverse(b->rchild);  12.   （3） 后序遍歷1. /后序遍歷  2. void PostOrderTraverse(BiTree* b)

17、   3.     if (b = NULL)   4.         return;  5.       6.     /首先后序遍歷左子樹(shù)  7.     PostOrderTraverse(b->

18、lchild);  8.     /再后序遍歷右子樹(shù)  9.     PostOrderTraverse(b->rchild);  10.     /最后打印結(jié)點(diǎn)數(shù)據(jù)  11.     printf("%c ", b->data);  12.   （4） 層序遍歷1.

19、 /層序遍歷  2. void LevelOrderTraverse(BiTree* b)   3.     SqQueue* s = initSqQueue();  4.     BiTree* temp;  5.     if (b)   6.    &#

20、160;    append(s, *b);  7.         while (!isEmpty(s)   8.             temp=pop(s);  9.         

21、;    printf("%c ", temp->data);  10.             if (temp->lchild)   11.                &

22、#160;append(s, *temp->lchild);  12.               13.             if (temp->rchild)   14.       

23、60;         append(s, *temp->rchild);  15.               16.           17.       18. &#

24、160; 統(tǒng)計(jì)葉子結(jié)點(diǎn)個(gè)數(shù)1. /統(tǒng)計(jì)葉子節(jié)點(diǎn)  2. int count;/全局變量，如果出現(xiàn)葉子結(jié)點(diǎn)就加一  3. void getLeavesNum(BiTree* b)   4.     if (b)   5.         if (!b->lchild && !b-

25、>rchild)   6.             count+;  7.           8.         getLeavesNum(b->lchild);  9.    

26、60;    getLeavesNum(b->rchild);  10.       11.   5.3.4求二叉樹(shù)的深度1. /求二叉樹(shù)的深度  2. int getHeight(BiTree* b)   3.     int leftHeight, rightHeight;  4.  &#

27、160;  if (!b)   5.         return 0;  6.       7.     leftHeight = getHeight(b->lchild);  8.     rightHeight = g

28、etHeight(b->rchild);  9.     return leftHeight > rightHeight  leftHeight + 1 : rightHeight + 1;  10.   子樹(shù)交換1. /子樹(shù)交換  2. BiTree* temp;/臨時(shí)變量，用于交換  3. void swap(BiT