【原】PHP數(shù)據(jù)結(jié)構(gòu)-完全二叉樹、線索二叉樹及樹的順序存儲(chǔ)結(jié)構(gòu)

硬核項(xiàng)目經(jīng)理 2021-05-31

展開全文

完全二叉樹、線索二叉樹及樹的順序存儲(chǔ)結(jié)構(gòu)

在上篇文章中，我們學(xué)習(xí)了二叉樹的基本鏈?zhǔn)浇Y(jié)構(gòu)以及建樹和遍歷相關(guān)的操作。今天我們學(xué)習(xí)的則是一些二叉樹相關(guān)的概念以及二叉樹的一種變形形式。

完全二叉樹

什么叫完全二叉樹呢？在說到完全二叉樹之前，我們先說另外一個(gè)名詞：“滿二叉樹”。像我們之前文章中演示過的那個(gè)二叉樹，就是一顆“滿二叉樹”。在這顆樹中，所有的結(jié)點(diǎn)都有兩個(gè)孩子結(jié)點(diǎn)，沒有哪個(gè)結(jié)點(diǎn)是只有一個(gè)孩子結(jié)點(diǎn)的，并且所有最底層的葉子結(jié)點(diǎn)都在同一層，這種樹就稱為“滿二叉樹”，也稱為“完美二叉樹”。

是不是非常漂亮的一顆樹？沒錯(cuò)，這種二叉樹非常地完美，它沒有多余的結(jié)點(diǎn)，也沒有缺少的結(jié)點(diǎn)，非常的漂亮。但是，在現(xiàn)實(shí)中，完美的東西是很稀少的，人生總會(huì)有一點(diǎn)缺憾嘛。我們盡量不要讓自己有太多的缺憾，但也總不能過上沒有一絲缺憾的人生。所以，我們允許葉結(jié)點(diǎn)出現(xiàn)在最下層和次下層，而且最下層的葉結(jié)點(diǎn)集中在樹的左部，也就是葉結(jié)點(diǎn)只能有左子樹，那么，這樣的一顆略帶缺憾的樹就叫做“完全二叉樹”。不要擔(dān)心它不完美，因?yàn)檫@樣略帶缺憾的人生才是最真實(shí)的嘛，所以“完全二叉樹”是一種理想的樹結(jié)構(gòu)。

從定義中，我們可以看出，一顆“滿二叉樹”，必定是一顆“完全二叉樹”，而一顆葉子結(jié)點(diǎn)都在一層的并且所有結(jié)點(diǎn)都有左右孩子結(jié)點(diǎn)的“完全二叉樹”也就是一顆”滿二叉樹“。

為什么要講”滿二叉樹“和”完全二叉樹“呢？當(dāng)然是為了我們接下來的內(nèi)容做鋪墊。因?yàn)椤睗M二叉樹“是最符合二叉樹性質(zhì)的一顆樹。還記得樹系列的第一篇文章中介紹過的二叉樹的那五個(gè)性質(zhì)嗎？當(dāng)時(shí)我們就是以那顆”滿二叉樹“為例進(jìn)行講解的。而其中的性質(zhì)5 ，就是我們學(xué)習(xí)使用順序結(jié)構(gòu)存儲(chǔ)二叉樹的基礎(chǔ)。

二叉樹的順序存儲(chǔ)

通過”滿二叉樹“的概念，以及二叉樹的性質(zhì)5 我們就可以實(shí)現(xiàn)使用一個(gè)數(shù)組來存儲(chǔ)順序結(jié)構(gòu)的實(shí)現(xiàn)。

$treeList = ['', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O'];

相信大家不陌生吧，在上篇文章中，我們就是通過這個(gè)數(shù)組來建立鏈樹的，而這個(gè)數(shù)組其實(shí)就是一個(gè)線性存儲(chǔ)的二叉樹。我們通過對比二叉樹的性質(zhì)5 來看一下。

A 結(jié)點(diǎn)的下標(biāo)是 1 ，它是我們的樹根。它的子結(jié)點(diǎn)是 B 和 C ，對應(yīng)的下標(biāo)分別是 2 和 3 ，也就是 1 * 2 和 1 * 2 + 1 。
同理，我們再選取一個(gè)結(jié)點(diǎn) F 。它的下標(biāo)是 6 ，所以它的左孩子結(jié)點(diǎn)的下標(biāo)是 6 * 2 = 12 ，對應(yīng)的是 L ；它的右孩子結(jié)點(diǎn)是 6 * 2 + 1 = 13 ，對應(yīng)的是 M 。
反過來看，一個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)就是 i / 2 。我們看下 K 結(jié)點(diǎn)的下標(biāo)是 11 ，它的父結(jié)點(diǎn)就是 11 / 2 ，舍去小數(shù)點(diǎn)是下標(biāo) 5 的位置，也就是結(jié)點(diǎn) E ；結(jié)點(diǎn) J 的下標(biāo)是 10 ，它的父結(jié)點(diǎn)是 10 / 2 ，也是下標(biāo)為 5 的 E 結(jié)點(diǎn)。

