| 构造二叉树的两个改进算法 |
| |
| 引用本文： | 赵素萍.构造二叉树的两个改进算法[J].现代计算机,2006(10):99-101. |
| |
| 作者姓名： | 赵素萍 |
| |
| 作者单位： | 洛阳师范学院,洛阳471022 |
| |
| 摘 要： | 在数据结构中,已知一棵二叉树的先序序列和中序序列,可唯一确定此二叉树.本文在分析建立二叉树经典算法的时间复杂度的基础上,给出了两个改进算法:①利用哈希函数,使得改进后的算法在最差情况下,时间复杂度由O(n2)降为O(n);②利用栈和控制输入的结点序列构造二叉树,时间复杂度也由O(n2)降为O(n).
|
| 关 键 词： | 先序序列 中序序列 二叉树 哈希函数 栈 时间复杂度 |
| 收稿时间： | 2006-06-19 |
| 修稿时间： | 2006-06-19 |
Two Improved Algorithms for Constructing Binary Tree |
| |
| ZHAO Su-ping.Two Improved Algorithms for Constructing Binary Tree[J].Modem Computer,2006(10):99-101. |
| |
| Authors: | ZHAO Su-ping |
| |
| Affiliation: | Luoyang Normal College, Luoyang 471002 China |
| |
| Abstract: | In the data structure,the binary tree can be uniquely confirmed when the nodes sequences of this binary tree for preorder traversal and inorder traversal are knows. In this thesis, an algorithm of creating binary tree is analyzed. Two improved algorithms are given. The time complexity of the improved algorithm goes down from O(n2) to O(n). |
| |
| Keywords: | Preorder Traversal Inorder Traversal Binary Tree Hash Function Stack Time Complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
