完全二叉樹和線索二叉樹是什么

完全二叉樹和線索二叉樹是什么，針對這個問題，這篇文章詳細介紹了相對應(yīng)的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

完全二叉樹

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

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

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

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

二叉樹的順序存儲

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

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

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

• A 結(jié)點的下標(biāo)是 1 ，它是我們的樹根。它的子結(jié)點是 B 和 C ，對應(yīng)的下標(biāo)分別是 2 和 3 ，也就是 1  2 和 1  2 + 1 。

• 同理，我們再選取一個結(jié)點 F 。它的下標(biāo)是 6 ，所以它的左孩子結(jié)點的下標(biāo)是 6  2 = 12 ，對應(yīng)的是 L ；它的右孩子結(jié)點是 6  2 + 1 = 13 ，對應(yīng)的是 M 。

• 反過來看，一個結(jié)點的父結(jié)點就是 i / 2 。我們看下 K 結(jié)點的下標(biāo)是 11 ，它的父結(jié)點就是 11 / 2 ，舍去小數(shù)點是下標(biāo) 5 的位置，也就是結(jié)點 E ；結(jié)點 J 的下標(biāo)是 10 ，它的父結(jié)點是 10 / 2 ，也是下標(biāo)為 5 的 E 結(jié)點。

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

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

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

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

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

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

// 建立二叉樹
function CreateBiTree($arr, $i)
{
    if (!isset($arr[$i]) || !$arr[$i]) { // 這里增加了個判斷，如果數(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)，接下來我們再來講講”線索二叉樹“。這又是個什么東西呢？

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

我們這樣來嘗試一下：

• 如果樹的葉子結(jié)點的左孩子結(jié)點為空，就讓它指向前驅(qū)（上級）結(jié)點

• 如果樹的葉子結(jié)點的右孩子結(jié)點為空，就讓它指向后繼結(jié)點

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

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

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

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

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

// 建立二叉樹
function CreateBiTree($arr, $i)
{
    if (!isset($arr[$i]) || !$arr[$i]) { // 這里增加了個判斷，如果數(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)的，在最后的線索二叉樹遍歷時獲得的結(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é)點的前驅(qū)線索
            $p->lChild = $pre;
            $p->lTag = 1;
        }
        if ($pre && !$pre->rChild) {
            // 建立當(dāng)前結(jié)點的后繼線索
            $pre->rChild = $p;
            $pre->rTag = 1;
        }
        $pre = $p; // $pre 指向當(dāng)前的 $p ，作為 $p 將要指向的下一個結(jié)點的前驅(qū)結(jié)點指示指針
        $p = $p->rChild; // $p 指向一個新結(jié)點，此時 $pre 和 $p 分別指向的結(jié)點形成了一個前驅(qū)后繼對，為下一次線索化做準(zhǔn)備
        
        // 遞歸，右子樹線索化
        InThread($p, $pre);
    }
}

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

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)寫得很詳細了。一句話總結(jié)就是在中序遍歷的過程中，根據(jù)結(jié)點的信息來確定它的左右孩子的形式，如果有左右孩子就繼續(xù)，如果沒有任一一個孩子的話，就將左右結(jié)點指向前驅(qū)或者后繼。建立之后的線索二叉樹就如圖所示：

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

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

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

// 在中序線索二叉樹上進行中序遍歷
function Inorder(TBTNode $root){
    //     第一個結(jié)點      結(jié)點不為空    下一個結(jié)點
    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é)點時，這個結(jié)點就是最左的那個結(jié)點了，如果這個不為空的話，【輸出】它。接著我們獲得下一跳的結(jié)點，也就是判斷這個結(jié)點的右孩子 $rTag 標(biāo)志，如果是為 0 的，也就是它還有右孩子，【輸出】后向下查找，直到找到一個 $rTag 也為 1 的結(jié)點，直接返回這個結(jié)點的后繼，也就是中序遍歷的中間那個結(jié)點，【輸出】它。

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

總結(jié)

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

測試代碼：

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

關(guān)于完全二叉樹和線索二叉樹是什么問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識。