這下想必大家就明白了用數(shù)組是如何表示一顆二叉樹結(jié)構(gòu)了吧。而且數(shù)組這種結(jié)構(gòu)更加的一維，更能體現(xiàn)出對于樹的操作就是二維化一維的一種表示，也就是非線性轉(zhuǎn)線性，這樣才能讓我們方便地操作這些數(shù)據(jù)。

針對順序存儲(chǔ)結(jié)構(gòu)，也就是數(shù)組元素的遍歷，也是可以使用先序、中序、后序以及層序的形式。不過這些遍歷方法都需要根據(jù)二叉樹的性質(zhì)5 來進(jìn)行遍歷。但更重要的是，只要給我一個(gè)下標(biāo)，我們通過二叉樹的性質(zhì)，就可能很容易地知道它的下級(jí)結(jié)點(diǎn)和上級(jí)結(jié)點(diǎn)的位置，能夠快速地獲得這些結(jié)點(diǎn)的信息。這一大特點(diǎn)是鏈?zhǔn)浇Y(jié)構(gòu)的二叉樹所沒有的。

如果我們要存儲(chǔ)的不是一顆”滿二叉樹“呢？甚至它都不是一顆完全二叉樹的情況下，只需要將對應(yīng)的結(jié)點(diǎn)設(shè)置為空值就行了。比如：

$treeList = ['', 'A', 'B', 'C', 'D', 'E', 'I', '', '', '', '', 'H', '', 'J', '', ''];

這顆樹的結(jié)構(gòu)所對應(yīng)的二叉樹圖形就是這樣的：

然后在建鏈樹的方法中，我們只需要再增加一個(gè)判斷就可以了。我們就可以通過這樣一個(gè)順序存儲(chǔ)的二叉樹快速地生成一顆鏈?zhǔn)酱鎯?chǔ)的二叉樹，方便我們之后的操作。

// 建立二叉樹
function CreateBiTree($arr, $i)
{
    if (!isset($arr[$i]) || !$arr[$i]) { // 這里增加了個(gè)判斷，如果數(shù)組元素為空
        return null;
    }
    $t = new TBTNode();
    $t->data = $arr[$i];
    $t->lChild = CreateBiTree($arr, $i * 2);
    $t->rChild = CreateBiTree($arr, $i * 2 + 1);
    return $t;
}

線索二叉樹

一環(huán)套一環(huán)，接下來我們再來講講”線索二叉樹“。這又是個(gè)什么東西呢？

從上面的學(xué)習(xí)中，我們知道了”滿二叉樹“和”完全二叉樹“。但是這種結(jié)構(gòu)都是非常理想的樹結(jié)構(gòu)，不過真實(shí)的情況可能大部分都是”理想很豐滿，現(xiàn)實(shí)很骨感“。很多樹并不能形成那樣的完全二叉樹的形式，更別提”滿二叉樹“了。而樹的遍歷又經(jīng)常會(huì)使用棧或者隊(duì)列來實(shí)現(xiàn)，這兩種遍歷方式基本都是線性的，也就是最好情況下也是 O(n) 的時(shí)間復(fù)雜度。那么，有沒有什么更快一點(diǎn)的方式來提高遍歷的效率呢？

我們這樣來嘗試一下：

如果樹的葉子結(jié)點(diǎn)的左孩子結(jié)點(diǎn)為空，就讓它指向前驅(qū)（上級(jí)）結(jié)點(diǎn)
如果樹的葉子結(jié)點(diǎn)的右孩子結(jié)點(diǎn)為空，就讓它指向后繼結(jié)點(diǎn)

