【摘 要】在很多應(yīng)用中，需要對完全二叉樹結(jié)點位置進行調(diào)整，使該數(shù)據(jù)集合具有堆的性質(zhì)?，F(xiàn)經(jīng)過實驗提出一種改進算法，利用優(yōu)先級隊列頗似隊列（刪除最早的數(shù)據(jù)）和棧（刪除最新的數(shù)據(jù)）特性轉(zhuǎn)存二叉樹結(jié)構(gòu)的結(jié)點元素，存儲在線性表中。直接調(diào)用下滑調(diào)整算法操作線性表，使之具有堆特性，后續(xù)轉(zhuǎn)回二叉樹。

【關(guān)鍵詞】完全二叉樹；下滑調(diào)整；堆調(diào)整；線性表操作

1.介紹

具有優(yōu)先級隊列[1]的數(shù)據(jù)集合在實際應(yīng)用中為各種搜索帶來便利。搜索是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)元素，是數(shù)據(jù)處理最常見的一種運算。對于不同方式組織起來的搜索結(jié)構(gòu)，相應(yīng)的搜索方法也不同。往往搜索結(jié)構(gòu)的性質(zhì)也影響著搜索速度。

對于以完全二叉樹[1，2]結(jié)構(gòu)形式存在的數(shù)據(jù)集合，在搜索前進行某種調(diào)整后，使數(shù)據(jù)集合具有堆[2，3]的性質(zhì)，可以提高搜索速度。調(diào)整的方法關(guān)系到整個處理過程的效率問題。

這里借用線性表[1，3]對元素位置進行調(diào)整，再轉(zhuǎn)換為原來的非線性表結(jié)構(gòu)，以此取代最初的數(shù)據(jù)集合。

2.算法描述

將給定的以鏈表結(jié)構(gòu)存取的完全二叉樹轉(zhuǎn)化為以數(shù)組結(jié)構(gòu)存取的完全二叉樹，對數(shù)組元素位置進行調(diào)整，使得該數(shù)組集合具有堆性質(zhì)，最后依此數(shù)組來新建具有堆性質(zhì)的完全二叉樹。

算法中用到相關(guān)變量和數(shù)據(jù)結(jié)構(gòu)：

Stack stack；//全局變量棧stack，用來作為中間記錄載體

template

struct TreeNode//二叉樹結(jié)點數(shù)據(jù)結(jié)構(gòu)

3.算法思路與過程

整個調(diào)整過程分為三步。首先，完全二叉樹的數(shù)組表示：將鏈表結(jié)構(gòu)的完全二叉樹轉(zhuǎn)化為數(shù)組結(jié)構(gòu)完全二叉樹。其次，數(shù)組的堆調(diào)整[3]：對數(shù)組heap[]進行下滑調(diào)整使得數(shù)組heap[]的數(shù)據(jù)集合具有堆的性質(zhì)。最后，完全二叉樹的創(chuàng)建：依heap[]數(shù)組創(chuàng)建完全二叉樹來替代原來的完全二叉樹。圖1為該調(diào)整算法分三步處理的圖例。

圖1 借用線性變操作流程處理

完全二叉樹的數(shù)組表示：基本思想：將n個結(jié)點的完全二叉樹，自頂向下，同一層次自左向右連續(xù)給結(jié)點編號0，1，2，3，......，n.，借助隊列作為中間載體，然后按此編號將樹中個結(jié)點順序地放在數(shù)組heap[]中，即heap[i]為編號i的結(jié)點。圖2為該操作的算法思想的流程圖。

.

圖2 二叉樹結(jié)點元素線性表轉(zhuǎn)存

數(shù)組的堆調(diào)整：依次以數(shù)組heap[]的每個元素為調(diào)整對象，使得調(diào)整后的數(shù)組heap[]滿足heap[i]≤heap[2i+1]且heap[i]≤heap[2i+2]（或者heap[i]≥k[2i+1]且k[i]≥k[2i+2]）條件。調(diào)整的過程分為，對每個結(jié)點的下滑調(diào)整和整體堆化。下列代碼實現(xiàn)某一個結(jié)點的下滑調(diào)整。同時由于在對每一個結(jié)點進行下滑調(diào)整時，他的子樹都已經(jīng)是調(diào)整好的具有堆性質(zhì)的樹，圖3為從下至上，在每一個結(jié)點進行下滑調(diào)整后的操作思路。

