數(shù)據(jù)結(jié)構(gòu)課程設(shè)計二叉樹的基本操作

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

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

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

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

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

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

7、個程序的主要功能就是建立二叉樹，然后運用先序、中序等遍歷方法遍歷二叉樹，然后還有統(tǒng)計二叉樹的葉子結(jié)點個數(shù)、求二叉樹的深度以及進(jìn)行子樹的交換。5.1二叉樹的根本操作流程圖如下菜單界面如下：5.2二叉樹的根本操作的代碼如下二叉樹的建立1. /按照前序輸入二叉樹結(jié)點的值，“#表示空  2. BiTree* createBinaryTree(BiTree* b)   3.     char 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é)點  11.       &

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

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

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

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

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

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

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

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

18、lchild);  8.     /再后序遍歷右子樹  9.     PostOrderTraverse(b->rchild);  10.     /最后打印結(jié)點數(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)計葉子結(jié)點個數(shù)1. /統(tǒng)計葉子節(jié)點  2. int count;/全局變量，如果出現(xiàn)葉子結(jié)點就加一  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求二叉樹的深度1. /求二叉樹的深度  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.   子樹交換1. /子樹交換  2. BiTree* temp;/臨時變量，用于交換  3. void swap(BiT