| 由先序序列和结点的层数构造严格二叉树的高效算法 |
| |
| 引用本文： | 唐自立.由先序序列和结点的层数构造严格二叉树的高效算法[J].南通大学学报(自然科学版),2014(4):12-16. |
| |
| 作者姓名： | 唐自立 |
| |
| 作者单位： | 苏州大学计算机科学与技术学院 |
| |
| 基金项目： | 国家自然科学基金项目(61075040);江苏省高校自然科学研究重大项目(10KJA520047);江苏省自然科学基金项目(BK2012645);江苏省产学研联合创新资金项目(BY2012114);苏州大学“东吴学者计划”项目 |
| |
| 摘 要： | 提出一种新的通过一棵严格二叉树的先序序列和这棵严格二叉树的结点的层数构造这棵严格二叉树的非递归算法.举例说明新算法的执行过程.对于有n个结点的严格二叉树,新算法的时间复杂度为O(n),比相应的递归算法的低,新算法的最差情况空间复杂度为O(n),与相应的递归算法的相同.
|
| 关 键 词： | 先序序列 结点 层 二叉树构造 非递归算法 |
An Efficient Algorithm for Constructing a Strictly Binary Tree from Preorder Traversal and the Level of Each Node |
| |
| Authors: | TANG Zili |
| |
| Institution: | TANG Zili;School of Computer Science and Technology, Suzhou University; |
| |
| Abstract: | A new non-recursive algorithm was proposed for constructing a strictly binary tree from its preorder traversal and the level of each node. The execution of the new algorithm was illustrated by an example. For a strictly binary tree with n nodes, the time complexity of the new algorithm is O（n）, and it is lower than that of the corresponding recursive algorithm, the worst case space complexity of the new algorithm is O（n）, and it is the same as that of the corresponding recursive algorithm. |
| |
| Keywords: | preorder traversal node level binary tree construction non-recursive algorithm |
| 本文献已被 CNKI 维普 等数据库收录！ |
