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

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

王防修1，刘春红2

(1.武汉轻工大学 数学与计算机学院 湖北 武汉 430023;2.鄂钢驰久钢板弹簧有限责任公司 湖北 鄂州 436000)

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

关键词：升序双链表；严格平衡二叉树；精确查询；二分查找；查找效率

收稿日期：2015-04-20.

作者简介：王防修(1973-)，男，副教授，E-mail:wfx323@126.com.

基金项目：国家自然科学基金资助项目(61179032).

文章编号：2095-7386(2015)03-0075-05

DOI:10.3969/j.issn.2095-7386.2015.03.016

中图分类号：TP 391

A strict balanced binary tree established based on

the double linked list

WANGFang-xiu1,LIUChun-hong2

(1.School of Mathematics and Computer Science,Wuhan Polytechnic University, Wuhan 430023,China;

2. Ezhou Iron and Steel Plate Spring Co., Ltd., Ezhou 436000),China

Abstract：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 .

Key words：ascending double linked list; strict balanced binary tree; precise query; binary search; search efficiency

1引言

在信息化时代，人们越来越多地通过网络来获得自己需要的信息。统计表明，人们在网上95%以上的工作都是在查询。因此，如何快速地搜索到用户需要的信息是用户最为关心的。查询分模糊查询[1]和精确查询，其中模糊查询出现的结果不唯一，需要用户在查询的结果中进一步手工筛选出自己需要的信息。当这种结果很多时，用户要从中手工选择是很费时的。比如用搜索引擎查询就是一种模糊查询，当用百度或谷歌等常用搜索引擎进行查询时，就会出现大量与用户输入的关键词相关的信息，用户从中选择自己需要的信息往往不是一件容易的事情。虽然日常生活中的大多数查询是模糊查询，但有时必须是精确查询，比如查询高考成绩、银行帐户等。事实上，只要涉及隐私保护[2]的查询，都必须是精确查询。由于精确查询是一对一查询，即查询的结果要么不存在，如果存在，其结果一定是唯一的。因此，在模糊查询的结果中进一步使用精确查询，则可以提高整个查询的速度，这对提高网络服务水平具有现实意义。

2利用双链表建立严格平衡二叉树

作为一种链式存储结构,双链表不要求各节点的地址必须连续,这使得它可以最大限度地使用内存空闲区域.与二叉树相比,它也有两个指针域,不同的是一个指向前驱节点,另一个指向后继节点.如果能设计一个算法, 使得该算法可以改变任何一个节点的两个指针域,一个指向左孩子节点,另一个指向右孩子节点,并且建立的二叉树是严格平衡的,则双链表就被转化为严格平衡二叉树。

由于严格平衡二叉树的中序遍历是一个关键字的有序序列,故需要先建立一个关于关键字的有序双链表，然后用二分法递归地将双链表转化为一个严格平衡二叉树。

为方便算法的描述，不妨做一些约定：(1)双链表的每个节点由左孩子指针、关键字和右孩子指针三部分组成；(2)如果用p表示双链表的一个节点，则p.lchild和p.rchild分别表示p的左孩子指针和右孩子指针，而p.key表示该节点保存的关键字；(3)虽然双链表可以是降序的，但此处建立的双链表要求是升序的。

2.1升序双链表的建立

由于升序双链表的关键字只能通过键盘或外部数据文件提供，为方便起见，要求关键字必须从外部文件读入。在建立升序双链表的过程中需要对关键字排序，使得最终得到的是一个关于关键字的升序双链表。具体做法是，每从外部文件读入一个关键字，除了需要为其申请一个节点的内存空间外，还需要找出该节点在一个已知升序双链表的具体插入位置，使得插入该节点后的双链表仍然是一个升序双链表。因为双链表的插入位置不外乎表首、表中和表尾这三个位置中的一个，而在双链表中插入某个节点时，为了排除表首插入的可能，不妨先建立一个带头节点的双链表，这样就不存在节点的表首插入，只剩下表中和表尾两种插入情形。当双链表建立完成后，再删除头节点。总之，所有这一切都是为了能够方便地建立一个升序双链表。

下面给出建立升序双链表的算法步骤如下。

步0申请双链表的头节点head。令head.lchild=head.rchild=∧。

步1从外部数据文件读一个关键字x，并为该关键字申请一个新节点q，使得q.key=x。

步2找出节点q在双链表head中的插入位置。令s=head和p=s.rchild，反复执行过程s=p和p=p.rchild，直到p=∧或x

步3新节点q的插入。如果p=∧，则在表尾节点s后插入新节点q；否则，在节点s和节点p之间插入节点q。

步4如果外部文件数据读完，则转步5；否则，转步1。

步5删除头节点head，使head指示下一个节点，即head=head.rchild和head.lchild=∧。

