皮匠网—开放、共享、免费的咨询方案报告文库
咨询人士学习成长与交流平台
二叉树
一、需求分析
1、设计任务
建立一棵二叉树，数据以字符串形式从键盘输入。在此二叉树上
完成：
（1）前序、中序、后序遍历 （2）求出叶子数 （3）求树高
（4）左右子树交换，输出交换后的前序、中序遍历序列 选做：
（1）给出非递归的后序遍历
（2）扩充为中序线索树，写出非递归的中序遍历
（3）在两个数组中分别有前序和中序遍历序列，试建立该二叉树 2、输入的形式和输出值的范围
二叉树的建立：本程序的二叉树的建立函数时根据二叉树的前序排列生成的，但是其中子树为空地方用特殊符号“＊”代替。
二叉树的输出值的范围：二叉树的输出是把二叉树各节点的值按遍历顺序输出的，本程序各节点的数据类型为字符型(可以在编译预处理修改)。
3、输出的形式
二叉树的输出是根据二叉树的遍历顺序输出的（包括前序、中序和后序三种）把各节点地值输出。 4、程序所能达到的功能
本程序能够实现对二叉树的一些简单操作，例如二叉树的各种遍历(包括二叉树的前序、中序和后序的递归遍历以及非递归遍历)、求二叉树的叶子数和高以及二叉树的左右子树交换。 5、测试数据
本资料由皮匠网收录，更多免费资料下载请点击：
https://www.3mbang.com/
皮匠网—开放、共享、免费的咨询方案报告文库
咨询人士学习成长与交流平台
(1)当为二叉树一时：
(2)当为二叉树二时：
本资料由皮匠网收录，更多免费资料下载请点击：
https://www.3mbang.com/
皮匠网—开放、共享、免费的咨询方案报告文库
咨询人士学习成长与交流平台
二、概要设计
1、树结点结构体
typedef char DataType;
struct TreeNode {
DataType data;
TreeNode *lchild,*rchild;};
2、棧结点结构体 struct StackNode
{
TreeNode* T_N; int Flag;
};
3、主程序流程
主程序开始；
调用CreateBiTree(TreeNode *&Tree)函数建立二叉树；
依次调用前序、中序和后序递归及非递归遍历二叉树； 计算二叉树的树叶和树高； 交换二叉树的左右子树；
依次用前序、中序和后序的递归和非递归方法遍历二叉树； 主程序结束； 三、详细设计
本资料由皮匠网收录，更多免费资料下载请点击：
https://www.3mbang.com/
数据结构实习报告---二叉树[12页].doc
