[科普中國(guó)]-滿二叉樹(shù)

除最后一層無(wú)任何子節(jié)點(diǎn)外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)二叉樹(shù)。

國(guó)內(nèi)教程定義：一個(gè)二叉樹(shù)，如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹(shù)就是滿二叉樹(shù)。也就是說(shuō)，如果一個(gè)二叉樹(shù)的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是(2^k) -1 ，則它就是滿二叉樹(shù)。

國(guó)外(國(guó)際)定義:a binary tree T is full if each node is either a leaf or possesses exactly two childnodes.

大意為：如果一棵二叉樹(shù)的結(jié)點(diǎn)要么是葉子結(jié)點(diǎn)，要么它有兩個(gè)子結(jié)點(diǎn)，這樣的樹(shù)就是滿二叉樹(shù)。(一棵滿二叉樹(shù)的每一個(gè)結(jié)點(diǎn)要么是葉子結(jié)點(diǎn)，要么它有兩個(gè)子結(jié)點(diǎn)，但是反過(guò)來(lái)不成立，因?yàn)橥耆鏄?shù)也滿足這個(gè)要求，但不是滿二叉樹(shù))

定義對(duì)于國(guó)內(nèi)的滿二叉樹(shù)從圖形形態(tài)上看，滿二叉樹(shù)外觀上是一個(gè)三角形。

從數(shù)學(xué)上看，滿二叉樹(shù)的各個(gè)層的結(jié)點(diǎn)數(shù)形成一個(gè)首項(xiàng)為1，公比為2的等比數(shù)列。

因此由等比數(shù)列的公式，滿二叉樹(shù)滿足如下性質(zhì)。

1、一個(gè)層數(shù)為k 的滿二叉樹(shù)總結(jié)點(diǎn)數(shù)為：。因此滿二叉樹(shù)

的結(jié)點(diǎn)樹(shù)一定是奇數(shù)個(gè)。

2、第i層上的結(jié)點(diǎn)數(shù)為：

3、一個(gè)層數(shù)為k的滿二叉樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)（也就是最后一層）：

對(duì)于國(guó)外的滿二叉樹(shù)滿二叉樹(shù)的結(jié)點(diǎn)要么是葉子結(jié)點(diǎn)，度為0，要么是度為2的結(jié)點(diǎn)，不存在度為1的結(jié)點(diǎn)。

因此，右圖中這個(gè)二叉樹(shù)也是滿二叉樹(shù)。但是按照國(guó)內(nèi)的定義，它卻不是滿二叉樹(shù)。

美國(guó)以及國(guó)際上所定義的滿二叉樹(shù)，即full binary tree,和國(guó)內(nèi)的定義不同，美國(guó)NIST給出的定義為：A binary tree in which each node has exactly zero or two children. In other words, every node is either a leaf or has two children. For efficiency, any Huffman coding is a full binary tree.

滿二叉樹(shù)的任意節(jié)點(diǎn)，要么度為0，要么度為2.換個(gè)說(shuō)法即要么為葉子結(jié)點(diǎn)，要么同時(shí)具有左右孩子?；舴蚵鼧?shù)是符合這種定義的，滿足國(guó)際上定義的滿二叉樹(shù)，但是不滿足國(guó)內(nèi)的定義。1

基于滿二叉樹(shù)的原地快速排序一種基于滿二叉樹(shù)的原地快速排序算法。 與經(jīng)典快速排序算法相比, 新算法每趟劃分采用動(dòng)態(tài)樞軸而不是靜態(tài)樞軸, 同時(shí)新算法利用滿二叉樹(shù)的特點(diǎn)計(jì)算下一趟劃分的樞軸位置和元素范圍, 避免使用遞歸或開(kāi)辟內(nèi)存堆棧。 實(shí)驗(yàn)表明, 新算法的時(shí)間性能優(yōu)于最好的原地排序—堆排序。 原地快速排序二叉樹(shù)的概念對(duì)排序算法的研究和改進(jìn)具有很好的理論和實(shí)用參考價(jià)值。

