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

Fast algorithms educed from intrinsic properties of node indices of binary trees

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

Through a study on properties of node-indices of a binary tree,the paper derives for processing binary trees several new non-recursive and stack-free algorithms,including an algorithm to query the Lowest Common Ancestor（LCA） of two nodes in a complete binary tree,an algorithm for fast inorder traverse,an algorithm for inter-conversions between the sequential sequence and the inorder sequence,and an algorithm to restore a complete binary tree from its sequential sequence or inorder sequence.All the new algorithms are of excellent time-complexity and spatial complexity.In aspect of time-complexity, the new LCA-query algorithm can answer without any preprocessing a query of LCA of two nodes in a complete binary tree in constant time and the other new algorithms are linear time complexity.In aspect of spatial complexity,all the new algorithms are constant spatial complexity.Furthermore,all new algorithms contain merely addition,subtraction and bitwise operations and thus fit both conventional programming and expert developments such as embedded system and so on.