依照上述算法，即可建立一个关键字的升序双链表。需要说明的是，对于双链表中的任何一个节点p，其前驱节点是p.lchild和后继节点是p.rchild.

2.2建立严格平衡二叉树的分治法

在建立了双链表之后，接下来就是如何通过该双链表建立一棵严格平衡二叉树的问题。要建立一棵二叉树，首先建立该二叉树的根节点，然后建立该根节点的左子树和右子树。然而，其左子树和右子树的建立同样面临根节点和左右子树的建立问题。因此，这是一个具有递归子结构的过程，即：(1)建立根节点；(2)递归建立根节点的左子树；(3)递归建立根节点的右子树。总之，需要应用分治法将双链表转化为严格平衡二叉树。

设t=f(p,q)是一个将升序双链表转化为严格平衡二叉树的函数，其中p，q分别是双链表的表首指针和表尾指针，而t是严格平衡二叉树的根节点。因此，二元函数f的内部设计是成功建立严格平衡二叉树的关键。

首先，二叉树的根节点t是双链表中的中间节点，也就是说，该节点距离表首节点和表尾节点的节点数之差最多不会超过1。如果用g(p,q)表示双链表p和q之间的节点数，则

|g(p,t)-g(t,q)|≤1.

(1)

其次，根节点t的左右孩子的确立问题。t的左孩子节点是p到t.lchild的双链表的中间节点，即t.lchild=f(p,t.lchild)，而t的右孩子节点是t.rchild和q的双链表的中间节点，即t.rchild=f(t.rchild,q)。

因此，用分治法建立严格平衡二叉树t=f(p,q)的步骤如下。

步1令p=head和q=head，然后重复进行过程q=q.rchild，直到q.rchild=∧为止。最终p指向双链表的表首，而q指向双链表的表尾。

步2确定严格平衡二叉树的根节点。令l=p和r=q，反复进行l=l.rchild和r=r.lchild，直到l.key>r.key为止，此时的r就是根节点。

步3递归建立左子树。如果r.lchild≠∧，则令r.lchild.rchild=∧和r.lchild=g(p,r.lchild)。

步4递归建立右子树。如果r.rchild≠∧，则令r.rchild.lchild=∧和r.rchild=g(r.rchild,q)。

步5令t=r，使得t指向严格平衡二叉树的根节点。

需要指出的是，当关键字的个数是奇数时，算法搜索的结果是l=r。此外，此处采用r作为二叉树的根节点，其实也可以用l做为二叉树的根节点。它们的不同在于：前者会出现一些节点的左子树节点数比右子树节点数少一个的情形，而后者会出现一些节点的左子树节点数比右子树节点数多一个的情况。对于严格平衡二叉树中的任何一个节点p，其左孩子节点是p.lchild和右孩子节点是p.rchild.而在双链表中，p.lchild是p的前驱，p.rchild是p的后继。

3严格平衡二叉树的检验

有两种方法可以对建立的二叉树是否严格平衡进行检验，它们是严格平衡二叉树的定义法和平均查找效率法。

3.1严格平衡二叉树结果的显示

从平衡二叉树中的任何一个节点出发，可以知道它是否存在左右孩子节点，以及如果存在，还可以求出孩子节点。然而，仅仅知道孩子节点信息是不够的，还必须知道该节点的双亲节点。对任何一棵二叉树而言，只有根节点没有双亲节点，只有叶子节点没有孩子节点，至于其它中间节点，它只有唯一的双亲节点以及最多两个孩子节点。

为了既能显示任何节点和它的孩子节点，又能显示它的双亲节点，不妨在每个节点中增加存储双亲节点的指针域。这样，当在每个节点中增加一个双亲指针parent后，可以在二叉树遍历过程中确定该指针的值。

由于层次遍历对双亲指针parent的建立比较方便，故此处不妨用它来搜索二叉树中各节点之间的关系。

二叉树的层次遍历算法步骤描述如下。

步0令t.parent=∧，表示t是无双亲的根节点。让t入队。

步1一个元素p出队，输出p.key。

步2如果p.parent=∧，则显示p的双亲为空；否则显示p的双亲。

步3如果p.lchild=∧，则显示p的左孩子为空；否则令p.lchild.parent=p，并且让p.lchild入队。

步4如果p.rchild=∧，则显示p的右孩子为空；否则令p.rchild.parent=p，并且让p.rchild入队。

步5如果队列非空，则转步1；否则层次遍历结束。

3.2严格平衡二叉树直接检验法

所谓严格平衡二叉树的直接检验法，就是从二叉树的任何一个节点出发，其左子树的节点数和右子树的节点数之差的绝对值不会超过1。如果有某个节点的左子树的节点数和右子树的节点数之差的绝对值超过1，则它不是严格平衡二叉树。因此，只有一棵二叉树的所有节点都满足式(1)，它才是严格平衡的。

