由先序序列和结点的左孩子情况构造严格二叉树的高效算法  

An Efficient Algorithm for Constructing a Strictly Binary Tree from Preorder Traversal and Left Child of Each Node

作　　者：唐自立[1] 

机构地区：[1]苏州大学计算机科学与技术学院,江苏苏州215006

出　　处：《南通大学学报（自然科学版）》2013年第1期9-13,共5页Journal of Nantong University(Natural Science Edition)　

基　　金：国家自然科学基金项目(61075040)

摘　　要：提出一种新的由一棵严格二叉树的先序序列和结点的左孩子情况构造该严格二叉树的非递归算法.通过实例给出了新算法的执行过程,同时说明,与已有的等价递归算法相比,新算法的时间复杂性更低,而最差情况空间复杂性相同.A new non-recursive algorithm is presented for constructing a strictly binary tree from its preorder traversal and the left child of each node. The execution of the new algorithm is illustrated by an example. Let n be the number of nodes of a strictly binary tree. The time complexity of the new algorithm is O（n）, and it is lower than that of the equivalent recursive algorithm. The worst case space complexity of the new algorithm is 0 （n）, and it is the same as that of the equivalent recursive algorithm.

关 键 词：先序序列 结点 左孩子 非递归算法 严格二叉树构造 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论] TP301.6[自动化与计算机技术—计算机科学与技术]