基于雙鏈表的嚴(yán)格平衡二叉樹建立

王防修1，劉春紅2

(1.武漢輕工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院 湖北 武漢 430023;2.鄂鋼馳久鋼板彈簧有限責(zé)任公司 湖北 鄂州 436000)

摘要：針對目前嚴(yán)格平衡二叉樹的建立需要借助有序順序表來實(shí)現(xiàn)的問題，提出一種無需借助有序順序表也可建立嚴(yán)格平衡二叉樹的算法。為了建立關(guān)鍵字的嚴(yán)格平衡二叉樹，需要首先建立一個(gè)關(guān)鍵字的有序雙鏈表，然后用分治法構(gòu)造嚴(yán)格平衡二叉樹的根節(jié)點(diǎn)和左右子樹。為了驗(yàn)證所建立的二叉樹是嚴(yán)格平衡的，還提出了判斷一棵二叉樹嚴(yán)格平衡的兩種檢驗(yàn)方法。其中，嚴(yán)格平衡二叉樹的定義法是一種直接判斷法，而平均查找長度法可以間接判斷一棵二叉樹的平衡性。算例仿真表明，無需借助有序順序表也可建立一棵嚴(yán)格平衡二叉樹。

關(guān)鍵詞：升序雙鏈表；嚴(yán)格平衡二叉樹；精確查詢；二分查找；查找效率

收稿日期：2015-04-20.

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

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(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引言

在信息化時(shí)代，人們越來越多地通過網(wǎng)絡(luò)來獲得自己需要的信息。統(tǒng)計(jì)表明，人們在網(wǎng)上95%以上的工作都是在查詢。因此，如何快速地搜索到用戶需要的信息是用戶最為關(guān)心的。查詢分模糊查詢[1]和精確查詢，其中模糊查詢出現(xiàn)的結(jié)果不唯一，需要用戶在查詢的結(jié)果中進(jìn)一步手工篩選出自己需要的信息。當(dāng)這種結(jié)果很多時(shí)，用戶要從中手工選擇是很費(fèi)時(shí)的。比如用搜索引擎查詢就是一種模糊查詢，當(dāng)用百度或谷歌等常用搜索引擎進(jìn)行查詢時(shí)，就會(huì)出現(xiàn)大量與用戶輸入的關(guān)鍵詞相關(guān)的信息，用戶從中選擇自己需要的信息往往不是一件容易的事情。雖然日常生活中的大多數(shù)查詢是模糊查詢，但有時(shí)必須是精確查詢，比如查詢高考成績、銀行帳戶等。事實(shí)上，只要涉及隱私保護(hù)[2]的查詢，都必須是精確查詢。由于精確查詢是一對一查詢，即查詢的結(jié)果要么不存在，如果存在，其結(jié)果一定是唯一的。因此，在模糊查詢的結(jié)果中進(jìn)一步使用精確查詢，則可以提高整個(gè)查詢的速度，這對提高網(wǎng)絡(luò)服務(wù)水平具有現(xiàn)實(shí)意義。

2利用雙鏈表建立嚴(yán)格平衡二叉樹

作為一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),雙鏈表不要求各節(jié)點(diǎn)的地址必須連續(xù),這使得它可以最大限度地使用內(nèi)存空閑區(qū)域.與二叉樹相比,它也有兩個(gè)指針域,不同的是一個(gè)指向前驅(qū)節(jié)點(diǎn),另一個(gè)指向后繼節(jié)點(diǎn).如果能設(shè)計(jì)一個(gè)算法, 使得該算法可以改變?nèi)魏我粋€(gè)節(jié)點(diǎn)的兩個(gè)指針域,一個(gè)指向左孩子節(jié)點(diǎn),另一個(gè)指向右孩子節(jié)點(diǎn),并且建立的二叉樹是嚴(yán)格平衡的,則雙鏈表就被轉(zhuǎn)化為嚴(yán)格平衡二叉樹。

由于嚴(yán)格平衡二叉樹的中序遍歷是一個(gè)關(guān)鍵字的有序序列,故需要先建立一個(gè)關(guān)于關(guān)鍵字的有序雙鏈表，然后用二分法遞歸地將雙鏈表轉(zhuǎn)化為一個(gè)嚴(yán)格平衡二叉樹。