至于二叉树中所有节点的左右子树的孩子节点数的计算，可以是先序遍历、中序遍历、后序遍历和层次遍历中的任何一个。

在遍历的过程中，如果有某个节点的左子树的节点数和右子树的节点数之差的绝对值超过1，则该二叉树就不可能是严格平衡二叉树,就不需要继续遍历下一个节点；否则，它就是严格平衡二叉树。

3.3平均查找效率间接检验法

设t是由n个关键字xi(i=1,2,…,n)构成的严格平衡二叉树，ci是在二叉树t中查找xi的比较次数，则t的平均查找长度为

(2)

如果ave(t)等于二分查找的平均查找长度，则t是严格平衡二叉树；否则，t就不是严格平衡二叉树。

4算法仿真及分析

本算法使用VC6.0作为仿真工具，在CPU为3.2 GHz和内存为1.86 GB的个人台式电脑上完成仿真。

算例1已知关键字序列Key={23,5,3,8 ,56,43 ,76 ,34,65 ,15 ,70}。求由该整型关键字构成的严格平衡二叉树。

首先，将该整型数据序列保存在一个外部数据文件中，然后由算法2.1建立一个升序双链表，最后由算法2.2将该升序双链表转化为一棵严格平衡二叉树。

由算法3.1可知该二叉树的树结构如表1所示。

表1二叉树中各节点之间的关系

节点双亲左孩子右孩子34空8658343156534437038∧5158∧234365∧567065∧7653∧∧2315∧∧5643∧∧7670∧∧

根据表1即可画出对应的二叉树如图1所示。

图1　严格平衡二叉树

用算法3.2对建立的二叉树进行直接检验的结果如表2所示。

表2算法3.2的计算结果

节点左子树节点数右子树节点数差值34550822065220301-11501-14301-17001-15000230005600076000

在表2中，差值=左子树节点数-右子树节点数。从表中可以发现，由于采用r作为二叉树的根节点，故出现一些节点的左子树节点数比右子树节点数少一个的情形。显然，该二叉树是一棵严格平衡二叉树。

用算法3.3计算该二叉树的平均查找长度，得到的结果是3，而该结果与二分查找的平均查找长度相等。因此，该结果间接说明此处建立的二叉树是一棵严格平衡二插树。

5结束语

笔者在此提出了一种基于双链表的构造严格平衡二叉树的算法。该算法首先建立一个关键字的升序双链表，然后用分治法将升序双链表转化为一棵严格平衡二叉树。为了检验算法的正确性，提出了判断一棵二叉树是否严格平衡的两种方法，它们分别是严格平衡二叉树的定义法的直接判断法和平均查找长度法的间接判断法。与有序顺序表相比，虽然严格平衡二叉树的每个节点会占用额外的内存空间来存储左右孩子指针，但它不要求节点间的物理地址必须连续，这就使得它可以充分利用内存碎片来存储关键字。总之，严格平衡二叉树的查找和有序顺序表的二分法查找具有相同的查找效率，但严格平衡二叉树可以使内存空间得到充分利用，而升序顺序表不能使用比它空间小的内存碎片。算法仿真表明，笔者在本文中所做的算法无需借助有序顺序表也可建立严格平衡二叉树，从而节省了有序顺序所需要的额外内存空间。笔者采用的是递归算法将一个升序双链表转化为一棵严格平衡二叉树，而将一个升序双链表转化为一棵严格平衡二叉树的非递归算法将是今后研究方向。

参考文献：

[1]郭猛,胡秀香,邵国金. 混合语义相似度计算优化模糊查询的智能信检索算法[J]. 科学技术与工程, 2014,14(23)：1671-1815.

[2]熊平,朱天清,金大卫. 一种面向决策树构建的差分隐私保护算法[J]. 计算机应用研究,2014，31(10)：3108-3112.

[3]王刚. 基于二分查找法实现对馆藏书目的查重处理[J] 黑龙江教育学院学报, 2008,27(4)：159-160.

[4]孙晓辉,王劲林,陈晓.实时系统中的动态内存分配算法[j] .计算机工程 ,2008,34(8): 80-81,84.

[5]谭浩强.实用数据结构[M].北 京: 清华大学出版社,2008．

[6]岑岗,周炳生.严格平衡二叉排序树及其构造[J].计算机工程与应用 ,2005 (13): 57-60．

[7]胡云,黄震宇.一种快速构建平衡二叉搜索树的算法[J] 大庆师范学院学报, 2008，28(2)：20-23.

[8]王防修,周康. 一种构建严格平衡二叉搜索树的非递归算法[J]. 武汉工业学院学报, 2013,32(4)：32-34,43.