二叉树课程设计.pdfVIP

目录

1问题描述1

2需求分析1

3概要设计1

3．1模块划分……….错误！

未定义书签。

4详细设计………6

4．1主要模块流程图………………7

4．2数据类型的定义………………8

4．3主要模块的算法描述…………8

5测试分析14

6课程设计总结.17

参考文献18

附录（源程序清单）19

1问题描述

建立一棵二叉树；再以广义表表示法输出这棵二叉树；然后对该树进行先序、中

序、后序遍历及层次遍历。

要求：

（1）采用二叉链表存储二叉树；

（2）先序、中序、后序遍历设计非递归算法。

2需求分析

二叉树一种数据结构，用于保存和处理树状的数据，比如家谱。他的应用极为广

泛，因为根据数据结构的理论，任何复杂的树够可以转换为二叉中并进行处理，二

叉树在排序、查找、大规模数据索引方面有很多很多应用。而且二叉树排序是简单

算法排序中速度最快的。

在二叉树的一些应用中，常常要求在树中查找具有某种特征的节点，或者对树

中全部节点逐一进行某种处理。这就提出了遍历二叉树。根据遍历的方向的选择，

就有了前序遍历，中序遍历和后序遍历以及层次遍历二叉树。因此掌握二叉树的各

种遍历二叉树算法非常重要，而且高效的遍历算法能够节省很多成本。

3概要设计

3．1模块划分

本程序包括七个模块：

（1）主程序模块

voidmain()

{

初始化；

以广义表表示法输出；

建立二叉树；

非递归先序遍历二叉树并输出；

非递归中序遍历二叉树并输出；

非递归后序遍历二叉树并输出；

1

层次遍历二叉树并输出；

}

（2）以广义表表示法输出——实现对二叉树的输出

3

（）二叉树建立模块——建立一个二叉树并

对二叉树进行初始化

4

（）非递归先序遍历模块——实现对二叉树的递归先序遍历并输出

5

（）非递归中序遍历模块——实现对二叉树的递归中序遍历并输出

6

（）非递归后序遍历模块——实现对二叉树的递归后序遍历并输出

（7）层次遍历模块——实现对二叉树的层次遍历并输出

4详细设计

4．1主要模块流程图

开始

广义表表示法输出printfbitree(t)

创建一棵二叉树t=creattree（）

非递归前序遍历nrpreorder(t)

非递归中序遍历nrinorder（t）

非递归后序遍历nrreorder（t）