1、 本科生毕业论文 (设计 ) 题 目： 二叉树遍历的实现与教学演示 i 目 录 摘要 (关键字 ) . 1 Abstract（ Key words） . 1 前言 . 2 1 二叉树的概述 . 2 1.1 二叉树的定义 . 2 1.2 二叉树的性质 . 3 1.3 二叉树的存储结构 . 4 2 二叉树的遍历 . 6 2.1 常用的二叉树遍历的算法 . 6 2.2二叉树遍历的 C 程序演示过程 . 9 2.3 非递归遍历二叉树 . 12 2.4 二叉树遍历算法的应用 . 14 3 基于 FLASH的二叉树遍历课件应用实现 . 15 3.1课件简介 . 15 3.2结构设计分析 . 15 3.3主
2、要功能 . 16 4 教学设计 . 18 结束语 . 20 参考文献 . 21 致 谢 . 22 第 1 页 二叉树遍历的实现与教学演示 摘要 : 所有数据结构中，树是非常重要的一种，尤其是二叉树的遍历，学习者是应该牢固掌握的。在学习了二叉树的存储结构之后，学生开始接触了二叉树的遍历。很多学生或多或少地会感到些困惑，看似简单的递归算法，可要理解其遍历过程，未必能够一目了然。 其主要原因在于二叉树的遍历执行过程较复杂，不容易理解，学生会会此失去兴趣，因此针对如果进行讲解，学生在理解上也有一定的难度。本文对于二叉树的 遍历执行过程给予了直观的教学演示，主要通过图形的形式展示，可以一目了然，让同学们
3、对此不排斥，从而达预期的教学效果。可以从理论角度出发，边讲解边演示让同学们听懂、学会。还从信息技术与课程整合的角度，制作 FLASH 课件应用于教学中，提高教学质量。 从而更好的进行课堂教学，使学生更清楚、更容易的理解二叉树的遍历过程。 关键字： 二叉树 ; 遍历 ; 多媒体 Abstract: All of the data structure, the tree is a very important, especially in the binary tree traversal, learners should have a solid grasp of. In the study o
4、f the storage structure of the binary tree, the students came into contact with a binary tree traversal. Many students will feel more or less some confusion appears to be simple recursive algorithm, Ergodicll understand the process, may not be able to clear at a glance. The main reason lies in the i
5、mplementation of binary tree traversal of the more complicated process, it is not easy to understand, students will lose interest in this, so if on for students in understanding have a certain degree of difficulty. In this paper, the binary tree traversal of the implementation process to give a visu
6、al presentation of the teaching, mainly through the form of graphics display, you can at a glance, while on the side of presentation so that students understand and learn. Information Technology and also from the perspective of curriculum integration, the production of courseware used in FLASH teach
7、ing, improve teaching quality. In order to better classroom teaching so that students more clearly and more easily understand the process of binary tree traversal. Keywords： Binary Tree; Ergodic; Multimedia 二叉树遍历的实现与教学演示 第 2 页 前言 树是另外一种非线性数据结构，二叉树就是其中一种，这种数据结构在日常生活中是十分常见的，二叉树的 遍历是树结构的一种常用的、重要的运算，是树的
8、其它运算的基础。 从结构上来看，在 对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。即如何按一定的规律和次序访问树中的每个结点，使得每个结点被访问一次，而且仅被访问一次。 真正理解这一运算的实现及其含义有助于许多二叉树运算的实现及算法设计。然而，许多初学者开始时的学习效果不理想，原因是较难理解其内在规律。二叉树的遍历方法及相应过程如下。 1 二叉树 的概述 1.1 二叉树的定义 定义： 二叉树是 n(n 0)个结点的有限集，它或为空树 (n=0)，或由一个根结点和两棵分别称为左子树和右子 树的互不相交的二叉树构成。 (图 1-1) (
9、图 1-1) 特点： 每个结点至多有 2 棵子树 (即不存在度大于 2的结点 )二叉树的子树有左、右分，且其次序不能任意颠倒。 二叉树的五种基本形态：（如图 1-2） （图 1-2） A 只有根结点的二叉树 空二叉树 A B 右子树为空 A B 左子树为空 A B C 左右子树均非空 A B C D E F G 二叉树遍历的实现与教学演示 第 3 页 1.2 二叉树的性质 【性质 1】 在二叉树的第 i 层上至多有 2i-1 个结点 证明：用数学归纳法证明。 i=1时，只有一个根结点， 2 10 是对的。 假设对所有 j(1 jn，则结点 i没有左孩子；否则其左孩子结点的编号为 2i。 （ 3
10、）如果 2i+1n，则结点 i没有右孩子； 否则其右孩子结点的编号为 2i+1。 下面我们利用数学归纳法证明这个性质。 我们首先证明（ 2）和（ 3）。 当 i=1时，若 n 3，则根的左、右孩子的编号分别是 2， 3；若 n=MAX_TREE_NODE_SIZE) n=MAX_TREE_NODE_SIZE-1; for (i=1; iitemi=itemi; BT-n=n; （ 2）获取给定结点的左孩子 int LeftCHild(QBTree BT,int node) if (2*nodeBT.n) return 0; else return 2*node; RightChild(BT,n
11、ode)与这个操作类似，读者可试着自行完成。 （ 3）获取给定结点的双亲 int Parent(QBTree BT,int node) if (1lchild 和 T-rchild 为根指针的子树。 visit( BiTree *T ) printf(“%c”,T-data); 先序遍历： 若二叉树非空，则： （ 1） 访问根结点 （ 2） 先序遍历左子树 （ 3） 先序遍历右子树 对应递归算法如下： void PreOrder(BiTree *T) if (T!=NULL) printf(“%dt“,T-data); preorder(T-lchild); preorder(T-rchild
12、); 采用先序遍历得到的访问结点序列称为先序遍历序列，先序遍历序列的特点是：其第一个元素值为二叉树中根结点的数据值。 如图所示的二叉树，先序遍历序列为 : e c b a j f m k z 中序遍历： 若二叉树非空，则： （ 1）中序遍历左子树 （ 2）访问根 结点 （ 3）中序遍历右子树 二叉树遍历的实现与教学演示 第 8 页 对应递归算法如下： void PreOrder(BiTree *T) if (T!=NULL) preorder(T-lchild); printf(“%dt“,T-data); preorder(T-rchild); 采用中序遍历得到的访问结点序列称为中序遍历序列
13、，中序遍历序列的特点是：若已知二叉树的根结点的数据值，以应该数据值为届，将中序遍历序列分为两部分，前半部分为左子树的中序遍历序列，后半部分为右子树的中 序遍历序列。 如图所示的二叉树，中序遍历序列为 : a b c e f j k m z 后序遍历： 若二叉树非空，则： （ 1）后序遍历左子树 （ 2）后序遍历右子树 （ 3）访问根结点 对应递归算法如下： void PreOrder(BiTree *T) if (T!=NULL) preorder(T-lchild); preorder(T-rchild); printf(“%dt“,T-data); 采用后序遍历得到的访问结点序列称为后序遍历 序列，后序遍历序列的特点是：其最后一个元素值为二叉树中根结点的数据值。 如图所示的二叉树，后序遍历序列为 : a b c f k z m j e （图 2-1） e c j m z f b a k
