数据结构课程设计-二叉树的基本操作.doc

二叉树的基本操作
摘要：
本次课程设计通过对二叉树的一系列操作主要练习了二叉树的建立、四种遍历方式：先序遍历、中序遍历、后序遍历和层序遍历以及节点数和深度的统计等算法。增加了对二叉树这一数据结构的理解，掌握了使用c语言对二叉树进行一些基本的操作。
关键字：递归、二叉树、层序遍历、子树交换
一、程序简介
本程序名为“二叉树基本操作的实现”，其主要为练习二叉树的基本操作而开发，其中包含了建立、遍历、统计叶子结点和深度等一系列操作。其中定义二叉链表来表示二叉树，用一个字符类型的数据来表示每一个节点中存储的数据。由于没有进行图形界面的设计，用户可以通过程序中的遍历二叉树一功能来查看操作的二叉树。
二、功能模块
2.1功能模块图

2.2功能模块详解
2.2.1建立二叉树
输入要建立的二叉树的扩展二叉树的先序遍历序列，来建立二叉树，建立成功会给出提示。
2.2.2遍历二叉树
执行操作之后会有四个选项可供选择：先序遍历、中序遍历、后序遍历、层序遍历。输入对应的序号即可调动相关函数输出相应的遍历序列。
2.2.3统计叶子节点树
执行之后输出叶子结点的个数。
2.2.4求二叉树深度
执行之后输出二叉树的深度。
2.2.5子树交换
交换成功则会给出提示，用户可通过遍历二叉树来观察子树交换之后的二叉树。
三、数据结构和算法设计
3.1二叉链表的设计
1. typedef struct BiNode {  
2.     char data;  
3.     struct BiNode* lchild;  //左孩子
4.     struct BiNode* rchild;  //右孩子
5. }BiTree;  
用一个字符型保存节点数据，分别定义两个struct BiNode类型的指针来指向左孩子和右孩子。在BiTree.h中实现相关的功能。
3.2队列的实现
1. typedef struct {  
2.     ElemType* data;  
3.     int head;//队头指针  
4.     int tail;//队尾指针  
5. } SqQueue;  
队列主要用于二叉树遍历过程中的层序遍历，从根节点开始分别将左右孩子放入队列，然后从对头开始输出。队列的相关操作封装在SqQueue.h中，包括入队、出队、判断队列是否为空等操作。
四、全局函数的设计
本程序中应用了一些全局函数，本着用到那个函数就把哪个函数设为全局函数的原则，抽象出了以下全局函数：
4.1全局函数列表
（1） BiTree* createBinaryTree(BiTree* b)
本函数用于建立二叉树
（2） void Traverse(BiTree* b)
本函数用于遍历二叉树
（3） void PreOrderTraverse(BiTree* b)
本函数用于前序遍历二叉树
（4） void InOrderTraverse(BiTree* b)
本函数用于中序遍历二叉树
（5） void PostOrderTraverse(BiTree* b)
本函数用于后序遍历二叉树
（6） void LevelOrderTraverse(BiTree* b)
本函数用于层序遍历二叉树
（7） void getLeavesNum(BiTree* b)
本函数用于统计叶子结点个数
（8） int getHeight(BiTree* b)
本函数用于求二叉树的深度
（9） void swap(BiTree* b)
本函数用子树交换
（10） void displayMenu()
本函数用于展示菜单
4.2全局函数在具体系统中的分布
BiTree.h
此文件为二叉树的头文件，包含上述所有全局函数
五、功能实现
二叉树的基本操作这个程序的主要功能就是建立二叉树，然后运用先序、中序等遍历方法遍历二叉树，然后还有统计二叉树的叶子结点个数、求二叉树的深度以及进行子树的交换。
5.1二叉树的基本操作流程图如下

菜单界面如下：

