基于双链表的严格平衡二叉树建立

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

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

In view of the problem of the previous strict balanced binary tree needing a orderly sequence table to create,this paper proposes an algorithm which can also establish a strict balanced binary tree without the orderly sequence 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 presents two test methods to judge balance of the binary tree established. Among them,It is a kind of direct judgment method for the definition of strict balanced binary tree method,and the average search length method can indirectly judge whether or not a binary tree is balanced. An examples of simulation shows thats a strict balanced binary tree can also be established without the orderly sequence table.