魏志威，王防修

(武汉轻工大学 数学与计算机学院，湖北 武汉 430023)



一种无需借助栈的严格平衡二叉树建立

魏志威，王防修

(武汉轻工大学 数学与计算机学院，湖北 武汉 430023)

摘要：针对当前严格平衡二叉树的建立需要借助栈来实现的问题，提出一种无需借助栈也能建立严格平衡二叉树的算法。为能对关键字进行二分查找，需要对现有的关键字序列进行排序,以便统计关键字的有序序列中每个关键字在二分查找时的比较次数。在统计完所有关键字的二分查找的比较次数后,通过关键字比较次数序列的排序得到严格平衡二叉树序列。最后，用非递归的二叉排序树插入算法依次插入严格平衡二叉树序列的每个关键字，得到的二叉排序树就是一棵严格平衡二叉树。算例仿真表明，无需借助栈也可建立一棵严格平衡二叉树。

关键词：选择排序；二叉排序树；严格平衡二叉树；二分查找；查找效率

1引言

在信息的查询中，二分查找由于具有较高的查找效率而受到人们的青睐。然而，二分查找[1]要求索引表在计算机内存里必须以有序顺序表的形式存放。如果内存中地址连续的空闲存储空间不够，则这样的顺序表无法建立，从而也就无法实现二分查找。与二分查找具有相同查找效率的是严格平衡二叉树，而严格平衡二叉树能充分利用地址不连续的空闲内存空间。因此，从内存管理[2]的角度出发，严格平衡二叉树的查询使用得更加广泛。……