数据结构课设二叉树的遍历

《数据结构课设二叉树的遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.数据结构课程设计说明书题目：二叉树的遍历学生姓名：学号：院（系）：专业：word范文.指导教师：年月日word范文.目录1需求分析12概要设计12.1功能设计12.2算法流程图23详细设计23.1创建二叉树23.2二叉树的递归遍历算法33.3二叉树的层次遍历算法33.4二叉树的非递归遍历算法34测试数据与分析35算法分析96总结9参考文献10附录11word范文.1需求分析数据结构是信息类专业最重要的专业基础课程，掌握好数据结构的知识将直接关系到后续专业课程的学习。数据结构研究四个方面的问题：（1）数据的逻辑结构，即数据之间的逻辑关系；（2）

2、数据的物理结构，即数据在计算机内的存储方式；（3）对数据的加工，即基于某种存储方式的操作算法；（4）算法的分析；即评价算法的优劣。本实验是用链式存储结构来存储二叉树并进行一系列的算法，且结点内容的数据类型为字符型。根据题目知，程序主要是根据给定二叉树的先序遍历结果，构造出二叉树并输出按中，后序遍历的结果，以及求二叉树的叶子个数等。其中二叉树的结点用字符表示。（1）创建二叉树：按先序次序输入，构造二叉链表表示的二叉树。（2）设计算法：先序遍历,中序遍历,后序遍历。（3）编写程序：设计main()函数调用以上步骤实现相关功能。本程序用Microso

3、ftVisualStudio2008编写，可以实现各种二叉树的遍历。包括先序遍历、中序遍历、后序遍历的递归算法，先序遍历、中序遍历、后序遍历的非递归算法以及能查找任一结点在某种遍历序列中的前驱和后继。2概要设计2.1功能设计（1）typedefstructBTNode—定义二叉树word范文.定义一个用链式存储结构存储的二叉树，其中包括左孩子和右孩子以及数据元素的内容。和单链表类似，一个二叉链表由头指针唯一确定，若二叉树为空，则头指针指向空。并且结点内容的数据类型为字符型。（2）CreateBiTree(BiTree&T)—构建二叉树此函数的功

4、能是构建二叉树。从键盘上按先序次序输入字符构造二叉链表表示的二叉树T，其中用星号表示空树。（3）NRPreOrder(BiTreebt)—先序遍历（非递归）此函数的功能是用非递归的方法实现二叉树的先序遍历算法。调用此函数可以获得二叉树的非递归的先序遍历的结果。（4）NRInOrder(BiTreebt)—中序遍历（非递归）此函数的功能是用非递归的方法实现二叉树的中序遍历算法。调用此函数可以获得二叉树的非递归的中序遍历的结果。（5）NRPostOrder(BiTreebt)—后序遍历（非递归）此函数的功能是用非递归的方法实现二叉树的后序遍历算法。

5、调用此函数可以获得二叉树的非递归的后序遍历的结果。其中bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。可采用标记法，结点入栈时，配一个标志tag一同入栈1：遍历左子树的现场保护，2：遍历右子树前的现场保护。首先将bt和tag(为1)入栈，遍历左子树；返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。（6）PreOrderTraverse(BiTreeT)—先序遍历（递归）函数功能是用递归的方法对二叉树进行先序遍历，调用此函数可以获得二叉树的递归的先序遍历的结果。（7）InOrderT

6、raverse(BiTreeT)—中序遍历（递归）函数功能是用递归的方法对二叉树进行中序遍历，调用此函数可以获得二叉树的递归的中序遍历的结果。word范文.（8）PostOrderTraverse(BiTreeT)—后序遍历（递归）函数功能是用递归的方法对二叉树进行后序遍历，调用此函数可以获得二叉树的递归的后序遍历的结果。（9）main()主函数用while()与switch(select)语句对二叉树的操作的算法进行了设计。可以实现以上函数的功能，并能退出程序。2.2算法流程图算法流程图如图1所示。图2-1算法流程图3详细设计3.1创建二叉树

7、(1)定义二叉树结点值的类型为字符型。word范文.(2)结点个数不超过10个。(3)按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树。3.2二叉树的递归遍历算法DLR(1)访问根结点。(2)先序遍历根结点的左子数。(3)先序遍历根结点的右子数。LDR(1)先序遍历根结点的左子数。(2)访问根结点。(3)先序遍历根结点的右子数。LRD(1)先序遍历根结点的左子数。(2)先序遍历根结点的右子数。(3)访问根结点。3.3二叉树的层次遍历算法(1)访问该元素所指结点。(2)若该元素所指结点的左右孩子结点非空，则该元素所指结点的左孩子指针和右孩

8、子指针顺序入队。3.4二叉树的非递归遍历算法（1）非递归的先序遍历算法a.访问结点的数据域。word范文.b.指针指向p的左孩子结点。c.从栈中弹出栈