圖3 線性表大半個元素的下滑調(diào)整

任意給定堆H0和H1，以及結(jié)點p，為得到堆H3，只需要將結(jié)點R0和R1當(dāng)作p的孩子，然后對p進行下滑調(diào)整。

某個結(jié)點的下滑調(diào)整的算法代碼實現(xiàn)：

完全二叉樹的創(chuàng)建：該操作實際是上述完全二叉樹的數(shù)組表示的逆操作。即以數(shù)組heap[]中的各元素為結(jié)點來創(chuàng)建一個以鏈表表示的完全二叉樹，且當(dāng)給該二叉樹進行自頂向下，同一層次自左向右連續(xù)編號后，編號i的結(jié)點為數(shù)組元素heap[i]。圖4為該操作的算法思想的流程圖。

圖4 堆性質(zhì)的二叉樹結(jié)構(gòu)轉(zhuǎn)化

4.算法復(fù)雜度和測試結(jié)果

空間復(fù)雜度：該算法用到的隊列和數(shù)組的空間大小之和：S（3└n/2┘），單位為sizeof（TreeNode）。

時間復(fù)雜度：在對完全二叉樹元素進行數(shù)組表示時進行了n次的進棧操作，進棧操作結(jié)束后再執(zhí)行了n次的出棧操作來轉(zhuǎn)存到數(shù)組中，二叉樹的轉(zhuǎn)存操作時間復(fù)雜度為T（2n）。調(diào)用下滑調(diào)整算法時，while循環(huán)的次數(shù)最大為樹的深度減1，所以數(shù)組的下滑調(diào)整算法的時間復(fù)雜度為T（log2n）。再依次操作該數(shù)組每一個元素，調(diào)用了n次數(shù)組的下滑調(diào)整算法?；跀?shù)組的堆調(diào)整算法復(fù)雜度整體的時間復(fù)雜度為T（nlog2n+2n）。

實驗測試結(jié)果：

在測試實驗中，每次對相同完全二叉樹用兩種方法進行堆調(diào)整驗證，記錄了算法執(zhí)行時間Time下面根據(jù)記錄的數(shù)據(jù)，繪制出曲線圖（如圖5）進行觀察對比。

圖5 曲線圖

由圖5曲線圖，可以明顯得出結(jié)論：隨著二叉樹結(jié)點數(shù)目的增多，堆調(diào)整的處理速率在增加。由于該轉(zhuǎn)換過程涉及到兩處組織結(jié)構(gòu)的轉(zhuǎn)換，導(dǎo)致在數(shù)據(jù)量龐大時出現(xiàn)延時，這也是本算法研究的最大缺點。

5.結(jié)論

本文通過以鏈表結(jié)構(gòu)的完全二叉樹為處理對象，形式地給出了借用線性表作為中間載體，再轉(zhuǎn)會為完全二叉樹結(jié)構(gòu)。該算法在對鏈表結(jié)構(gòu)的完全二叉樹的堆調(diào)整算法時，要經(jīng)過多系組織結(jié)構(gòu)的轉(zhuǎn)換在這樣的情況下，當(dāng)數(shù)據(jù)量特別大的時候肯定會出現(xiàn)延時情況。在后續(xù)階段我們將對處理龐大數(shù)據(jù)量的二叉樹結(jié)構(gòu)進行算法研究，解決延時問題。

參考文獻：

[1]Glenn W Rowe：Introduction to Data Structures and Algorithms with C++，Prentice-HallEurope（1997）.

[2][美]Mark Allen Weiss.數(shù)據(jù)結(jié)構(gòu)與算法分析：Java語言描述[M].北京：人民郵電出版社（英文版第3版），2007.

[3][中]殷人昆數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++語言描述）[M].北京：清華大學(xué)出版社（第二版）.

本文屬基于青海大學(xué)2012年課程建設(shè)項目（KC-12-2-3）“數(shù)據(jù)結(jié)構(gòu)與算法青海大學(xué)教育教學(xué)研究項目”。

作者簡介：胡媛，女，現(xiàn)就讀于青海大學(xué)計算機科學(xué)與技術(shù)系，研究方向：計算機技術(shù)與應(yīng)用。