二叉樹的存儲(chǔ)及簡(jiǎn)單遍歷算法

胡承欣

摘 要：自計(jì)算機(jī)出現(xiàn)以來，人們就開始嘗試將生活中遇到的問題在計(jì)算機(jī)中抽象出來并解決，因此出現(xiàn)了數(shù)據(jù)結(jié)構(gòu)的概念，而樹是數(shù)據(jù)結(jié)構(gòu)中十分重要的一種，目前應(yīng)用十分廣泛。本文從樹的結(jié)構(gòu)及概念入手，首先介紹了數(shù)據(jù)結(jié)構(gòu)的概念，以及二叉樹的基本知識(shí)，接著重點(diǎn)介紹了二叉樹在計(jì)算機(jī)中的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)方式，并詳細(xì)介紹了二叉樹的先根遍歷算法以及霍夫曼樹的構(gòu)建方法，最后對(duì)全文進(jìn)行了總結(jié)。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu);二叉樹;存儲(chǔ)方式;遍歷算法;霍夫曼樹

中圖分類號(hào)：TP273 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1671-2064（2019）02-0056-02

1 樹的結(jié)構(gòu)及其概念

1.1 數(shù)據(jù)結(jié)構(gòu)的主要分類

數(shù)據(jù)結(jié)構(gòu)實(shí)質(zhì)上是數(shù)據(jù)的存儲(chǔ)形式，在數(shù)據(jù)結(jié)構(gòu)中較重要的有數(shù)組，線性表，樹等[1]。數(shù)組是數(shù)據(jù)結(jié)構(gòu)中較為常見的一種，它是有序的元素序列，表示有限個(gè)相同類型元素的集合。在一個(gè)數(shù)據(jù)集合中，每一個(gè)數(shù)據(jù)元素對(duì)應(yīng)于一個(gè)存儲(chǔ)單元，也稱之為數(shù)據(jù)結(jié)點(diǎn)，簡(jiǎn)稱結(jié)點(diǎn)。而樹就是由有限結(jié)點(diǎn)組成的一個(gè)具有層次關(guān)系的集合，結(jié)點(diǎn)則是樹的層次性的體現(xiàn)者。在數(shù)據(jù)結(jié)構(gòu)中出現(xiàn)的樹并非我們生活中所提及的自然之樹，只是因?yàn)槠湎褚豢玫沽⒌臉洌史Q之為樹。

1.2 二叉樹簡(jiǎn)介

上文提到的樹有很多分類，如二叉樹、有序或無序樹等。二叉樹是指在整個(gè)樹中每個(gè)結(jié)點(diǎn)最多只有兩個(gè)子結(jié)點(diǎn)的樹結(jié)構(gòu)，是樹結(jié)構(gòu)中最重要也是最基礎(chǔ)的結(jié)構(gòu)。二叉樹含有完全二叉樹，滿二叉樹等。完全二叉樹與滿二叉樹又有一些區(qū)別。完全二叉樹是指除最后一層外，其余各層達(dá)到該層的最大結(jié)點(diǎn)數(shù)，若最后一層不滿，則最后一層的所有結(jié)點(diǎn)都靠左排，而滿二叉樹是指所有結(jié)點(diǎn)都達(dá)到該層的最大結(jié)點(diǎn)數(shù)，在滿二叉樹中每層的最大結(jié)點(diǎn)數(shù)為2n-1。

完全二叉樹與滿二叉樹是包含關(guān)系，即完全二叉樹包含了滿二叉樹，但滿二叉樹無法包含完全二叉樹。本文重點(diǎn)介紹的為二叉樹相關(guān)的內(nèi)容。

2 二叉樹的主要存儲(chǔ)方式

在計(jì)算機(jī)能夠?qū)溥M(jìn)行一系列的操作之前，我們需要知道二叉樹的存儲(chǔ)方式是什么。我們將需要存儲(chǔ)的元素比作需要存取的衣物，將衣柜比作內(nèi)存區(qū)域，而存衣物可以有不同的方法，不同的方法對(duì)找到不同的衣物的快慢不同，同樣的數(shù)據(jù)的存儲(chǔ)中存在不同的存儲(chǔ)方式，我們需要根據(jù)實(shí)際情況來選擇。在二叉樹的存儲(chǔ)中主要有兩種存儲(chǔ)方式，即順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)[2]。

