一种构建严格平衡二叉搜索树的非递归算法

• 作者: 周康 王防修
• 来源期刊: 武汉工业学院学报
• 学科: 工学
• 关键词: 二叉搜索树 平衡二叉树 严格平衡二叉树 平衡二叉搜索树 严格平衡二叉搜索树
• 年，卷（期）: 2013,（4）
• 所属期刊栏目: 信息与控制工程
• 页码范围: 32-34,43
• 页数: 4页
• 分类号: TP391
• 字数: 2666字
• 语种: 中文
• DOI: 10.3969/j.issn.1009-4881.2013.04.008

摘要

针对传统算法所构造的平衡二叉搜索树并非真正平衡的二叉搜索树，设计了一种构建严格平衡二叉搜索树的非递归算法。改进后的算法具有计算速度快、占用内存小、计算机易于实现等优点。改进算法的核心是生成严格二叉搜索树的先序序列，提出了对升序序列的进行二分得到严格二叉搜索树的先序序列，讨论并给出了构建严格二叉搜索树的快速算法，该算法充分利用了栈在计算过程中提供的二分信息得到严格二叉搜索树的先序序列，该算法与传统算法相比可更快地构建严格二叉搜索树。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王防修	武汉轻工大学数学与计算机学院	23	33	4.0	5.0
2	周康	武汉轻工大学数学与计算机学院	10	32	4.0	4.0