給定一個(gè)長(zhǎng)度為m的順序表 ,每個(gè)元素由一個(gè)關(guān)鍵字和其他的相關(guān)信息構(gòu)成 , 排序算法的任務(wù)就是根據(jù)關(guān)鍵字以非降序(或非升序)重新安排數(shù)組中的元素(不失一般性, 以下我們按非降序排序)。排序算法僅允許做關(guān)鍵字比較和元素移動(dòng)操作, 并用關(guān)鍵字比較次數(shù)和元素移動(dòng)次數(shù) ,衡量排序算法的時(shí)間性能和空間性能 。如果一個(gè)算法所使用的額外空間是一個(gè)固定常數(shù) ,與處理問(wèn)題的規(guī)模無(wú)關(guān) ,則我們稱(chēng)該算法是原地的?？焖倥判蛩惴ㄊ亲詈玫呐判蛩惴ㄖ? 它的基本思想是通過(guò)若干次劃分得到有序表。一次劃分后樞軸左邊元素的關(guān)鍵字都不大于樞軸的關(guān)鍵字, 樞軸右邊元素的關(guān)鍵字都不小于樞軸的關(guān)鍵字 。然后對(duì)樞軸左邊和右邊的元素繼續(xù)劃分 ,直到每個(gè)部分都只有1個(gè)元素為止。經(jīng)典快速排序或用遞歸函數(shù)實(shí)現(xiàn)或自己開(kāi)辟內(nèi)存堆棧實(shí)現(xiàn),需要的額外空間, 都不是嚴(yán)格意義上的原地算法 。在本文中 ,將滿二叉樹(shù)的概念引入快速排序中, 利用滿二叉樹(shù)的特點(diǎn)計(jì)算下一趟劃分的樞軸位置和元素范圍 ,避免了使用遞歸或開(kāi)辟內(nèi)存堆棧 ,從而將快速排序改造成嚴(yán)格原地的。實(shí)驗(yàn)表明, 該算法的時(shí)間性能優(yōu)于最好的原地排序 —堆排序。

基于滿二叉樹(shù)二分K-means聚類(lèi)并行推薦算法在推薦系統(tǒng)中應(yīng)用K-means算法聚類(lèi)可有效降維，然而聚類(lèi)效果往往依賴(lài)于選定的初始中心，并且一旦選定目標(biāo)簇后，推薦過(guò)程只針對(duì)目標(biāo)簇進(jìn)行，與其他簇?zé)o關(guān)。針對(duì)上述兩個(gè)問(wèn)題，提出一種基于滿二叉樹(shù)的二分K-means聚類(lèi)并行推薦算法。該算法首先反復(fù)迭代二分K-means算法，迭代過(guò)程中使用簇內(nèi)凝聚度作為分裂閾值，形成一顆滿二叉樹(shù)；然后通過(guò)層次遍歷將用戶歸入到K個(gè)葉子節(jié)點(diǎn)（簇）；最后針對(duì)K個(gè)簇，應(yīng)用MapReduce框架進(jìn)行并行推薦預(yù)測(cè)。MovieLens上的實(shí)驗(yàn)結(jié)果表明，該算法可大幅度提高推薦系統(tǒng)準(zhǔn)確性，同時(shí)增強(qiáng)系統(tǒng)可擴(kuò)展性。2

基于滿二叉樹(shù)的RA碼交織器設(shè)計(jì)為提高輸入信息較長(zhǎng)時(shí)重復(fù)累積碼的編碼效率，對(duì)重復(fù)累積碼的交織器進(jìn)行優(yōu)化改進(jìn)。按照滿二叉樹(shù)子節(jié)點(diǎn)的奇偶排列方式對(duì)交織器的輸入序列依次分組，并利用葉子節(jié)點(diǎn)對(duì)分組信息重新組合獲得輸出序列，與S隨機(jī)交織器相比，大大降低輸入信息之間的相關(guān)性，避免了RA碼校驗(yàn)矩陣中I、II類(lèi)4環(huán)的產(chǎn)生，保證了譯碼的準(zhǔn)確性。仿真結(jié)果表明，在輸入信息序列較長(zhǎng)時(shí)，改進(jìn)的交織器編碼速度快且誤碼率遠(yuǎn)低于行列規(guī)則交織器；與S隨機(jī)交織器相比，改進(jìn)的交織器可以顯著提高編碼速率，且在誤碼率同為時(shí)約有0.3dB的增益。3

本詞條內(nèi)容貢獻(xiàn)者為:

劉燕兵 - 副研究員 - 中國(guó)科學(xué)院信息工程研究所