二叉树的基本操作实现及其应用

《二叉树的基本操作实现及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、目录一、实验目的1二、实验内容1三、实验步骤1㈠、数据结构与核心算法的设计描述1㈡、函数调用及主函数设计2㈢程序调试及运行结果分析3㈣实验总结3四、主要算法流程图及程序清单31、主要算法流程图：32、程序清单411实验三二叉树的基本操作实现及其应用一、实验目的1．熟悉二叉树结点的结构和对二叉树的基本操作。2．掌握对二叉树每一种操作的具体实现。3．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。4.会用二叉树解决简单的实际问题。二、实验内容题目一设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操

2、作的具体的函数定义和主函数。1按先序次序建立一个二叉树，2按（A:先序B:中序C:后序）遍历输出二叉树的所有结点以上比做，以下选做3求二叉树中所有结点数4求二叉树的深度三、实验步骤㈠、数据结构与核心算法的设计描述1)二叉树结构类型定义：typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;2）队列节点定义：typedefstructQNode{BiTreebt;structQNode*next;11}QNode,*QueuePtr;3）队列类型定义

3、：structLinkQueue队列类型定义{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针};4）初始化二叉树，即把二叉树置空：voidBiTreeInit(BiTree&T)5）按先序建立一个二叉树：StatusCreateBiTree(BiTree&T)按先序次序输入二叉树中结点值（一个字符），空格字符表示空树。构造二叉链表表示的二叉树T。6）StatusPreOrderTraverse(BiTreeT)//先序遍历二叉树7）StatusInOrderTraverse(BiTreeT)//中序遍历二叉树8）

4、StatusPostOrderTraverse(BiTreeT)//后序遍历二叉树9）voidout(BiTreeT)//从左到右，从上到下遍历二叉树10）voidnodesum(BiTree&T)//二叉树节点总数11）intDepth(BiTreeT)//返回二叉树的深度12）voidInitQueue(LinkQueue&Q)//构造一个空队列Q13）EnQueue(LinkQueue&Q,BiTree&e)//进队14）DeQueue(LinkQueue&Q,BiTree&e)//出队15）StatusemptyQueue(LinkQu

5、eue&Q)//判断队列是否空㈡、函数调用及主函数设计11主函数先序建立二叉树先序遍历二叉树中序遍历二叉树后序遍历二叉树上下左右依次遍历二叉树总结点数其他键退出二叉树深度㈢程序调试及运行结果分析1.先序建立二叉树时，应用getchar（）函数，从流中读入字符；2.上下左右依次遍历二叉树时，判断结束的条件是栈是否空；3.队列节点的数据域应定义成二叉树型的；4.求节点总数时，计数n应定义成全局变量。5.求深度的k也应是全局变量。㈣实验总结以前只是学一些零碎的东西，通过做实验，让我们把这些零碎的东西拼接成一个小小的程序。让我们在做实验时对整体的把握得

6、以提高。11这次实验既培养了自己的动手能力，又加深了对知识的认识，同时使自己有了解决问题的思路和方法。在这次实验的过程中，我知道了一些如何查找错误的方法，掌握了一些关于如何调试来解决自己的代码编译错的技巧。自己在以后的学习过程中加强锻炼，多写写，多练练，把书本上的知识应用到实际问题中去，达到所学以用。通过这次实验，我对二叉树更加了解，还有跟队列的结合，是我对知识有更深的应用。四、主要算法流程图及程序清单结束队头元素出队T->lchild是否空T->lchild入队输出T->lchild->dataT->rchild是否空是T->rchild入队

7、输出T->lchild->data是开始构造空队列，T入队，输出T->data栈是否空是1、主要算法流程图：否否否11从上到下，从左到右遍历二叉树图2、程序清单#include#include#include#defineStatusint#defineOVERFLOW1#defineOK1#defineERROR0intn=0,k;typedefstructBiTNode//二叉树节点定义{chardata;structBiTNode*lchild,*rchild;}BiTNode

8、,*BiTree;typedefstructQNode//队列节点定义{BiTreebt;structQNode*next;}QNode,*Queue