為方便算法的描述，不妨做一些約定：(1)雙鏈表的每個(gè)節(jié)點(diǎn)由左孩子指針、關(guān)鍵字和右孩子指針三部分組成；(2)如果用p表示雙鏈表的一個(gè)節(jié)點(diǎn)，則p.lchild和p.rchild分別表示p的左孩子指針和右孩子指針，而p.key表示該節(jié)點(diǎn)保存的關(guān)鍵字；(3)雖然雙鏈表可以是降序的，但此處建立的雙鏈表要求是升序的。

2.1升序雙鏈表的建立

由于升序雙鏈表的關(guān)鍵字只能通過鍵盤或外部數(shù)據(jù)文件提供，為方便起見，要求關(guān)鍵字必須從外部文件讀入。在建立升序雙鏈表的過程中需要對關(guān)鍵字排序，使得最終得到的是一個(gè)關(guān)于關(guān)鍵字的升序雙鏈表。具體做法是，每從外部文件讀入一個(gè)關(guān)鍵字，除了需要為其申請一個(gè)節(jié)點(diǎn)的內(nèi)存空間外，還需要找出該節(jié)點(diǎn)在一個(gè)已知升序雙鏈表的具體插入位置，使得插入該節(jié)點(diǎn)后的雙鏈表仍然是一個(gè)升序雙鏈表。因?yàn)殡p鏈表的插入位置不外乎表首、表中和表尾這三個(gè)位置中的一個(gè)，而在雙鏈表中插入某個(gè)節(jié)點(diǎn)時(shí)，為了排除表首插入的可能，不妨先建立一個(gè)帶頭節(jié)點(diǎn)的雙鏈表，這樣就不存在節(jié)點(diǎn)的表首插入，只剩下表中和表尾兩種插入情形。當(dāng)雙鏈表建立完成后，再刪除頭節(jié)點(diǎn)?？傊羞@一切都是為了能夠方便地建立一個(gè)升序雙鏈表。

下面給出建立升序雙鏈表的算法步驟如下。

步0申請雙鏈表的頭節(jié)點(diǎn)head。令head.lchild=head.rchild=∧。

步1從外部數(shù)據(jù)文件讀一個(gè)關(guān)鍵字x，并為該關(guān)鍵字申請一個(gè)新節(jié)點(diǎn)q，使得q.key=x。

步2找出節(jié)點(diǎn)q在雙鏈表head中的插入位置。令s=head和p=s.rchild，反復(fù)執(zhí)行過程s=p和p=p.rchild，直到p=∧或x

步3新節(jié)點(diǎn)q的插入。如果p=∧，則在表尾節(jié)點(diǎn)s后插入新節(jié)點(diǎn)q；否則，在節(jié)點(diǎn)s和節(jié)點(diǎn)p之間插入節(jié)點(diǎn)q。

步4如果外部文件數(shù)據(jù)讀完，則轉(zhuǎn)步5；否則，轉(zhuǎn)步1。

步5刪除頭節(jié)點(diǎn)head，使head指示下一個(gè)節(jié)點(diǎn)，即head=head.rchild和head.lchild=∧。

依照上述算法，即可建立一個(gè)關(guān)鍵字的升序雙鏈表。需要說明的是，對于雙鏈表中的任何一個(gè)節(jié)點(diǎn)p，其前驅(qū)節(jié)點(diǎn)是p.lchild和后繼節(jié)點(diǎn)是p.rchild.

2.2建立嚴(yán)格平衡二叉樹的分治法

在建立了雙鏈表之后，接下來就是如何通過該雙鏈表建立一棵嚴(yán)格平衡二叉樹的問題。要建立一棵二叉樹，首先建立該二叉樹的根節(jié)點(diǎn)，然后建立該根節(jié)點(diǎn)的左子樹和右子樹。然而，其左子樹和右子樹的建立同樣面臨根節(jié)點(diǎn)和左右子樹的建立問題。因此，這是一個(gè)具有遞歸子結(jié)構(gòu)的過程，即：(1)建立根節(jié)點(diǎn)；(2)遞歸建立根節(jié)點(diǎn)的左子樹；(3)遞歸建立根節(jié)點(diǎn)的右子樹。總之，需要應(yīng)用分治法將雙鏈表轉(zhuǎn)化為嚴(yán)格平衡二叉樹。

