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

二叉树的基本操作摘要：本次课程设计通过对二叉树的一系列操作主要练习了二叉树的建立、四种遍历方式：先序遍历、中序遍历、后序遍历和层序遍历以及节点数和深度的统计等算法。增加了对二叉树这一数据结构的理解，掌握了使用c语言对二叉树进行一些基本的操作。关键字：递归、二叉树、层序遍历、子树交换一、程序简介本程序名为“二叉树基本操作的实现”，其主要为练习二叉树的基本操作而开发，其中包含了建立、遍历、统计叶子结点和深度等一系列操作。其中定义二叉链表来表示二叉树，用一个字符类型的数据来表示每一个节点中存储的数据。由于没有进行图形界面的设计，用户可以通过程序中的遍历二叉树一功能来查看操作的二叉树。二、功能模块2.1功能模块图2.2功能模块详解2.2.1建立二叉树输入要建立的二叉树的扩展二叉树的先序遍历序列，来建立二叉树，建立成功会给出提示。2.2.2遍历二叉树执行操作之后会有四个选项可供选择：先序遍历、中序遍历、后序遍历、层序遍历。输入对应的序号即可调动相关函数输出相应的遍历序列。2.2.3统计叶子节点树执行之后输出叶子结点的个数。2.2.4求二叉树深度执行之后输出二叉树的深度。2.2.5子树交换交换成功则会给出提示，用户可通过遍历二叉树来观察子树交换之后的二叉树。三、数据结构和算法设计3.1二叉链表的设计1. typedefstructBiNode2. chardata;3. structBiNode*lchild;/左孩子4. structBiNode*rchild;/右孩子5. BiTree;用一个字符型保存节点数据，分别定义两个struct BiNode类型的指针来指向左孩子和右孩子。在BiTree.h中实现相关的功能。3.2队列的实现1. typedefstruct2. ElemType*data;3. inthead;/队头指针4. inttail;/队尾指针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. charch;/定义变量用于储存输入的字符4. scanf(%c,&ch);5. if(ch=#)6. b=NULL;7. 8. else9. 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. returnb;19. 5.2.2二叉树的遍历如图所示选择遍历后有三种方案可供选择：（1） 前序遍历1. voidPreOrderTraverse(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. voidInOrderTraverse(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. voidPostOrderTraverse(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. voidLevelOrderTraverse(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. intcount;/全局变量，如果出现叶子结点就加一3. voidgetLeavesNum(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. intgetHeight(BiTree*b)3. intleftHeight,rightHeight;4. if(!b)5. return0;6. 7. leftHeight=getHeight(b-lchild);8. rightHeight=getHeight(b-rchild);9. returnleftHeightrightHeight?leftHeight+1:rightHeight+1;10. 5.2.5子树交换1. /子树交换2. BiTree*temp;/临时变量，用于交换3. voidswap(BiTree*b)4. if(b=NULL)5. return;6. 7. else8. 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