2.1 順序存儲(chǔ)

順序存儲(chǔ)的定義為：在計(jì)算機(jī)中用存儲(chǔ)單元存儲(chǔ)相應(yīng)的元素，存儲(chǔ)單元的在內(nèi)存地址上是連續(xù)的，且被存儲(chǔ)的元素在邏輯上也是連續(xù)的，如一維數(shù)組的從左至右的所有元素。例如：int arrary[ ]={3，4，5，6，7，8}，在該數(shù)組中有6個(gè)元素，對(duì)應(yīng)了6個(gè)存儲(chǔ)單元，該6個(gè)存儲(chǔ)單元在位置上是連續(xù)的，則該存儲(chǔ)方式為順序存儲(chǔ)。從例子我們可以知道array[0]=3，而與它相鄰的則是array[1]=4。在順序存儲(chǔ)中，想訪問其中的元素其實(shí)很容易，因?yàn)樗鼈兊奈锢砦恢檬沁B續(xù)的。所以當(dāng)我們按照順序存儲(chǔ)數(shù)據(jù)時(shí)，我們會(huì)根據(jù)自己的需求來存放數(shù)據(jù)。對(duì)二叉樹而言，順序存儲(chǔ)用地址連續(xù)的存儲(chǔ)單元按照從上至下，從左至右的順序存儲(chǔ)結(jié)點(diǎn)元素。在順序存儲(chǔ)中的存儲(chǔ)規(guī)則為：將其每個(gè)結(jié)點(diǎn)與完全二叉樹上的結(jié)點(diǎn)相對(duì)應(yīng)，將結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組中。

2.2 鏈?zhǔn)酱鎯?chǔ)

在數(shù)據(jù)存儲(chǔ)中還有一種存儲(chǔ)方式叫鏈?zhǔn)酱鎯?chǔ)，其定義為：在計(jì)算機(jī)中用一組任意的存儲(chǔ)單元存儲(chǔ)線性表中的元素。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)方式不要求每個(gè)數(shù)據(jù)元素物理位置相鄰，也就是說它的物理地址位置關(guān)系是隨機(jī)的，不像順序存儲(chǔ)那樣有規(guī)律。但為了方便尋找與其中一個(gè)元素邏輯相鄰的元素的物理位置，我們需要在定義鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)還需定義一個(gè)保存與其邏輯相鄰元素的信息的指針域，在二叉樹的鏈?zhǔn)酱鎯?chǔ)中，給每個(gè)結(jié)點(diǎn)定義相同的鏈表結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)包含它本身的數(shù)據(jù)域和指向下一個(gè)結(jié)點(diǎn)的指針域。如二叉樹的二叉鏈表，就包含數(shù)據(jù)域和指向左右孩子的指針域。（總而言之，若其中一個(gè)元素值稱為數(shù)據(jù)域，則與它相鄰邏輯關(guān)系相鄰元素位置的信息稱為指針域）。

2.3 二者的利弊分析

