1、 目 录 1 问题描述 . 1 2 需求分析 . 1 3 概要设计 . 1 31 模块划分.错误错误! 未定义书签。未定义书签。 4 详细设计 6 41 主要模块流程图7 42 数据类型的定义8 43 主要模块的算法描述8 5 测试分析 . 14 6 课程设计总结 17 参考文献 . 18 附录（源程序清单） 19 1 1 问题描述 建立一棵二叉树；再以广义表表示法输出这棵二叉树；然后对该树进行先序、中 序、后序遍历及层次遍历。 要求： （1）采用二叉链表存储二叉树； （2）先序、中序、后序遍历设计非递归算法。 2 需求分析 二叉树一种数据结构，用于保存和处理树状的数据，比如家谱。他的应用极为
2、广 泛，因为根据数据结构的理论，任何复杂的树够可以转换为二叉中并进行处理，二 叉树在排序、查找、大规模数据索引方面有很多很多应用。而且二叉树排序是简单 算法排序中速度最快的。 在二叉树的一些应用中，常常要求在树中查找具有某种特征的节点，或者对树 中全部节点逐一进行某种处理。这就提出了遍历二叉树。根据遍历的方向的选择， 就有了前序遍历，中序遍历和后序遍历以及层次遍历二叉树。因此掌握二叉树的各 种遍历二叉树算法非常重要，而且高效的遍历算法能够节省很多成本。 3 概要设计 31 模块划分 本程序包括七个模块： （1）主程序模块 void main() 初始化； 以广义表表示法输出； 建立二叉树； 非
3、递归先序遍历二叉树并输出； 非递归中序遍历二叉树并输出； 非递归后序遍历二叉树并输出； 2 层次遍历二叉树并输出； （2）以广义表表示法输出实现对二叉树的输出 （3）二叉树建立模块建立一个二叉树并 对二叉树进行初始化 （4）非递归先序遍历模块实现对二叉树的递归先序遍历并输出 （5）非递归中序遍历模块实现对二叉树的递归中序遍历并输出 （6）非递归后序遍历模块实现对二叉树的递归后序遍历并输出 （7）层次遍历模块实现对二叉树的层次遍历并输出 4 详细设计 41 主要模块流程图 主流程图 开始 广义表表示法输出 printfbitree(t) 创建一棵二叉树 t=creattree（） 非递归前序遍历
4、 nrpreorder(t) 非递归中序遍历 nrinorder（t） 非递归后序遍历 nrreorder（t） 层次遍历 levelorder（t） 结束 3 建立一棵二叉树 以广义表表示法输出一棵二叉树 charp;BiTreeT; p=# return(T); T=NULL; T=(BiTNode*)malloc(sizeof(BiTN bt!=NULL printf(“%c“,bt-data); bt-lchild!=N printf(“(“); bt-rchild!=N printfBTree(bt-rchild); printf(“,“); 4 非递归先序遍历 SqStackS; p !StackEmpty( p=(BiTNode*)malloc(sizeof(BiTNode) p-rchild p-lchild Push( Push( SqStackS; p|
