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

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

2、块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 

3、0; 2.     char data;  3.     struct BiNode* lchild;  /左孩子4.     struct BiNode* rchild;  /右孩子5. BiTree;  用一个字符型保存节点数据，分别定义两个struct BiNode类型的指针来指向左孩子和右孩子。在BiTree.h中实现相关的功能。

4、3.2队列的实现1. typedef struct   2.     ElemType* data;  3.     int head;/队头指针  4.     int tail;/队尾指针  5.  SqQueue;  队列主要用于二叉树遍历过程中的层序遍历，从根节点开始分别将左右孩子放入队列，然后从对头开始输出。

5、队列的相关操作封装在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

6、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此文件为二叉树的头文件，包含上述所有全局函数五、功能实现二叉树的根本操作这

7、个程序的主要功能就是建立二叉树，然后运用先序、中序等遍历方法遍历二叉树，然后还有统计二叉树的叶子结点个数、求二叉树的深度以及进行子树的交换。5.1二叉树的根本操作流程图如下菜单界面如下：5.2二叉树的根本操作的代码如下二叉树的建立1. /按照前序输入二叉树结点的值，“#表示空  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) /如果内存分配成功就执行下面操作  10.             /生成根节点  11.       &

10、#160;     b->data = ch;  12.             /构造左子树  13.             b->lchild=createBinaryTree(b->lchild);  1

11、4.             /构造右子树  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.     /首先打印结点数据  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.     /再打印结点数据 &

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.     /最后打印结点数据  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; 统计叶子结点个数1. /统计叶子节点  2. int count;/全局变量，如果出现叶子结点就加一  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