数据结构课程设计之二叉树的遍历.doc

《数据结构》课程设计报告 题 目 学生姓名 学 号 专业班级 指导老师 设计日期 指导老师评阅意见： 评阅成绩： 签名： 目录 问题定义······································3 可行性分析···································3-4 调试界面·····································4-7 错误分析······································7 总结·········································7-8 附录········································8-14 问题定义 1.1 课题： 建立二叉树，层序、先序、中序、后序遍历（ 用递归或非递归的方法）以及中序线索化。 1.2意义： 通过以前的学习以及查看相关资料，按照题目要求编写程序，进一步加强对编程的训练，使得自己掌握一些将书本知识转化为实际应用当中去，在整个程序中，主要应用的是链表，但也运用了栈。通过两种方法解决现有问题。 1.3要求： 要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数； 实现二叉树的中序线索化。 可行性分析 2.1 创建二叉树链表的结点存储结构及数据的输入函数 因为每个结点所存储的数据类型为字符串，却无法使用字符串和String等数据类型，所以使用单链表作为结点所存储的数据类型。以#表示空结点。 利用先序遍历创建链表 2.1.1用单链表s记录输入的数据 2.1.2利用非递归调用分别生成根节点的左子树和右子树。 2.1.3返回菜单重新选择。 基本程序如下： void CreatBiTree_q(BiTree T)/ { ······ if(ch==#) T=NULL; else { T=(BiTree)malloc(sizeof(BiTNode)); if(!T) exit(0); T-data=ch; T-LTag=Link; T-RTag=Link; CreatBiTree_q(T-lchild); CreatBiTree_q(T-rchild); } } 2.2先序遍历、中序遍历、后序遍历二叉链表。 A 、先序遍历：访问根节点，左子树，右子树的顺序。 B、中序遍历：访问左子树，根节点，右子树的顺序。 C、后序遍历：访问左子树，右子树，根节点的顺序。 D、层次遍历：从根结点开始，按从左至右的顺序依次访问。 E、中序线索化：将二叉树线索化，再进行中序遍历输出。 2.3主函数 a、调用生成二叉树的函数，从键盘输入二叉树的各个结点 b、分别调用先序遍历、中序遍历、后序遍历二叉树的函数，输出所有结点 显示的菜单为： *********************************************** 请选择遍历算法 1.按先序输入二叉树序列以#表示空节点 2.先序遍历二叉树递非归算法 3.中序遍历二叉树非递归算法 4.后序遍历二叉树非递归算法 5.层次遍历二叉树非递归算法 6.中序线索遍历二叉树算法 0.按0退出endl 请输入序号（0，1,2,3,4,5,6）： 三、调试界面： 3.1调试所用二叉树：