這樣有什么好處呢？我們可以避免掉大范圍的遞歸操作，從而加快樹的遍歷速度。在整個(gè)算法中，它并沒有什么優(yōu)勢，因?yàn)槲覀冃枰獙⒁活w樹進(jìn)行線索化，也就是去改變它的葉子結(jié)點(diǎn)的左右孩子的指向，這也是一次遍歷。但是，如果你的操作是經(jīng)常需要遍歷，而且是來回的多次遍歷，那么它的整體性能是要強(qiáng)于普通二叉樹的遍歷的。因?yàn)樵谝淮尉€索化之后，它的遍歷就是在快速的查找葉子結(jié)點(diǎn)的基礎(chǔ)上進(jìn)行普通的線性遍歷操作，而不是遞歸操作。

對于線索二叉樹來說，我們需要改變樹的結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)。

// 線索二叉樹結(jié)點(diǎn)
class TBTNode
{
    public $data;
    public $lTag = 0;
    public $rTag = 0;
    public $lChild;
    public $rChild;
}

我們增加了兩個(gè)標(biāo)志位，當(dāng) lTag 或 rTag 為 1 時(shí)，lChild 或 rChild 分別指向前驅(qū)或后繼結(jié)點(diǎn)。這樣在最后的遍歷時(shí)，我們就可以快速地通過這個(gè) tag 標(biāo)志位分辨出結(jié)點(diǎn)的指向狀態(tài)。

然后我們先簡單地建立一顆樹。使用上一節(jié)中的那個(gè)示例。

// 建立二叉樹
function CreateBiTree($arr, $i)
{
    if (!isset($arr[$i]) || !$arr[$i]) { // 這里增加了個(gè)判斷，如果數(shù)組元素為空
        return null;
    }
    $t = new TBTNode();
    $t->data = $arr[$i];
    $t->lChild = CreateBiTree($arr, $i * 2);
    $t->rChild = CreateBiTree($arr, $i * 2 + 1);
    return $t;
}

$treeList = ['', 'A', 'B', 'C', 'D', 'E', 'I', '', '', '', '', 'H', '', 'J', '', ''];

$tree = CreateBiTree($treeList, 1);

接下來就是最重要的線索化過程，我們可以建立前序、中序、后序的線索二叉樹。對應(yīng)的，在最后的線索二叉樹遍歷時(shí)獲得的結(jié)果也將是這三種遍歷方式所對應(yīng)的結(jié)果。在這里，我們學(xué)習(xí)最普遍的也是最經(jīng)典的”中序線索二叉樹“。所以，我們以中序遍歷的形式將這顆樹線索化。

// 線索化
function InThread(?TBTNode $p, ?TBTNode &$pre)
{
    if ($p) {
        // 遞歸，左子樹線索化
        InThread($p->lChild, $pre);

        if (!$p->lChild) {
            // 建立當(dāng)前結(jié)點(diǎn)的前驅(qū)線索
            $p->lChild = $pre;
            $p->lTag = 1;
        }
        if ($pre && !$pre->rChild) {
            // 建立當(dāng)前結(jié)點(diǎn)的后繼線索
            $pre->rChild = $p;
            $pre->rTag = 1;
        }
        $pre = $p; // $pre 指向當(dāng)前的 $p ，作為 $p 將要指向的下一個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)指示指針
        $p = $p->rChild; // $p 指向一個(gè)新結(jié)點(diǎn)，此時(shí) $pre 和 $p 分別指向的結(jié)點(diǎn)形成了一個(gè)前驅(qū)后繼對，為下一次線索化做準(zhǔn)備
        
        // 遞歸，右子樹線索化
        InThread($p, $pre);
    }
}

// 創(chuàng)建線索二叉樹
function createInThread(TBTNode $root)
{
    $pre = null; // 前驅(qū)結(jié)點(diǎn)指針
    if($root){
        InThread($root, $pre);
        $pre->rChild = null; // 非空二叉樹，線索化
        $pre->rTag = 1; // 后處理中序最后一個(gè)結(jié)點(diǎn)
    }
}

createInThread($tree);

var_dump($tree);
// object(TBTNode)#1 (5) {
//     ["data"]=>
//     string(1) "A"
//     ["lTag"]=>
//     int(0)
//     ["rTag"]=>
//     int(0)
//     ["lChild"]=>
//     object(TBTNode)#2 (5) {
//       ["data"]=>
//       string(1) "B"
//       ["lTag"]=>
//       int(0)
//       ["rTag"]=>
//       int(0)
//       ["lChild"]=>
//       object(TBTNode)#3 (5) {
//         ["data"]=>
//         string(1) "D"
//         ["lTag"]=>
//         int(1)
//         ["rTag"]=>
//         int(1)
//         ["lChild"]=>
//         NULL
//         ["rChild"]=>
//         *RECURSION*
//       }
//       ……

