完全二叉樹和線索二叉樹是什么，針對(duì)這個(gè)問(wèn)題，這篇文章詳細(xì)介紹了相對(duì)應(yīng)的分析和解答，希望可以幫助更多想解決這個(gè)問(wèn)題的小伙伴找到更簡(jiǎn)單易行的方法。
成都創(chuàng)新互聯(lián)是一家專注于網(wǎng)站設(shè)計(jì)、網(wǎng)站制作與策劃設(shè)計(jì),城區(qū)網(wǎng)站建設(shè)哪家好?成都創(chuàng)新互聯(lián)做網(wǎng)站,專注于網(wǎng)站建設(shè)10余年,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:城區(qū)等地區(qū)。城區(qū)做網(wǎng)站價(jià)格咨詢:13518219792
什么叫完全二叉樹呢？在說(shuō)到完全二叉樹之前，我們先說(shuō)另外一個(gè)名詞：“滿二叉樹”。像我們之前文章中演示過(guò)的那個(gè)二叉樹，就是一顆“滿二叉樹”。在這顆樹中，所有的結(jié)點(diǎn)都有兩個(gè)孩子結(jié)點(diǎn)，沒(méi)有哪個(gè)結(jié)點(diǎn)是只有一個(gè)孩子結(jié)點(diǎn)的，并且所有最底層的葉子結(jié)點(diǎn)都在同一層，這種樹就稱為“滿二叉樹”，也稱為“完美二叉樹”。
是不是非常漂亮的一顆樹？沒(méi)錯(cuò)，這種二叉樹非常地完美，它沒(méi)有多余的結(jié)點(diǎn)，也沒(méi)有缺少的結(jié)點(diǎn)，非常的漂亮。但是，在現(xiàn)實(shí)中，完美的東西是很稀少的，人生總會(huì)有一點(diǎn)缺憾嘛。我們盡量不要讓自己有太多的缺憾，但也總不能過(guò)上沒(méi)有一絲缺憾的人生。所以，我們?cè)试S葉結(jié)點(diǎn)出現(xiàn)在最下層和次下層，而且最下層的葉結(jié)點(diǎn)集中在樹的左部，也就是葉結(jié)點(diǎn)只能有左子樹，那么，這樣的一顆略帶缺憾的樹就叫做“完全二叉樹”。不要擔(dān)心它不完美，因?yàn)檫@樣略帶缺憾的人生才是完整的嘛，所以“完全二叉樹”是一種理想的樹結(jié)構(gòu)。
從定義中，我們可以看出，一顆“滿二叉樹”，必定是一顆“完全二叉樹”，而一顆葉子結(jié)點(diǎn)都在一層的并且所有結(jié)點(diǎn)都有左右孩子結(jié)點(diǎn)的“完全二叉樹”也就是一顆”滿二叉樹“。
為什么要講”滿二叉樹“和”完全二叉樹“呢？當(dāng)然是為了我們接下來(lái)的內(nèi)容做鋪墊。因?yàn)椤睗M二叉樹“是最符合二叉樹性質(zhì)的一顆樹。還記得樹系列的第一篇文章中介紹過(guò)的二叉樹的那五個(gè)性質(zhì)嗎？當(dāng)時(shí)我們就是以那顆”滿二叉樹“為例進(jìn)行講解的。而其中的 性質(zhì)5 ，就是我們學(xué)習(xí)使用順序結(jié)構(gòu)存儲(chǔ)二叉樹的基礎(chǔ)。
通過(guò)”滿二叉樹“的概念，以及二叉樹的 性質(zhì)5 我們就可以實(shí)現(xiàn)使用一個(gè)數(shù)組來(lái)存儲(chǔ)順序結(jié)構(gòu)的實(shí)現(xiàn)。
$treeList = ['', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O'];
相信大家不陌生吧，在上篇文章中，我們就是通過(guò)這個(gè)數(shù)組來(lái)建立鏈樹的，而這個(gè)數(shù)組其實(shí)就是一個(gè)線性存儲(chǔ)的二叉樹。我們通過(guò)對(duì)比二叉樹的 性質(zhì)5 來(lái)看一下。
A 結(jié)點(diǎn)的下標(biāo)是 1 ，它是我們的樹根。它的子結(jié)點(diǎn)是 B 和 C ，對(duì)應(yīng)的下標(biāo)分別是 2 和 3 ，也就是 1 2 和 1 2 + 1 。
同理，我們?cè)龠x取一個(gè)結(jié)點(diǎn) F 。它的下標(biāo)是 6 ，所以它的左孩子結(jié)點(diǎn)的下標(biāo)是 6 2 = 12 ，對(duì)應(yīng)的是 L ；它的右孩子結(jié)點(diǎn)是 6 2 + 1 = 13 ，對(duì)應(yīng)的是 M 。
反過(guò)來(lái)看，一個(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)出對(duì)于樹的操作就是二維化一維的一種表示，也就是非線性轉(zhuǎn)線性，這樣才能讓我們方便地操作這些數(shù)據(jù)。
針對(duì)順序存儲(chǔ)結(jié)構(gòu)，也就是數(shù)組元素的遍歷，也是可以使用先序、中序、后序以及層序的形式。不過(guò)這些遍歷方法都需要根據(jù)二叉樹的 性質(zhì)5 來(lái)進(jìn)行遍歷。但更重要的是，只要給我一個(gè)下標(biāo)，我們通過(guò)二叉樹的性質(zhì)，就可能很容易地知道它的下級(jí)結(jié)點(diǎn)和上級(jí)結(jié)點(diǎn)的位置，能夠快速地獲得這些結(jié)點(diǎn)的信息。這一大特點(diǎn)是鏈?zhǔn)浇Y(jié)構(gòu)的二叉樹所沒(méi)有的。
如果我們要存儲(chǔ)的不是一顆”滿二叉樹“呢？甚至它都不是一顆完全二叉樹的情況下，只需要將對(duì)應(yīng)的結(jié)點(diǎn)設(shè)置為空值就行了。比如：
$treeList = ['', 'A', 'B', 'C', 'D', 'E', 'I', '', '', '', '', 'H', '', 'J', '', ''];
這顆樹的結(jié)構(gòu)所對(duì)應(yīng)的二叉樹圖形就是這樣的：
然后在建鏈樹的方法中，我們只需要再增加一個(gè)判斷就可以了。我們就可以通過(guò)這樣一個(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)，接下來(lái)我們?cè)賮?lái)講講”線索二叉樹“。這又是個(gè)什么東西呢？
從上面的學(xué)習(xí)中，我們知道了”滿二叉樹“和”完全二叉樹“。但是這種結(jié)構(gòu)都是非常理想的樹結(jié)構(gòu)，不過(guò)真實(shí)的情況可能大部分都是”理想很豐滿，現(xiàn)實(shí)很骨感“。很多樹并不能形成那樣的完全二叉樹的形式，更別提”滿二叉樹“了。而樹的遍歷又經(jīng)常會(huì)使用?；蛘哧?duì)列來(lái)實(shí)現(xiàn)，這兩種遍歷方式基本都是線性的，也就是最好情況下也是 O(n) 的時(shí)間復(fù)雜度。那么，有沒(méi)有什么更快一點(diǎn)的方式來(lái)提高遍歷的效率呢？
我們這樣來(lái)嘗試一下：
如果樹的葉子結(jié)點(diǎn)的左孩子結(jié)點(diǎn)為空，就讓它指向前驅(qū)（上級(jí)）結(jié)點(diǎn)
如果樹的葉子結(jié)點(diǎn)的右孩子結(jié)點(diǎn)為空，就讓它指向后繼結(jié)點(diǎn)
這樣有什么好處呢？我們可以避免掉大范圍的遞歸操作，從而加快樹的遍歷速度。在整個(gè)算法中，它并沒(méi)有什么優(yōu)勢(shì)，因?yàn)槲覀冃枰獙⒁活w樹進(jìn)行線索化，也就是去改變它的葉子結(jié)點(diǎn)的左右孩子的指向，這也是一次遍歷。但是，如果你的操作是經(jīng)常需要遍歷，而且是來(lái)回的多次遍歷，那么它的整體性能是要強(qiáng)于普通二叉樹的遍歷的。因?yàn)樵谝淮尉€索化之后，它的遍歷就是在快速的查找葉子結(jié)點(diǎn)的基礎(chǔ)上進(jìn)行普通的線性遍歷操作，而不是遞歸操作。
對(duì)于線索二叉樹來(lái)說(shuō)，我們需要改變樹的結(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;
}我們?cè)黾恿藘蓚€(gè)標(biāo)志位，當(dāng) $lTag 或 $rTag 為 1 時(shí)，$lChild 或 $rChild 分別指向前驅(qū)或后繼結(jié)點(diǎn)。這樣在最后的遍歷時(shí)，我們就可以快速地通過(guò)這個(gè) tag 標(biāo)志位分辨出結(jié)點(diǎn)的指向狀態(tài)。
然后我們先簡(jiǎn)單地建立一顆樹。使用上一節(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);接下來(lái)就是最重要的線索化過(guò)程，我們可以建立前序、中序、后序的線索二叉樹。對(duì)應(yīng)的，在最后的線索二叉樹遍歷時(shí)獲得的結(jié)果也將是這三種遍歷方式所對(duì)應(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ū)后繼對(duì)，為下一次線索化做準(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é)就是在中序遍歷的過(guò)程中，根據(jù)結(jié)點(diǎn)的信息來(lái)確定它的左右孩子的形式，如果有左右孩子就繼續(xù)，如果沒(méi)有任一一個(gè)孩子的話，就將左右結(jié)點(diǎn)指向前驅(qū)或者后繼。建立之后的線索二叉樹就如圖所示：
最后就是遍歷了。我們需要的是能夠快速地獲得最左葉子結(jié)點(diǎn)的信息，然后就是下一跳的信息，這時(shí)，線索的威力就發(fā)揮出來(lái)了。
// 以 $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í)候，我們沒(méi)有用一個(gè)遞歸吧，全部是使用的 while() 和 for() 就完成了對(duì)這個(gè)線索二叉樹的遍歷。
堅(jiān)持到現(xiàn)在不容易，不能再小看數(shù)據(jù)結(jié)構(gòu)了吧？現(xiàn)在還只是樹，我們的圖都還沒(méi)開始呢！當(dāng)然，也不要害怕，一步一步的學(xué)，慢慢掌握，不要幻想一口氣吃成個(gè)胖子。寫完這篇文章我也不可能馬上就手寫出一個(gè)中序的線索二叉樹來(lái)的。大家還是以理解原理為主，如果說(shuō)真能手寫的話，那也是為了面試而去背的或者是為了考研而準(zhǔn)備的。這樣的小同學(xué)在面試中我反而要更多問(wèn)一些其它的問(wèn)題，畢竟臨時(shí)抱佛腳的準(zhǔn)備遠(yuǎn)不如深入理解帶來(lái)的感悟更能打動(dòng)人！
測(cè)試代碼：
https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/4.樹/source/4.3完全二叉樹、線索二叉樹及樹的順序存儲(chǔ)結(jié)構(gòu).php
關(guān)于完全二叉樹和線索二叉樹是什么問(wèn)題的解答就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，如果你還有很多疑惑沒(méi)有解開，可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道了解更多相關(guān)知識(shí)。
