1、本科毕业论文（20 届）二叉树算法的动画演示所在学院专业班级 计算机科学与技术学生姓名指导教师完成日期摘要现代社会是信息化的社会,国家对计算机方面的人才的重视以及社会对高素质计算机人才的缺乏，使得高校越来越重视计算机方面的教学工作。算法是计算机领域的一个重要的分支，其中二叉树的算法是计算机教学中的基础和重点环节。因此，研究一个更加形象生动利于学生理解的二叉树算法演示程序是非常有必要的。本文主要介绍了二叉树算法的动画演示软件的开发背景、开发意义、应用目标、技术简介、可行性分析、系统分析与设计、系统实现、出现的问题及解决方案。系统综合运用了数据结构的相关知识理论，采用 Flash、HTML 和 C
2、SS 技术，主要利用了Flash、HTML 强大的人机交互能力。系统包括数据结构算法演示网站和二叉树算法的动画演示软件。其中二叉树算法的动画演示软件包括二叉树的遍历、二叉树遍历算法的应用、二叉树的创建、二叉树的线索化、树和森林的基本操作、哈夫曼树六个模块。本系统突出从教师教学环节中的难点和学生易于出错的知识点这两方面出发，解决了现有二叉树算法演示软件不能满足计算机教师教学要求的问题，可以使学生更好地理解二叉树的基本算法及操作，也可以使教师的教学工作更加高效。关键词：Flash；HTML；CSS；二叉树AbstractThe modern society is an information so
3、ciety. The situation of our country values computer talents and the lack of computer talents, making universities pay more and more attention in teaching computer work. Algorithm is an important branch of computer field, where the algorithm of binary tree is the foundation and key point of computer
4、teaching. Therefore, to study a more vivid binary tree program that students can easily understand is very necessary. Paper mainly introduced the topic development background, significant of developing, application objectives, introduction of technology, feasibility analysis, system analysis and des
5、ign, system implementation, problems and solutions. The system is based on Flash, HTML and CSS technologies. The system uses the relevant knowledge theory of data structure. The system takes advantage of Flash, HTML powerful interactive capabilities.System includes a data structures algorithms demo
6、site and binary tree algorithm animation software. Binary tree algorithm animation software which includes binary tree traversal, binary tree traversal algorithm applications, binary tree creation, threaded binary tree, trees and forests basic operations, Huffman tree. The system highlights from the
7、 difficulties in teachers teaching and error points in students learning to solve problem of the existing binary tree algorithm demo software does not meet the requirements of teaching computer. So that students can understand the basic algorithm and operation of binary tree better and also allows t
8、eachers work more efficient.Keywords: Flash；HTML；CSS；Binary tree目 录1. 引言 .11.1 开发背景 .11.2 开发意义 .11.3 应用目标 .11.4 可行性分析 .21.4.1 技术可行性 .21.4.2 经济可行性 .22技术简介 .32.1 Flash 技术 .32.1.1Flash 软件特性 .32.1.2 Flash 基本功能 .32.1.3Flash 脚本语言 .32.2 超文本标记语言 .42.2.1 语言特点 .42.3 级联样式表 .42.3.1 使用方式 .52.2.2 布局特点 .53. 系统分析 .
9、63.1 系统功能分析 .63.2 模块分析 .64.系统设计与实现 .104.1 介绍网站模块设计与实现 .104.2 二叉树算法的动画演示软件模块设计与实现 .114.2.1 二叉树的创建模块设计与实现 .114.2.2 树和森林的基本操作模块设计与实现 .124.2.3 哈夫曼树模块设计与实现 .145.出现的问题及解决方案 .165.1 数据结构算法演示网站的问题及解决方案 .165.2 树和二叉树的演示的问题及解决方案 .165.2.1 二叉树的遍历模块的问题及解决方案 .165.2.2 二叉树的创建的问题及解决方案 .175.2.3 二叉树的线索化的问题及解决方案 .17结论 .1
10、8致谢 .19参考文献 .2011. 引言1.1 开发背景现代社会是信息化的社会，各行各业都用到计算机，社会需要大量的高素质计算机人才。随着国家对计算机方面的人才的重视以及社会对于高素质的计算机人才的缺乏，使得高校越来越重视计算机科学的与技术教学工作。数据结构是计算机科学中的一门综合性的专业基础课，数据结构是计算机科学技术专业教学计划中的核心课程之一，也是其他非计算机专业的主要选修课之一。数据结构的研究不仅涉及计算机软件的研究范围，而且和计算机硬件的研究也有密切的关系。而树和二叉树的算法是数据结构教学中的基础和重点环节。传统的计算机数据结构教学中由于缺乏演示软件或者演示软件不够形象生动，使得学
11、生对于这部分重点内容的掌握程度不够，极大地影响了教师教学的效率和教学进度。因此研究一个更加形象生动利于学生理解的二叉树算法演示软件是非常有必要的。二叉树算法的动画演示软件可以使学生更好地理解二叉树的基本算法及操作，也可以使教师的教学工作更加高效。1.2 开发意义该项目开发的软件为基于 Flash、HTML（Hypertext Markup Language）和CSS（Cascading Style Sheets）技术的二叉树基本算法演示软件。目前计算机教师的教学工作面临着二叉树教学演示软件严重不足的问题，同时现有的二叉树教学演示软件不够形象生动，使得学生难以理解二叉树的基本知识和操作。本软件正
12、是鉴于二叉树教学软件不能满足计算机教学工作的现状构思出来的。二叉树算法的动画演示软件设计完成后可用于高校计算机数据结构教学的工作中。该软件突出从教师教学环节中的难点和学生易于出错的知识点这两方面出发，解决了现有二叉树算法演示软件不能满足计算机教师教学要求的问题。1.3 应用目标二叉树算法的动画演示软件基于 Flash、HTML 和 CSS 技术，本软件应用于高校的计算机数据结构的教学工作中，可以演示二叉树的先序递归遍历、中序递归遍历、后序递归遍历、先序非递归遍历、中序非递归遍历、后序非递归遍历、统计二叉树的叶子结点数、计算二叉树的深度、查找数据元素、结合“扩展先序遍历序列”创建二叉树、中序线索
13、化二叉树、中序线索化二叉树查找前驱、中序线索化二叉树查找后继、树转换为二叉树、二叉树转换为树、二叉树转换为森林、森林转换为二叉树、哈夫曼树的构造和哈夫曼编码。计算机教学工作者在运行二叉树算法的动画演示软件中可以控制程序的播放，使得教师在教学中在学生不易于理解的地方多次演示，便于学生理解。学生也可以在教师的指导下借助该软件对二叉树的基本算法进行预习、复习。21.4 可行性分析我国目前正处于信息化飞速发展的时代，国家和社会的现代化建设急需具备全面技术能力的高素质计算机人才。在此背景下，国家不断加大对高校计算机学科教学研究工作的扶持力度。为了进一步响应国家号召，为国家输送技术过硬的计算机人才，各高校
14、已经越来越重视对计算机学生的基础知识的培养和他们对基础知识的掌握情况。所以二叉树算法的动画演示软件有其开发的需求。当二叉树算法的动画演示软件开发成功后，计算机教学工作者可以将其应用到数据结构这门课程的教学工作中，让学生把数据结构的基本算法掌握得更加扎实。同时本软件的平台是数据结构算法演示网站，这个平台可以为以后开发人员提供二次开发的平台和参考借鉴的地方。所以开发二叉树算法的动画演示软件非常有必要，而且鉴于现在计算机软件及语言的发展，可以使开发人员在很好地满足计算机教学工作者的教学要求下开发出形象生动的软件，所以开发本软件是可行的。1.4.1 技术可行性本系统包括数据结构算法演示网站和二叉树算法
15、的动画演示软件。其中数据结构算法演示网站所用开发技术为 HTML 和 CSS，二叉树算法的动画演示软件所用的开发技术为Flash。这些技术都已经成熟，所以本系统具备技术可行性。1.4.2 经济可行性目前国家每年对计算机方面的研究的投资和支持力度在逐年增加，以中关村为首的一大批高新技术产业园也在全国各地茁壮发展起来，许多计算机公司也在国家的扶持下越来越壮大。在各高校，国家也为一大批计算机学科带头人下拨科研经费，为学校建立实验室。而本系统的开发工作可在高校的实验室中进行，不需要额外投资硬件设备，所以本系统具备经济可行性。32技术简介2.1 Flash 技术Flash 是一种用于动画创作与应用程序开
16、发的技术。现在流行的 Flash 技术是由macromedia 公司推出的交互式矢量图和 Web 动画的标准。Flash 为创建数字动画、交互式 Web 站点、桌面应用程序以及手机应用程序开发提供了功能全面的创作和编辑环境。Flash 广泛应用于建立形象生动的应用程序，它包含丰富的声音、图形、视频和动画等形式。可以在 Flash 中建立图形、动画等原始内容或者从其它应用程序（如 Photoshop 或Illustrator）导入他们，快速设计简单的动画，以及使用 Adobe ActionScript3.0 开发与人的交互式项目。计算机开发人员可使用它来创建演示文稿、应用程序和允许用户交互的项目
17、。Flash 可以包含生动的动画、视频、复杂演示文稿和应用程序以及介于它们之间的任何内容。2.1.1Flash 软件特性Flash 广泛应用于基于互联网网页的矢量动画设计。利用 Flash 制作出来的影片占用存储空间较小。使用 Flash 创作出的影片的存储格式特殊，而且 Flash 播放器被应用于全世界 97%以上的网络浏览器中。Flash 作为平台实现了 Macromedia 提出的“富因特网应用”概念。2.1.2 Flash 基本功能Flash 动画设计有三个逻辑上紧密相连的基本功能，它们是整个 Flash 动画设计知识体系中最重要的、也是最基础的，包括：绘图和编辑图形、补间动画和遮罩。
18、绘图和编辑图形是创作 Flash 动画的基本功能。Flash 包括多种绘图工具，这些绘图工具可以在不同的绘制模式下工作。Flash 提供的三种绘制模式决定了“舞台”上的对象的编辑方式和交互方式。补间动画在 Flash 动画的三个基本功能中很重要，是 Flash 动画设计的核心功能，它有动画补间和形状补间两种形式。动画补间是用于图形及元件的动画，形状补间是用于形状的动画。遮罩是 Flash 动画设计三大基本功能中的出彩点，在配合补间动画的基础上，遮罩可以使用户创造更多丰富多彩的动画效果。遮罩是遮罩图层中的图形或者文字等对象，透出下面图层中的内容。遮罩主要有两种用途：一种是用来遮罩住某一元件的一部
19、分，从而实现一些特殊的效果；另一种是用在整个场景或一个特定区域，使场景外的对象或特定对象外的对象不可见。2.1.3Flash 脚本语言Flash 的脚本语言 ActionScript 是一门吸收了 C+（C plus plus） 、Java 以及JavaScript 等编程语言部分特点的新的语言；它使用英文单词为编程语言给 Flash 影片4设置指令。Flash 脚本语言使 Flash 影片比普通的按照线性模式播放的动画具备强大得多的人机交互能力。ActionScript 是 Flash 内置的编程语言，用它为动画编程，可以实现各种动画特效、对影片的良好控制、强大的人机交互及与网络服务器的交互
20、功能。在某些情况下，ActionScript 还可以指挥用户的操作系统、浏览器、各种外部程序等，并向其传递参数。正是由于 ActionScript 具备如此强大的交互能力，而二叉树算法的动画演示软件需要满足计算机教师教学活动中的交互需求，所以在选择开发二叉树算法的动画演示软件的时候我选择了 Flash 脚本语言。2.2 超文本标记语言由于二叉树算法的动画演示软件演示的是数据结构的一个方面的内容，为了便于以后将数据结构的其它方面演示程序加入进来，所以选择用网页作为载体，即把二叉树算法的演示软件的可执行文件链接到网页中的超链接上，所以需要用到超文本标记语言来制作一个网站。超文本标记语言（英文缩写
21、HTML）是标准通用标记语言的下一个应用，也是一种规范，一种标准，它通过标记符号来标记要显示的网页中的各个部分。网页文件本身是一种文本文件，通过在文本文件中添加标记符，可以告诉浏览器如何显示其中的内容（如：文字如何处理，画面如何安排，图片如何显示等） 。2.2.1 语言特点超文本标记语言功能强大，支持不同数据格式的文件嵌入，其主要特点如下：简易性：超文本标记语言版本升级采用超集方式，从而更加灵活方便。可扩展性：超文本标记语言的广泛应用带来了加强功能，增加标识符等要求，超文本标记语言采取子类元素的方式，为系统扩展带来保证。平台无关性：超文本标记语言可以使用在广泛的平台上。正是由于超文本标记语言如
22、此强大、简单易学，所以在选择制作网站时我选择了用超文本标记语言来编写网站。2.3 级联样式表二叉树算法的动画演示软件需要一个网站为载体，在编写这个网站时需要对其网页风格进行设计，所以需要用到级联样式表技术。级联样式表简称为“CSS”(Cascading Style Sheet)。级联样式表是一种用来表现HTML 或 XML 等文件样式的计算机语言。在进行网页风格的设计时，用级联样式表可以精确地指示网页元素的位置，外观及效果。用级联样式表不仅可以对网页对象和样式进行编辑，还可以进行初步交互设计。52.3.1 使用方式级联样式表有三种使用方式：外部样式、内页样式和行内样式。其中，外部样式是将网页链
23、接到外部样式表；内页样式是在网页上创建嵌入的样式表；行内样式是应用内嵌样式到各个网页元素。为了在数据结构的算法演示网站上的部分网页拥有相同的样式，所以在选择级联样式表的使用方式时我用了外部样式表。外部样式表可以在一个外部表中定义样式，然后其它网页选用和其一样的样式定义，并将它们链接到所有网页，以保证网页外观的一致性。外部样式表在修改时也非常便捷，当要更改样式时，只需在外部样式表中修改一次即可使所有与该样式表相链接的网页都更改。2.2.2 布局特点使用 CSS 进行布局具有以下几种优点：使代码变得精简，减少重构难度，当修改布局时只需修改 CSS 文件中的一个代码即可；加快了网页访问速度，提高用户
24、对网站的体验度；便于搜索引擎抓取，提高网站的访问量。63. 系统分析3.1 系统功能分析基于 Flash、HTML 和 CSS 的数据结构算法的演示包括介绍网站和二叉树算法的动画演示软件。其中介绍网站主要包括绪论、线性表、栈、队列、串、数组、广义表、树和二叉树、图、排序、查找和文件等部分。二叉树算法的动画演示软件主要实现了二叉树的遍历、二叉树的遍历的应用、二叉树的创建、二叉树的线索化、树和森林的转化、哈夫曼树等模块。每个模块又包含许多子模块，其中：二叉树的遍历包括先序递归遍历、中序递归遍历、后序递归遍历、先序非递归遍历、中序非递归遍历和后序非递归遍历；二叉树的遍历的应用包括统计二叉树的叶子结点
25、数、计算二叉树的深度、先序查找数据元素、中序查找数据元素和后续查找数据元素；二叉树的线索化包括中序线索化二叉树、中序线索化二叉树的前驱查找和中序线索化二叉树的后继查找；树和森林的转换包括树转换为二叉树、二叉树转换为树、二叉树转换为森林和森林转换为二叉树；哈夫曼树包括哈夫曼树的构造和哈夫曼编码。3.2 模块分析本系统基于 Flash、HTML 和 CSS，主要包含介绍网站和二叉树算法的动画演示软件，其中介绍网站的功能模块图如图 3-1 所示：图 3-1 介绍网站功能模块图数据结构算法演示绪论线性表栈 队列串 数组广义表树和二叉树图 排序查找文件二叉树的线索化树和森林的转换二叉树的遍历二叉树遍历的应用二叉树的创建哈夫曼树
