二叉树的先序遍历和中序遍历的非递归算法

从二叉树先序遍历递归算法的执行过程的分析入手,总结出二叉树先序遍历的实质,从而得出利用栈的二叉树的非递归算法。最后,再从分析二叉树中序遍历与先序遍历过程实质的不同之处,得出了二叉树中序遍历的非递归算法。重点在于对二叉树先序和中序遍历过程实质的分析。     

中序遍历二叉树的教学方法研究

结合教学中学生难以理解与掌握中序遍历二叉树这一实际情况,本文提出利用下压法进行二叉树的中序遍历,同时,利用栈的思想推导中序遍历二叉树的递归算法和非递归算法,清晰直观,便于学生更好的学习与理解。     

用栈结构实现二叉树的非递归中序遍历算法

二叉树作为数据结构中的一个重要的部分,有着广泛的应用,其中二叉树的遍历是二叉树操作的根本。文中通过分析二叉树的中序遍历过程,结合栈的先进后出特点,归纳出二叉树的中序遍历非递归算法。     

二叉树的遍历探究与应用

通过对同一棵二叉树的前序遍历、中序遍历、后序遍历及层次遍历得到四个不同序列的分析,概括出二叉树的前序遍历、中序遍历、后序遍历及层次遍历序列间的关系,确定对应的二叉树。     

从中序遍历及后序遍历构造二叉树

本文给出了一个算法，该算法输入一棵二叉树的中序遍历和后序遍历的结点序列，构造出该二叉树。该算法具有Ｏ（ｎ）时间复杂度，是解决该问题的最优算法，其中ｎ为二叉树的结点数。     

二叉树演绎于结点序号内蕴性质的快速算法

通过研究二叉树结点顺序存储序号的性质,演绎出了二叉树非递归无堆栈的一些新算法,包括完全二叉树两结点最近共同祖先（LCA）的查询算法、中序遍历算法、顺序序列与中序序列的互转算法以及从中序序列恢复层次结构的算法。新的算法都具有很好的时间复杂度,其中LCA查询算法可在常数时间内实现且不需要任何预处理过程,其他算法均为线性时间复杂度。所有算法均为常数空间复杂度,仅涉及到简单的加减运算与位运算,既可用于常规程序设计也可用于嵌入式等专业开发。     

一种优化的线索二叉树方法

本文在分析传统线索二叉树的基础上,提出了一种新的线索二又树,它比传统的先序和后序线索二叉树更优越．在进行先序和后序遍历时,如同对线性链表操作。非常简单。     

完全二叉树非递归无堆栈先序遍历算法的研究

通过对满二叉树的层次结构、顺序序列与先序序列三者之间解析关系的研究,得到了满二叉树的层次结构及顺序序列与先序序列之间互相转换的算法,并由此演绎出了非递归无堆栈方式的完全二叉树先序遍历以及先序与顺序互转算法。该算法可在常数时间内完成单个结点的查询,在线性时间内完成整个序列的遍历或互转。以精准二进制编码的解析公式为基础,易于与位运算结合,不仅适合常规程序设计,而且适合于嵌入式及相关的专业开发。通过一个简单的示例,说明了该算法在虚拟植物建模方面的应用。     

由遍历结果还原二叉树的递归算法

二叉树的遍历操作和其它操作的算法实现,都必须先创建二叉树。分析常规创建二叉树方法的特点和不足,给出利用中序遍历和后序遍历结果还原二叉树的算法,利用这一方法,给出由前序遍历和后序遍历还原二叉树的算法,最后,提供利用次层遍历和中序遍历还原二叉树的算法。     

二叉树遍历的非递归算法

本文对<数据结构>课程的重点和难点内容之一:二叉树遍历的非递归算法进行了研究,提出了一个系统化公式化的解决方案,并给出了用C 语言描述的先序、中序和后序遍历非递归算法的具体实现.     

基于遍历序列的唯一确定树或二叉树的方法

基于遍历序列的唯一确定树或二叉树的方法既体现了树或二叉村的遍历序列的部分性质,又是建立树或二叉村的存储结构的主要依据,本文首先介绍了由一棵二叉树的某两种遍历序列或某种遍历序列和结点的某种信息可以唯一确定该二叉树的各种可能方法,然后分别针对树、严格二叉树与雨季叉排序树加以介绍,本文比较全面的介绍了基于遍历离列的唯一确定树或二叉树的方法,进一步完善了树或二叉树的遍历序列的性质。     

一种二叉树非递归遍历算法的C语言实现

针对二叉树的链式存储结构,分析了二叉树的各种遍历算法,探讨了递归算法的递推消除问题,提出了一种改进的非递归遍历算法并用C语言予以实现。     

一种基于二叉树遍历的数字图像置乱方法

针对近年来兴起的数字图像信息安全问题，从二叉树的性质出发，提出了一种基于二叉树遍历的数字图像置乱方法，并讨论了该置乱方法的周期性及其逆变换。该方法简便易行，适用于任意大小的图像，且具有很好的置乱效果和极大的置乱周期。在一定的攻击下，置乱后的图像可以恢复原始图像，在一定程度上可以满足数字图像加密和隐藏的鲁棒性要求。     

Efficient algorithms to create and maintain balanced and threaded binary search trees

The algorithm proposed by Chang and lyengar to perfectly balance binary search trees has been modified to not only balance but also thread binary search trees. Threads are constructed in the same sequence as normal pointers during the balancing process. No extra workspace is necessary, and the running time is also linear for the modified algorithm. Such produced tree structure has minimal average path length for fast information retrieval, and threads to facilitate more flexible and efficient traversing schemes. Maintenance and manipulation of the data structure are discussed and relevant algorithms given.     

表达式与二叉树的相互转换

数学表达式、栈的操作、二又树的遍历,这几个概念在数据结构的教材中是不可缺少的。数学表达式求值是程序设计语言编译中的一个最基本问题,也是栈应用的一个典型例子,用它来研制出各种类型的电子计算器（前缀计算器、中缀计算器（常见的计算器）、后缀计算器）。在数据结构中没有解决表达式与二又树之间的相互转换关系,也就是说不能由一种表达式迅速地得到另外的两种表达式,也就难于解决其他两种计算器的研制过程。本文旨在研究表达式与二叉树间的相互转换关系,便于由一种表达式（或表达式树）迅速求出其他的表达式,再通过栈的应用（操作）研制出三种不同的计算器（栈的应用在数据结构的教材中都有,在此文中不予介绍）。     

Generalized non-recursive traversal of binary trees

A non-recursive algorithm for the traversal of a binary tree is presented in which the order of traversal is defined by an external data array, allowing any of the six possible orders to be selected without modification to the algorithm itself. The extra storage requirements are three pointer variables and two bits per node (or two bits per level if an auxiliary stack is used.) The algorithm is a generalization of the pointer reversal method of Schorr and Waite and is derived by transformation of a generalized recursive version. The algorithm is described using the notation and conventions of Pascal.     

一种改进的点在多边形内外判断算法

为解决多边形内外算法中BSP树退化为链表的问题,提出一种改进的点在多边形内外的判断算法。在构建水平扫描线的BSP树之前,对水平扫描线按照Y值进行排序,将排好序的水平扫描线按照二分法的顺序插入到BSP树中,其查找时间复杂度为O(lbn)。实验结果表明,该算法在不增加BSP构建时间复杂度的前提下,能够保证BSP树的查找效果总是最优的,且简单易行,具有较好的通用性。