設(shè)t=f(p,q)是一個(gè)將升序雙鏈表轉(zhuǎn)化為嚴(yán)格平衡二叉樹的函數(shù)，其中p，q分別是雙鏈表的表首指針和表尾指針，而t是嚴(yán)格平衡二叉樹的根節(jié)點(diǎn)。因此，二元函數(shù)f的內(nèi)部設(shè)計(jì)是成功建立嚴(yán)格平衡二叉樹的關(guān)鍵。

首先，二叉樹的根節(jié)點(diǎn)t是雙鏈表中的中間節(jié)點(diǎn)，也就是說，該節(jié)點(diǎn)距離表首節(jié)點(diǎn)和表尾節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)之差最多不會(huì)超過1。如果用g(p,q)表示雙鏈表p和q之間的節(jié)點(diǎn)數(shù)，則

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

(1)

其次，根節(jié)點(diǎn)t的左右孩子的確立問題。t的左孩子節(jié)點(diǎn)是p到t.lchild的雙鏈表的中間節(jié)點(diǎn)，即t.lchild=f(p,t.lchild)，而t的右孩子節(jié)點(diǎn)是t.rchild和q的雙鏈表的中間節(jié)點(diǎn)，即t.rchild=f(t.rchild,q)。

因此，用分治法建立嚴(yán)格平衡二叉樹t=f(p,q)的步驟如下。

步1令p=head和q=head，然后重復(fù)進(jìn)行過程q=q.rchild，直到q.rchild=∧為止。最終p指向雙鏈表的表首，而q指向雙鏈表的表尾。

步2確定嚴(yán)格平衡二叉樹的根節(jié)點(diǎn)。令l=p和r=q，反復(fù)進(jìn)行l(wèi)=l.rchild和r=r.lchild，直到l.key>r.key為止，此時(shí)的r就是根節(jié)點(diǎn)。

步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指向嚴(yán)格平衡二叉樹的根節(jié)點(diǎn)。

需要指出的是，當(dāng)關(guān)鍵字的個(gè)數(shù)是奇數(shù)時(shí)，算法搜索的結(jié)果是l=r。此外，此處采用r作為二叉樹的根節(jié)點(diǎn)，其實(shí)也可以用l做為二叉樹的根節(jié)點(diǎn)。它們的不同在于：前者會(huì)出現(xiàn)一些節(jié)點(diǎn)的左子樹節(jié)點(diǎn)數(shù)比右子樹節(jié)點(diǎn)數(shù)少一個(gè)的情形，而后者會(huì)出現(xiàn)一些節(jié)點(diǎn)的左子樹節(jié)點(diǎn)數(shù)比右子樹節(jié)點(diǎn)數(shù)多一個(gè)的情況。對于嚴(yán)格平衡二叉樹中的任何一個(gè)節(jié)點(diǎn)p，其左孩子節(jié)點(diǎn)是p.lchild和右孩子節(jié)點(diǎn)是p.rchild.而在雙鏈表中，p.lchild是p的前驅(qū)，p.rchild是p的后繼。

3嚴(yán)格平衡二叉樹的檢驗(yàn)

有兩種方法可以對建立的二叉樹是否嚴(yán)格平衡進(jìn)行檢驗(yàn)，它們是嚴(yán)格平衡二叉樹的定義法和平均查找效率法。

3.1嚴(yán)格平衡二叉樹結(jié)果的顯示

從平衡二叉樹中的任何一個(gè)節(jié)點(diǎn)出發(fā)，可以知道它是否存在左右孩子節(jié)點(diǎn)，以及如果存在，還可以求出孩子節(jié)點(diǎn)。然而，僅僅知道孩子節(jié)點(diǎn)信息是不夠的，還必須知道該節(jié)點(diǎn)的雙親節(jié)點(diǎn)。對任何一棵二叉樹而言，只有根節(jié)點(diǎn)沒有雙親節(jié)點(diǎn)，只有葉子節(jié)點(diǎn)沒有孩子節(jié)點(diǎn)，至于其它中間節(jié)點(diǎn)，它只有唯一的雙親節(jié)點(diǎn)以及最多兩個(gè)孩子節(jié)點(diǎn)。

為了既能顯示任何節(jié)點(diǎn)和它的孩子節(jié)點(diǎn)，又能顯示它的雙親節(jié)點(diǎn)，不妨在每個(gè)節(jié)點(diǎn)中增加存儲(chǔ)雙親節(jié)點(diǎn)的指針域。這樣，當(dāng)在每個(gè)節(jié)點(diǎn)中增加一個(gè)雙親指針parent后，可以在二叉樹遍歷過程中確定該指針的值。