從上文對(duì)順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的分析可知，二者的特征幾乎是不相同的，二者各有利弊。我們可以發(fā)現(xiàn)，在順序存儲(chǔ)中相鄰元素的存儲(chǔ)位置也是相鄰的，是一塊連續(xù)的內(nèi)存，所以我們對(duì)數(shù)據(jù)進(jìn)行插入或刪除時(shí)，就會(huì)顯得比較繁瑣，對(duì)數(shù)據(jù)進(jìn)行插入或刪除時(shí)，需要進(jìn)行對(duì)位置的填充，并且可能要移動(dòng)一系列結(jié)點(diǎn)，比較浪費(fèi)時(shí)間。而鏈?zhǔn)浇Y(jié)構(gòu)中位置可不連續(xù)，所以只要內(nèi)存空間中有空位就可以存入。但鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)失去了順序表中的可直接訪問的優(yōu)點(diǎn)。所以在數(shù)據(jù)存儲(chǔ)時(shí)，我們通常把握幾個(gè)原則：（1）當(dāng)我們需要對(duì)數(shù)據(jù)頻繁查找，很少對(duì)數(shù)據(jù)進(jìn)行改動(dòng)時(shí)，選擇順序存儲(chǔ);（2）當(dāng)線性表中我們不知道內(nèi)存大小時(shí)，選擇鏈?zhǔn)酱鎯?chǔ)。對(duì)于二叉樹來說，若該二叉樹為完全二叉樹，且對(duì)所存儲(chǔ)的數(shù)據(jù)很少改動(dòng)時(shí)，選用順序存儲(chǔ)，除此之外使用鏈?zhǔn)酱鎯?chǔ)。

3 遍歷算法

3.1 二叉樹遍歷算法簡(jiǎn)介

所謂遍歷，是指按照一定的策略，依次訪問樹中的每個(gè)節(jié)點(diǎn)，且不重復(fù)訪問;而遍歷算法就是利用遍歷的原理對(duì)樹進(jìn)行運(yùn)算。在遍歷算法中主要有三種遍歷方式，即先根遍歷，中根遍歷，后根遍歷，在進(jìn)行運(yùn)算時(shí)應(yīng)根據(jù)實(shí)際問題選擇遍歷方式。將遍歷算法區(qū)分成三種，是因?yàn)樗鼈兯裱谋闅v規(guī)則不同：主要根據(jù)訪問根節(jié)點(diǎn)的先后來區(qū)分，先訪問根節(jié)點(diǎn)再遍歷左右子樹為先根遍歷，同理中間訪問根節(jié)點(diǎn)為中根遍歷，最后訪問根節(jié)點(diǎn)為后跟遍歷[3]。因此，遍歷一個(gè)非空二叉樹一般要進(jìn)行以下幾個(gè)操作：（1）訪問結(jié)點(diǎn)（將節(jié)點(diǎn)當(dāng)作根節(jié)點(diǎn)）;（2）遍歷當(dāng)前結(jié)點(diǎn)的左子樹;（3）遍歷當(dāng)前結(jié)點(diǎn)的右子樹。根據(jù)遍歷算法的不同規(guī)則，以上三個(gè)操作的順序也是不同的[4]。下文重點(diǎn)介紹先根遍歷的原理與實(shí)現(xiàn)過程。

3.2 先根遍歷的實(shí)現(xiàn)原理及過程

由于三種遍歷算法僅僅執(zhí)行順序不同，本文僅詳細(xì)介紹先根遍歷的過程，根據(jù)上文介紹的先根遍歷規(guī)則：先訪問根節(jié)點(diǎn)，再遍歷左子樹，最后遍歷右子樹，我們以圖1為例來分析：

在先根遍歷中，我們首先要找到根結(jié)點(diǎn)，即A，記錄A。根據(jù)先根遍歷規(guī)則，所以再遍歷A的左子樹，A的左子樹存在，找到C，記錄C，把C當(dāng)做根結(jié)點(diǎn)，遍歷C的左子樹;C的左子樹存在，找到D，把D當(dāng)做根結(jié)點(diǎn)，記錄D，D的左子樹不存在，根據(jù)規(guī)則，D的右子樹存在找到B，把B當(dāng)做根結(jié)點(diǎn)，記錄B;返回D，D的右子樹遍歷完，返回C;C的左右子樹遍歷完，返回A;A的左子樹遍歷完，開始遍歷A的右子樹，找到E，記錄E，把E當(dāng)做根結(jié)點(diǎn)，開始遍歷E的左子樹，找到F，把F當(dāng)做根結(jié)點(diǎn)，遍歷F的左子樹，左子樹不存在，返回F并記錄F，再遍歷F的右子樹，找到G，記錄G，把G當(dāng)做根結(jié)點(diǎn)，遍歷G的左子樹，找到I，把I當(dāng)做根結(jié)點(diǎn)，遍歷I的左子樹，找到J;J為葉子結(jié)點(diǎn)，返回I，記錄I;I無右子樹，返回G;G無右子樹，返回E并記錄E;遍歷E的右子樹，找到H，記錄H，返回E，A的右子樹遍歷完畢，所以整個(gè)二叉樹先根遍歷完畢。所以先根遍歷的順序?yàn)椋篈CDBEFGIJH。根據(jù)以上的遍歷步驟，中根遍歷的遍歷順序?yàn)椋篋BCAFJIGEH;后根遍歷的遍歷順序：BDCJIGFHEA。

