《数据结构》课程设计报告 题 目 学生姓名 学 号 专业班级 指导老师 设计日期 指导老师评阅意见： 评阅成绩： 签名： 目录 问题定义······································3 可行性分析···································3 -4 调试界面·····································4 -7 错误分析······································7 总结·········································7 -8 附录········································8 -1 4 一、 问题定义 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、后序遍历：访问左子树，右子...