由于層次遍歷對雙親指針parent的建立比較方便，故此處不妨用它來搜索二叉樹中各節(jié)點(diǎn)之間的關(guān)系。

二叉樹的層次遍歷算法步驟描述如下。

步0令t.parent=∧，表示t是無雙親的根節(jié)點(diǎn)。讓t入隊(duì)。

步1一個(gè)元素p出隊(duì)，輸出p.key。

步2如果p.parent=∧，則顯示p的雙親為空；否則顯示p的雙親。

步3如果p.lchild=∧，則顯示p的左孩子為空；否則令p.lchild.parent=p，并且讓p.lchild入隊(duì)。

步4如果p.rchild=∧，則顯示p的右孩子為空；否則令p.rchild.parent=p，并且讓p.rchild入隊(duì)。

步5如果隊(duì)列非空，則轉(zhuǎn)步1；否則層次遍歷結(jié)束。

3.2嚴(yán)格平衡二叉樹直接檢驗(yàn)法

所謂嚴(yán)格平衡二叉樹的直接檢驗(yàn)法，就是從二叉樹的任何一個(gè)節(jié)點(diǎn)出發(fā)，其左子樹的節(jié)點(diǎn)數(shù)和右子樹的節(jié)點(diǎn)數(shù)之差的絕對值不會(huì)超過1。如果有某個(gè)節(jié)點(diǎn)的左子樹的節(jié)點(diǎn)數(shù)和右子樹的節(jié)點(diǎn)數(shù)之差的絕對值超過1，則它不是嚴(yán)格平衡二叉樹。因此，只有一棵二叉樹的所有節(jié)點(diǎn)都滿足式(1)，它才是嚴(yán)格平衡的。

至于二叉樹中所有節(jié)點(diǎn)的左右子樹的孩子節(jié)點(diǎn)數(shù)的計(jì)算，可以是先序遍歷、中序遍歷、后序遍歷和層次遍歷中的任何一個(gè)。

在遍歷的過程中，如果有某個(gè)節(jié)點(diǎn)的左子樹的節(jié)點(diǎn)數(shù)和右子樹的節(jié)點(diǎn)數(shù)之差的絕對值超過1，則該二叉樹就不可能是嚴(yán)格平衡二叉樹,就不需要繼續(xù)遍歷下一個(gè)節(jié)點(diǎn)；否則，它就是嚴(yán)格平衡二叉樹。

3.3平均查找效率間接檢驗(yàn)法

設(shè)t是由n個(gè)關(guān)鍵字xi(i=1,2,…,n)構(gòu)成的嚴(yán)格平衡二叉樹，ci是在二叉樹t中查找xi的比較次數(shù)，則t的平均查找長度為

(2)

如果ave(t)等于二分查找的平均查找長度，則t是嚴(yán)格平衡二叉樹；否則，t就不是嚴(yán)格平衡二叉樹。

4算法仿真及分析

本算法使用VC6.0作為仿真工具，在CPU為3.2 GHz和內(nèi)存為1.86 GB的個(gè)人臺(tái)式電腦上完成仿真。

算例1已知關(guān)鍵字序列Key={23,5,3,8 ,56,43 ,76 ,34,65 ,15 ,70}。求由該整型關(guān)鍵字構(gòu)成的嚴(yán)格平衡二叉樹。

首先，將該整型數(shù)據(jù)序列保存在一個(gè)外部數(shù)據(jù)文件中，然后由算法2.1建立一個(gè)升序雙鏈表，最后由算法2.2將該升序雙鏈表轉(zhuǎn)化為一棵嚴(yán)格平衡二叉樹。

由算法3.1可知該二叉樹的樹結(jié)構(gòu)如表1所示。

表1二叉樹中各節(jié)點(diǎn)之間的關(guān)系

節(jié)點(diǎn)雙親左孩子右孩子34空8658343156534437038∧5158∧234365∧567065∧7653∧∧2315∧∧5643∧∧7670∧∧

根據(jù)表1即可畫出對應(yīng)的二叉樹如圖1所示。

圖1　嚴(yán)格平衡二叉樹

用算法3.2對建立的二叉樹進(jìn)行直接檢驗(yàn)的結(jié)果如表2所示。

表2算法3.2的計(jì)算結(jié)果