關(guān)于算法的具體步驟在注釋中已經(jīng)寫得很詳細(xì)了。一句話總結(jié)就是在中序遍歷的過程中，根據(jù)結(jié)點(diǎn)的信息來確定它的左右孩子的形式，如果有左右孩子就繼續(xù)，如果沒有任一一個(gè)孩子的話，就將左右結(jié)點(diǎn)指向前驅(qū)或者后繼。建立之后的線索二叉樹就如圖所示：

最后就是遍歷了。我們需要的是能夠快速地獲得最左葉子結(jié)點(diǎn)的信息，然后就是下一跳的信息，這時(shí)，線索的威力就發(fā)揮出來了。

// 以 $p 為根的中序線索二叉樹中，中序序列下的第一個(gè)結(jié)點(diǎn)，也就是最左邊那個(gè)結(jié)點(diǎn)
function First(?TBTNode $p){
    while($p->lTag == 0){
        $p = $p->lChild; // 最左下結(jié)點(diǎn)（不一定是葉子結(jié)點(diǎn)）
    }
    return $p;
}

// 在中序二叉樹中，結(jié)點(diǎn) $p 在中序下的后繼結(jié)點(diǎn)
function NextNode(?TBTNode $p){
    if($p->rTag == 0){
        return First($p->rChild);
    }else{
        return $p->rChild; // 如果 rTag == 1 ，直接返回后繼線索
    }
}

// 在中序線索二叉樹上進(jìn)行中序遍歷
function Inorder(TBTNode $root){
    //     第一個(gè)結(jié)點(diǎn)      結(jié)點(diǎn)不為空    下一個(gè)結(jié)點(diǎn)
    for($p = First($root);$p;$p=NextNode($p)){
        echo $p->data, ',';
    }
}

Inorder($tree); // D,B,E,H,A,I,J,C,

當(dāng)遇到 lTag 不為 0 的結(jié)點(diǎn)時(shí)，這個(gè)結(jié)點(diǎn)就是最左的那個(gè)結(jié)點(diǎn)了，如果這個(gè)不為空的話，【輸出】它。接著我們獲得下一跳的結(jié)點(diǎn)，也就是判斷這個(gè)結(jié)點(diǎn)的右孩子 rTag 標(biāo)志，如果是為 0 的，也就是它還有右孩子，【輸出】后向下查找，直到找到一個(gè) rTag 也為 1 的結(jié)點(diǎn)，直接返回這個(gè)結(jié)點(diǎn)的后繼，也就是中序遍歷的中間那個(gè)結(jié)點(diǎn)，【輸出】它。

最后輸出的順序是不是和我們中序遍歷的結(jié)果一樣呢？注意看代碼，在遍歷中序線索二叉樹的時(shí)候，我們沒有用一個(gè)遞歸吧，全部是使用的 while() 和 for() 就完成了對這個(gè)線索二叉樹的遍歷。

總結(jié)

堅(jiān)持到現(xiàn)在不容易，不能再小看數(shù)據(jù)結(jié)構(gòu)了吧？現(xiàn)在還只是樹，我們的圖都還沒開始呢！當(dāng)然，也不要害怕，一步一步的學(xué)，慢慢掌握，不要幻想一口氣吃成個(gè)胖子。即使是寫完這篇文章了，我也不可能馬上就手寫出一個(gè)中序的線索二叉樹來的。大家還是以理解原理為主，如果說真能手寫的話，那也是為了面試而去背的或者是為了考研而準(zhǔn)備的。如果有這樣為了應(yīng)付的小同學(xué)出現(xiàn)在面試中的話，我反而要更多問一些其它的問題，畢竟臨時(shí)抱佛腳的準(zhǔn)備遠(yuǎn)不如深入理解帶來的感悟更能打動(dòng)人！

測試代碼：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/4.樹/source/4.3完全二叉樹、線索二叉樹及樹的順序存儲(chǔ)結(jié)構(gòu).php

參考資料：

《數(shù)據(jù)結(jié)構(gòu)》第二版，嚴(yán)蔚敏

《數(shù)據(jù)結(jié)構(gòu)》第二版，陳越

《數(shù)據(jù)結(jié)構(gòu)高分筆記》2020版，天勤考研