3.3 霍夫曼編碼

二叉樹在實(shí)際生活中的應(yīng)用最普遍的額就是霍夫曼編碼，因?yàn)榛舴蚵鼧涞玫降木幋a長(zhǎng)度不一，以發(fā)送電報(bào)為例，將經(jīng)常出現(xiàn)的字符用較短長(zhǎng)度的編碼表示，不常出現(xiàn)的字符用較長(zhǎng)編碼表示，這就能夠從整體上得到編碼長(zhǎng)度較短的電報(bào)。有利于提升電報(bào)發(fā)送的速度和效率。以下對(duì)霍夫曼編碼進(jìn)行詳細(xì)說明：

首先我們將給定的4個(gè)根節(jié)點(diǎn)分別定義為a，b，c，d，需要選擇兩棵根節(jié)點(diǎn)權(quán)值最小的樹，即c，d;將其組合為一個(gè)新的二叉樹，其中c，d為該二叉樹的左右結(jié)點(diǎn)，組成的二叉樹的根節(jié)點(diǎn)權(quán)值為8;用e表示，將原有的c，d刪除并將e放入集合中，比較權(quán)值大小，發(fā)現(xiàn)e和a為現(xiàn)集合權(quán)值最小的兩棵樹;將e和a組合成一個(gè)新的二叉樹，權(quán)值為15;以此類推，直到F只有一棵樹，見圖2。

4 結(jié)語

在計(jì)算機(jī)中，樹可以說是無處不在，并且在計(jì)算機(jī)的體系中，樹的地位是無可替代的。因?yàn)橛?jì)算機(jī)的核心是計(jì)算和儲(chǔ)存，而樹有效的解決了計(jì)算機(jī)的儲(chǔ)存問題和計(jì)算時(shí)程序調(diào)用的問題。在數(shù)據(jù)結(jié)構(gòu)方面，因?yàn)闃涞膹?qiáng)大的儲(chǔ)存查詢功能，使查詢數(shù)據(jù)時(shí)顯得十分高效，樹的空間復(fù)雜度利于數(shù)據(jù)儲(chǔ)存;在計(jì)算機(jī)的算法方面，從前文所述中可以發(fā)現(xiàn)，沒有樹作為算法的模板，我們很難去描述一個(gè)算法，由此可見，樹在計(jì)算機(jī)中的應(yīng)用十分的廣泛。

參考文獻(xiàn)

[1] 朱戰(zhàn)立，張選平.數(shù)據(jù)結(jié)構(gòu)要點(diǎn)與解題——三一叢書[M].西安交通大學(xué)出版社，2006.

[2] 楊萌，李嵩嵩，蘇姣.一種高效的二叉樹存儲(chǔ)結(jié)構(gòu)[J].中國(guó)科技博覽，2009（28）：228-228.

[3] 馬靖善，秦玉平.順序存儲(chǔ)二叉樹的遍歷及其應(yīng)用研究[J].渤海大學(xué)學(xué)報(bào)（自然科學(xué)版），2013（2）：172-176.

[4] 劉洋.一種統(tǒng)一的二叉樹結(jié)構(gòu)遍歷算法及其實(shí)現(xiàn)[J].贛南師范學(xué)院學(xué)報(bào)，2004，25（3）：10-13.

[5] 王防修，劉春紅.一種哈夫曼編碼的改進(jìn)算法[J].武漢輕工大學(xué)學(xué)報(bào)，2016，35（1）：88-91.