節(jié)點(diǎn)左子樹節(jié)點(diǎn)數(shù)右子樹節(jié)點(diǎn)數(shù)差值34550822065220301-11501-14301-17001-15000230005600076000

在表2中，差值=左子樹節(jié)點(diǎn)數(shù)-右子樹節(jié)點(diǎn)數(shù)。從表中可以發(fā)現(xiàn)，由于采用r作為二叉樹的根節(jié)點(diǎn)，故出現(xiàn)一些節(jié)點(diǎn)的左子樹節(jié)點(diǎn)數(shù)比右子樹節(jié)點(diǎn)數(shù)少一個(gè)的情形。顯然，該二叉樹是一棵嚴(yán)格平衡二叉樹。

用算法3.3計(jì)算該二叉樹的平均查找長度，得到的結(jié)果是3，而該結(jié)果與二分查找的平均查找長度相等。因此，該結(jié)果間接說明此處建立的二叉樹是一棵嚴(yán)格平衡二插樹。

5結(jié)束語

筆者在此提出了一種基于雙鏈表的構(gòu)造嚴(yán)格平衡二叉樹的算法。該算法首先建立一個(gè)關(guān)鍵字的升序雙鏈表，然后用分治法將升序雙鏈表轉(zhuǎn)化為一棵嚴(yán)格平衡二叉樹。為了檢驗(yàn)算法的正確性，提出了判斷一棵二叉樹是否嚴(yán)格平衡的兩種方法，它們分別是嚴(yán)格平衡二叉樹的定義法的直接判斷法和平均查找長度法的間接判斷法。與有序順序表相比，雖然嚴(yán)格平衡二叉樹的每個(gè)節(jié)點(diǎn)會(huì)占用額外的內(nèi)存空間來存儲(chǔ)左右孩子指針，但它不要求節(jié)點(diǎn)間的物理地址必須連續(xù)，這就使得它可以充分利用內(nèi)存碎片來存儲(chǔ)關(guān)鍵字?？傊?，嚴(yán)格平衡二叉樹的查找和有序順序表的二分法查找具有相同的查找效率，但嚴(yán)格平衡二叉樹可以使內(nèi)存空間得到充分利用，而升序順序表不能使用比它空間小的內(nèi)存碎片。算法仿真表明，筆者在本文中所做的算法無需借助有序順序表也可建立嚴(yán)格平衡二叉樹，從而節(jié)省了有序順序所需要的額外內(nèi)存空間。筆者采用的是遞歸算法將一個(gè)升序雙鏈表轉(zhuǎn)化為一棵嚴(yán)格平衡二叉樹，而將一個(gè)升序雙鏈表轉(zhuǎn)化為一棵嚴(yán)格平衡二叉樹的非遞歸算法將是今后研究方向。

參考文獻(xiàn)：

[1]郭猛,胡秀香,邵國金. 混合語義相似度計(jì)算優(yōu)化模糊查詢的智能信檢索算法[J]. 科學(xué)技術(shù)與工程, 2014,14(23)：1671-1815.

[2]熊平,朱天清,金大衛(wèi). 一種面向決策樹構(gòu)建的差分隱私保護(hù)算法[J]. 計(jì)算機(jī)應(yīng)用研究,2014，31(10)：3108-3112.

[3]王剛. 基于二分查找法實(shí)現(xiàn)對館藏書目的查重處理[J] 黑龍江教育學(xué)院學(xué)報(bào), 2008,27(4)：159-160.

[4]孫曉輝,王勁林,陳曉.實(shí)時(shí)系統(tǒng)中的動(dòng)態(tài)內(nèi)存分配算法[j] .計(jì)算機(jī)工程 ,2008,34(8): 80-81,84.

[5]譚浩強(qiáng).實(shí)用數(shù)據(jù)結(jié)構(gòu)[M].北 京: 清華大學(xué)出版社,2008．

[6]岑崗,周炳生.嚴(yán)格平衡二叉排序樹及其構(gòu)造[J].計(jì)算機(jī)工程與應(yīng)用 ,2005 (13): 57-60．

[7]胡云,黃震宇.一種快速構(gòu)建平衡二叉搜索樹的算法[J] 大慶師范學(xué)院學(xué)報(bào), 2008，28(2)：20-23.

[8]王防修,周康. 一種構(gòu)建嚴(yán)格平衡二叉搜索樹的非遞歸算法[J]. 武漢工業(yè)學(xué)院學(xué)報(bào), 2013,32(4)：32-34,43.