- 上一篇：Android操作系统下的贪吃蛇游戏设计
- 下一篇：基于Android系统的SQLite数据库编程实现
对于一棵二叉树来说，在非递归算法实现二叉树的遍历中，要用到栈这种数据结构，使用栈是为了保存根节点信息，用以在访问完左子树之后通过栈找到右子树继续访问，另外，二叉树本身有递归特点，每个结点在右子树没有被访问前都要保存结点信息，符合栈后进先出的特点。 非递归后序遍历中关键的问题是判断根结点何时出栈，大多数算法是在二叉树结点的存储结构中加入一个标志位。程冠琦[9]提出了一种新的方法，在算法中引入了一个同步的标志栈，用来保持前一个入栈的结点的状态。在标志位算法中，这个标志位对先序和中序算法基本没用，还要分配存储空间。在同步栈方法中，同步栈属于局部变量，后序遍历后该栈所占空间将自动销毁，空间复杂度较小，相比标志位算法更好。
二叉树中有一种特殊的二叉树，中序遍历之后的输出是有序的，这种二叉树叫二叉排序树，在查找与搜索中具有重要的运用，其中一个运用就是在图书搜索中。目前大多数图书检索系统采用的的查找方法是顺序查找法，也就是逐条记录依次查找的方法，这种方法算法简单，但是效率十分低下，时间复杂度比较高，当查找的数据量较大时，耗费时间较多。叶玉萍[10]研究了二叉排序树在图书检索中的应用，用将要被检索的图书简码建立二叉排序树，并将建立的二叉排序树进行平衡化处理，使之为平衡二叉树[]，在检索时候，只需输入图书名称的首字母就可以很快的查找到该图书。由于二叉排序树的结构，检索效率大大提高，在大型图书商场和图书馆图书检索中具有重要的应用。
基于遍历序列的唯一确定二叉树或树的方法体现了二叉树或树的遍历序列的部分性质，也是建立二叉树或树的存储结构的主要依据. 唐自立[11]研究发现了一项结论，根据一棵二叉树的两种遍历序列或者遍历序列和结点的某些信息可以唯一确定该二叉树。并分别针对树、严格二叉树和二叉排序树研究，大体上介绍了基于遍历序列的唯一确定树或二叉树的方法，进一步完善了树或二叉树的遍历序列方面的性质[11]。
因为二叉树在很多方面具有很重要的应用，因此对于二叉树的研究很有意义，本文介绍了树和二叉树的一些基本知识，设计了实验中对于二叉树的教学演示软件，对二叉树的教学具有一定帮助。
1.2 论文的主要工作
本文所作的研究工作主要包括：
a) 对树和二叉树概念进行了简要的图形化介绍。
b) 介绍了二叉树和二叉排序树的各种操作和算法。
c) 设计了软件来演示二叉树结构和操作。
1.3 开发工具介绍
本文软件设计采用了visual c++，Visual C++是微软公司推出的开发工具，目前已经是国内外使用最多的高级程序设计语言之一[14]。与其它软件开发工具相比，Visual C++开发工具有以下优点:
a) 面向对象、可视化开发。
Vc++提供了面向对象的应用程序框架微软基础类库MFC (Microsoft Foundation Class,）,简化了程序员的编程工作，提高的模块的可重用性。另外，Visaul C++提供了基于CASE技术的自动生成和维护工具---AppWizard、ClassWizard、Visual Studio、WizardBar等，帮助用户直观地、可视地设计软件的用户界面，方便编写和管理各种类，维护程序源代码，提高了开发效率[13]。
b) MFC 基础类库已经成为工业标准类库，得到了总多软件开发商的支持。
由于很多的开发商都采用Visual C++开发相关软件，这样用Visual C++ 开发的程序就与其他应用软件有许多相似之处，容易学习和使用。