5.2二叉树的基本操作的代码如下
5.2.1二叉树的建立
1. //按照前序输入二叉树结点的值，“#”表示空  
2. BiTree* createBinaryTree(BiTree* b) {  
3.     char ch;//定义变量用于储存输入的字符  
4.     scanf("%c", &ch);  
5.     if (ch == '#') {  
6.         b = NULL;  
7.     }  
8.     else {  
9.         if ((b = (BiTree*)malloc(sizeof(BiTree))) != NULL) {//如果内存分配成功就执行下面操作  
10.             //生成根节点  
11.             b->data = ch;  
12.             //构造左子树  
13.             b->lchild=createBinaryTree(b->lchild);  
14.             //构造右子树  
15.             b->rchild=createBinaryTree(b->rchild);  
16.         }  
17.     }  
18.     return b;  
19. }  

5.2.2二叉树的遍历
如图所示选择遍历后有三种方案可供选择：

（1） 前序遍历
1. void PreOrderTraverse(BiTree* b) {  
2.     if (b == NULL) {  
3.         return;  
4.     }  
5.     //首先打印结点数据  
6.     printf("%c ", b->data);  
7.     //再先序遍历左子树  
8.     PreOrderTraverse(b->lchild);  
9.     //最后先序遍历右子树  
10.     PreOrderTraverse(b->rchild);  
11. }  

（2） 中序遍历
1. //中序遍历  
2. void InOrderTraverse(BiTree* b) {  
3.     if (b == NULL) {  
4.         return;  
5.     }  
6.     //首先中序遍历左子树  
7.     InOrderTraverse(b->lchild);  
8.     //再打印结点数据  
9.     printf("%c ", b->data);  
10.     //最后中序遍历右子树  
11.     InOrderTraverse(b->rchild);  
12. }  

（3） 后序遍历
1. //后序遍历  
2. void PostOrderTraverse(BiTree* b) {  
3.     if (b == NULL) {  
4.         return;  
5.     }  
6.     //首先后序遍历左子树  
7.     PostOrderTraverse(b->lchild);  
8.     //再后序遍历右子树  
9.     PostOrderTraverse(b->rchild);  
10.     //最后打印结点数据  
11.     printf("%c ", b->data);  
12. }  

（4） 层序遍历
1. //层序遍历  
2. void LevelOrderTraverse(BiTree* b) {  
3.     SqQueue* s = initSqQueue();  
4.     BiTree* temp;  
5.     if (b) {  
6.         append(s, *b);  
7.         while (!isEmpty(s)) {  
8.             temp=pop(s);  
9.             printf("%c ", temp->data);  
10.             if (temp->lchild) {  
11.                 append(s, *temp->lchild);  
12.             }  
13.             if (temp->rchild) {  
14.                 append(s, *temp->rchild);  
15.             }  
16.         }  
17.     }  
18. }  

5.2.3统计叶子结点个数
1. //统计叶子节点  
2. int count;//全局变量，如果出现叶子结点就加一  
3. void getLeavesNum(BiTree* b) {  
4.     if (b) {  
5.         if (!b->lchild && !b->rchild) {  
6.             count++;  
7.         }  
8.         getLeavesNum(b->lchild);  
9.         getLeavesNum(b->rchild);  
10.     }  
11. }  

5.3.4求二叉树的深度
1. //求二叉树的深度  
2. int getHeight(BiTree* b) {  
3.     int leftHeight, rightHeight;  
4.     if (!b) {  
5.         return 0;  
6.     }  
7.     leftHeight = getHeight(b->lchild);  
8.     rightHeight = getHeight(b->rchild);  
9.     return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;  
10. }  

5.2.5子树交换
1. //子树交换  
2. BiTree* temp;//临时变量，用于交换  
3. void swap(BiTree* b) {  
4.     if (b == NULL) {  
5.         return;  
6.     }  
7.     else {  
8.         temp = b->lchild;  
9.         b->lchild = b->rchild;  
10.         b->rchild = temp;  
11.         swap(b->lchild);  
12.         swap(b->rchild);  
13.     }  
14. }  
部分运行结果截图如下：
建立二叉树：

统计叶子节点个数：

求二叉树的深度：

六、参考文献
1. Stephen Prata.《C Primer Plus (第6版) 中文版》. 人民邮电出版社. 2016年
2. CSDN博客：
3. 谭浩强.《C程序设计（第四版）》．清华大学出版社.
4. 严蔚敏《数据结构》c语言版 第二版 人民邮电出版社

9