数据结构实训是计算机科学与技术专业集中实践环节之一。数据结构是本专业一门重要的专业基础课程，是一门关键性核心课程。该课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术。该课程将为整个专业的学习以及软件设计水平的提高打下良好的基础。

数据结构是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践，设置数据结构实训环节十分重要。

本次实训我选择的题目是二叉树的遍历与应用算法设计与实现

二叉树是树形结构的一个重要类型，许多实际问题抽象出来的数据结构往往是二叉树类型，应用极为广泛。本次课程设计使用二叉链表来建立二叉树的存储结构，利用栈和队列来实现二叉树的中序非递归遍历和层序遍历，并利用递归来实现二叉树的先序、中序、后序遍历。本次设计还实现了计算二叉树中的叶子结点个数、求二叉树的深度、将二叉树中所有结点的左右孩子互换以及判断二叉树是否为完全二叉树等二叉树的应用算法。

本次设计使用的编程语言是C语言，使用的Microsoft Visual Studio2010编译实现。

    图1 系统模块结构图

（1）建立二叉树：利用二叉链表建立二叉树的存储结构。利用链式存储结构来存储一颗二叉树，即用链来指示元素的逻辑关系，二叉树中的每个结点用链表中的一个链结点来存储。

（2）实现二叉树的层序遍历：利用队列实现二叉树的层序遍历。队列是一种先进先出的存储结构，仅允许在表的前端进行删除操作而在表的后端进行插入操作，利用队列实现二叉树的层序遍历更加简洁和方便。

（3）实现二叉树递归遍历：利用递归的算法来实现二叉树的先序、中序和后序遍历。

（4）实现二叉树的中序非递归遍历：利用栈实现二叉树的中序非递归遍历。栈是一种后进先出的存储结构，仅限定在栈顶进行插入和删除操作，可以用栈来实现二叉树的中序非递归遍历。

（5）实现二叉树的应用：二叉树在一些搜索引擎和路由器中应用广泛，这些应用都要用到二叉树的最基本的应用算法：计算二叉树的叶子结点个数、求二叉树的深度、将二叉树中所有结点的左右孩子互换以及判断二叉树是否为完全二叉树。

（6）菜单功能：对二叉树的各种遍历和应用进行选择。

（7）显示功能：将二叉树的遍历和应用结果显示出来。

（8）退出功能：退出整个程序，结束运行。

2、数据结构分析

(1)顺序表是一种静态存储结构，需要预先知道数据大小来申请连续的存储空间，而且进行扩充时需要进行数据的搬迁。相对于顺序表，链表结构可以充分利用计算机的内存空间，实现灵活的内存动态管理且进行数据扩充是不需要数据的搬迁。在实际应用中，虽然顺序表的存取速度更高效，但是在一些搜素引擎中的大部分数据都是需要经常进行更新的，因此对于开发人员来说使用链表的删除和插入操作更有利于对引擎中的数据进行更新，动态分配存储空间，避免进行数据的搬迁。

通过上述分析，我选择二叉链表存储结构，存储结构如下：

typedef int Status;

typedef char TElemType; //二叉树结点的值的类型

typedef struct BiTNode {

TElemType data;//二叉树的结点值

struct BiTNode *lchild, *rchild; //左右孩子指针

}BiTNode, *BiTree;  //定义二叉树的存储类型