期刊论文

A strict balanced binary tree established based on the double linked list

中文

武汉轻工大学学报

2095-7386

2015

3

75-79

10.3969/j.issn.2095-7386.2015.03.016

国家自然科学基金资助项目（61179032）；

本校为第一机构

针对目前严格平衡二叉树的建立需要借助有序顺序表来实现的问题,提出一种无需借助有序顺序表也可建立严格平衡二叉树的算法。为了建立关键字的严格平衡二叉树,需要首先建立一个关键字的有序双链表,然后用分治法构造严格平衡二叉树的根节点和左右子树。为了验证所建立的二叉树是严格平衡的,还提出了判断一棵二叉树严格平衡的两种检验方法。其中,严格平衡二叉树的定义法是一种直接判断法,而平均查找长度法可以间接判断一棵二叉树的平衡性。算例仿真表明,无需借助有序顺序表也可建立一棵严格平衡二叉树。

In view of the problem of the previous strict balanced binary tree needing a orderly sequence table to cre -ate,this paper proposes an algorithm which can also establish a strict balanced binary tree without the orderly se -quence table .In order to establish a strict balanced binary tree about keywords ,the algorithm needs to first establish a ascending double linked list about keywords , then it uses partition method to construct strict balanced binary tree root node and left and right subtrees .In order to ensure the correctness of the strict balanced binary tree , at the same time, it pres...