关键词: 算法设计, 二叉树, 中序遍历, 快速访问

Abstract: 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.

Key words: algorithm design, binary tree, inorder traversal, fast query