立体二叉树及其应用

Solid Binary Tree and Applications

文章提出了立体二叉树的数据结构,对立体二叉树的基本概念和性质进行了讨论;对满立体二叉树结构的结点分布和结点编码之和问题进行了研究并给出了有关的公式;最后探讨了立体二叉树在分类中的应用,提出了立体堆的分类方法,并对它的算法实现进行设计与分析,得出了立体堆分类方法在最坏情况下的时间复杂性,从而减少了堆分类方法的时间复杂性的常数因子。

In this paper,a data structure called the Solid Binary Tree （SBT） is proposed,and the basic concepts and properties of the SBT are discussed.The node distribution and the coding sum of the full SBT are researched and the related formulaes are given.At last,a method of the solid heap sort is presented,and its algorithm is designed and analyzed as well.The time complexity of the worst case of the solid heap sort is derived.It lessens the constant factor of the time complexity of the heap sort.