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

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

1.介紹

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

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

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

2.算法描述

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

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

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

template

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

3.算法思路與過(guò)程

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

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

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

.

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

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

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

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

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

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

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

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

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

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

實(shí)驗(yàn)測(cè)試結(jié)果：

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

圖5 曲線圖

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

5.結(jié)論

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

參考文獻(xiàn)：

[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語(yǔ)言描述[M].北京：人民郵電出版社（英文版第3版），2007.

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

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

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