【原】PHP數(shù)據(jù)結(jié)構(gòu)-二叉樹的遍歷及邏輯操作

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

展開全文

二叉樹的遍歷及邏輯操作

上篇文章我們講了許多理論方面的知識(shí)，雖說很枯燥，但那些都是我們今天學(xué)習(xí)的前提，一會(huì)看代碼的時(shí)候你就會(huì)發(fā)現(xiàn)這些理論知識(shí)是多么地重要了。首先，我們還是要說明一下，我們學(xué)習(xí)的主要內(nèi)容是二叉樹，因?yàn)槎鏄涫亲畹湫偷囊环N樹的應(yīng)用，不管是考試還是面試，它都是必知必學(xué)的內(nèi)容。

首先，在學(xué)習(xí)樹的操作之前，我們先要明白在樹的操作中，最核心的就是“遍歷”。為什么這么說呢？不同于棧和隊(duì)列，樹結(jié)構(gòu)其實(shí)已經(jīng)不是一維的了，它有分支，有不同的角度，更重要的是它有了層級(jí)的概念。一維空間的東西就是我們常見的“線”，它只有長度，沒有高度，而這個(gè)長度就是它唯一的維度，棧和隊(duì)列很明顯都是一維的。而樹就不同了，因?yàn)閷蛹?jí)的概念，所以它有了“高度”，也就是說，它升級(jí)到了二維的概念。就像上一篇文章中介紹的那一堆名詞中，就有“樹的高度（深度）”的概念。

能夠遍歷一顆樹之后，我們就可以在遍歷的基礎(chǔ)上對(duì)這顆樹的結(jié)點(diǎn)進(jìn)行增、刪、改等操作，這些基本的邏輯操作全都是建立在遍歷的基礎(chǔ)之上的，仔細(xì)回想一下棧和隊(duì)列，其實(shí)它們的這些邏輯操作不也是從遍歷入手嗎？不管是出棧入棧還是出隊(duì)入隊(duì)，我們都是建立在一種固定的遍歷規(guī)則之下的（FILO、FIFO）。

對(duì)于二維的事物，如何遍歷它就是一個(gè)重點(diǎn)的內(nèi)容。一維的數(shù)據(jù)結(jié)構(gòu)我們只要順序地去遍歷就可以了，而二維的數(shù)據(jù)結(jié)果則不能簡單的按順序一個(gè)一個(gè)地去遍歷了，因?yàn)榻Y(jié)點(diǎn)之間有層次關(guān)系的存在，所以我們要考慮當(dāng)前的結(jié)點(diǎn)如果沒有子結(jié)點(diǎn)了，我們的遍歷操作應(yīng)該怎么辦呢？

幸好，我們是站在巨人的肩膀上來學(xué)習(xí)這些知識(shí)。許多的前輩已經(jīng)為我們總結(jié)出來了一些非常簡單的對(duì)于樹的遍歷方法，有多簡單呢？先賣個(gè)關(guān)子，我們先來看看如何建立一顆樹，也就是我們在上篇文章中展示過的那顆二叉樹。

二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

使用鏈?zhǔn)酱鎯?chǔ)二叉樹非常簡單，而且也很形象，小伙伴們先收起對(duì)順序存儲(chǔ)二叉樹的疑問，因?yàn)樵谙乱黄恼轮形覀兙蜁?huì)講解在什么情況下使用順序存儲(chǔ)。

class BiTree
{
    public $data;
    public $lChild;
    public $rChild;
}

其實(shí)，在鏈?zhǔn)酱鎯?chǔ)中，我們就是使用一個(gè)個(gè)地結(jié)點(diǎn)來保存這顆樹。每個(gè)二叉樹結(jié)點(diǎn)都有一個(gè)數(shù)據(jù)域，也就是 data 屬性。另外兩個(gè)屬性就可以看做是兩個(gè)分叉的指針，分別是這個(gè)結(jié)點(diǎn)的左孩子結(jié)點(diǎn) lChild 和右孩子結(jié)點(diǎn) rChild 。對(duì)比棧和隊(duì)列來說，我們只是將 next 結(jié)點(diǎn)換成了左、右兩個(gè)孩子結(jié)點(diǎn)而已，本質(zhì)上其實(shí)與棧和隊(duì)列并沒有太大的差別。說白了，從數(shù)據(jù)結(jié)構(gòu)上來看，我們還是用一維的存儲(chǔ)來表示二維的概念，而這個(gè)概念的轉(zhuǎn)變則是我們需要從對(duì)概念理解的角度出發(fā)的。

二叉樹建樹

// 建立二叉樹
function CreateBiTree($arr, $i)
{
    if (!isset($arr[$i])) {
        return null;
    }
    $t = new BiTree();
    $t->data = $arr[$i];
    $t->lChild = CreateBiTree($arr, $i * 2);
    $t->rChild = CreateBiTree($arr, $i * 2 + 1);
    return $t;
}

就這么一個(gè)簡單的方法，我們就可以完成一個(gè)鏈?zhǔn)蕉鏄涞慕?。小伙伴們?qǐng)仔細(xì)看好了，這一個(gè)簡單的建樹操作其實(shí)內(nèi)含不少玄機(jī)：

我們使用一個(gè)數(shù)組來依次表示樹的各個(gè)結(jié)點(diǎn)，比如依次輸入 A 、 B 、 C 、 D 、 E …… （樹的順序存儲(chǔ)中我們會(huì)再次看到它們的身影）
賦值的內(nèi)容是當(dāng)前 $i 下標(biāo)的數(shù)據(jù)，注意我們在給左、右孩子賦值時(shí)進(jìn)行了遞歸操作
在學(xué)習(xí)棧的時(shí)候，我們學(xué)習(xí)過“遞歸”就是一種棧式的操作，所以，在這段代碼中，我們是以棧的形式來建樹的
注意到每次的 i * 2 和 i * 2 + 1 了吧？請(qǐng)復(fù)習(xí)二叉樹的性質(zhì)5

最后我們測試一下這個(gè)方法是否能夠成功的建立一顆鏈?zhǔn)綐浣Y(jié)構(gòu)。

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

$tree = CreateBiTree($treeList, 1);
print_r($tree);

// BiTree Object
// (
//     [data] => A
//     [lChild] => BiTree Object
//         (
//             [data] => B
//             [lChild] => BiTree Object
//                 (
//                     [data] => D
//                     [lChild] => BiTree Object
//                         (
//                             [data] => H
//                             [lChild] =>
//                             [rChild] =>
//                         )

//                     [rChild] => BiTree Object
//                         (
//                             [data] => I
//                             [lChild] =>
//                             [rChild] =>
//                         )

//                 )

//             [rChild] => BiTree Object
//                 (
//                     [data] => E
//                     [lChild] => BiTree Object
//                         (
//                             [data] => J
//                             [lChild] =>
//                             [rChild] =>
//                         )

//                     [rChild] => BiTree Object
//                         (
//                             [data] => K
//                             [lChild] =>
//                             [rChild] =>
//                         )

//                 )

//         )

//     [rChild] => BiTree Object
//         (
//             [data] => C
//             [lChild] => BiTree Object
//                 (
//                     [data] => F
//                     [lChild] => BiTree Object
//                         (
//                             [data] => L
//                             [lChild] =>
//                             [rChild] =>
//                         )

//                     [rChild] => BiTree Object
//                         (
//                             [data] => M
//                             [lChild] =>
//                             [rChild] =>
//                         )

//                 )

//             [rChild] => BiTree Object
//                 (
//                     [data] => G
//                     [lChild] => BiTree Object
//                         (
//                             [data] => N
//                             [lChild] =>
//                             [rChild] =>
//                         )

//                     [rChild] => BiTree Object
//                         (
//                             [data] => O
//                             [lChild] =>
//                             [rChild] =>
//                         )

//                 )

//         )

// )

打印出來的內(nèi)容應(yīng)該非常清晰了吧？A 結(jié)點(diǎn)有左右兩個(gè)孩子結(jié)點(diǎn)分別是 B 和 C ，B 結(jié)點(diǎn)有左右兩個(gè)孩子分別是 D 和 E ，依次類推。最終的結(jié)構(gòu)和我們上面那個(gè)二叉樹圖的結(jié)構(gòu)完全一致。在這里，我們還需要注意的一點(diǎn)是，對(duì)于傳遞進(jìn)來的數(shù)組，我們給第一個(gè)元素，也就是 0 下標(biāo)的數(shù)據(jù)為空，并且是從第二個(gè)元素也就是 1 下標(biāo)的元素開始建樹的。這樣也是為了能夠直觀方便的利用二叉樹的性質(zhì)5 來快速地建立這顆樹。

二叉樹的遍歷

說完二叉樹的建樹了，其實(shí)我們就已經(jīng)接觸到了一種二叉樹的遍歷形式。注意看我們建樹方法中的代碼，我們是先給結(jié)點(diǎn)的 data 賦值，然后建立這個(gè)結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)，并為它們賦值后再繼續(xù)使用同樣的操作一路建立完成所有的結(jié)點(diǎn)?，F(xiàn)在，我們將這個(gè)操作反過來，不是建立結(jié)點(diǎn)，而是讀取這些結(jié)點(diǎn)的內(nèi)容，先讀取結(jié)點(diǎn)的內(nèi)容，然后再讀取這個(gè)結(jié)點(diǎn)左右孩子結(jié)點(diǎn)的內(nèi)容，這就是“先序遍歷”。

先序遍歷

/**
 * 前序遍歷
 */
function PreOrderTraverse(?BiTree $t)
{
    if ($t) {
        echo $t->data, ',';
        PreOrderTraverse($t->lChild);
        PreOrderTraverse($t->rChild);
    }
}

PreOrderTraverse($tree);

// A,B,D,H,I,E,J,K,C,F,L,M,G,N,O,

是不是很神奇？就連建樹我們竟然也使用的是同一種遍歷的方法，可以看出對(duì)于二叉樹這種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)來說，遍歷的重要作用了吧。

大家可以看一個(gè)遍歷讀取出來的結(jié)點(diǎn)順序，貌似和我們輸入的順序不一樣呀！沒錯(cuò)，先序遍歷是通過遞歸，先按一個(gè)方向走到底，當(dāng)這個(gè)結(jié)點(diǎn)沒有子結(jié)點(diǎn)之后，通過遞歸棧的特性再向上彈出。并且在遍歷孩子結(jié)點(diǎn)之前先輸出當(dāng)前這個(gè)結(jié)點(diǎn)的內(nèi)容。注意，這一句話很重要！所以我們的順序就是 A,B,D,H ，當(dāng) H 沒有子結(jié)點(diǎn)之后，我們就回到父結(jié)點(diǎn) D 再進(jìn)入它的右子結(jié)點(diǎn) I ，具體順序可以參考下圖：

我們代碼中的先序遍歷和先序建樹的結(jié)點(diǎn)順序是完全不一樣的，這一點(diǎn)也是要搞清楚的。建樹的過程我們根據(jù)二叉樹的性質(zhì)5 直接為它指定了數(shù)據(jù)下標(biāo)。而在遍歷過程中則是一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)的去掃描遍歷整顆樹的。

中序遍歷

顧名思義，中序遍歷其實(shí)就是在遍歷完左孩子結(jié)點(diǎn)之后再輸出當(dāng)前這個(gè)結(jié)點(diǎn)的內(nèi)容，所以我們只需要微調(diào)先序遍歷的代碼即可。

/**
 * 中序遍歷
 */
function InOrderTraverse(?BiTree $t)
{
    if ($t) {
        InOrderTraverse($t->lChild);
        echo $t->data, ',';
        InOrderTraverse($t->rChild);
    }
}

InOrderTraverse($tree);

// H,D,I,B,J,E,K,A,L,F,M,C,N,G,O,

中序遍歷的步驟就是我們會(huì)直接先走到最左邊的子結(jié)點(diǎn)，當(dāng)遇到最后一個(gè)結(jié)點(diǎn)時(shí)，輸出內(nèi)容，也就是圖中的 H 結(jié)點(diǎn)，接著回到它的父結(jié)點(diǎn) D 結(jié)點(diǎn)，這時(shí)根據(jù)中序的原理輸出 D ，再進(jìn)入它的右孩子結(jié)點(diǎn)并輸出 I 。D 結(jié)點(diǎn)的子樹及它本身遍歷完成后，返回 D 結(jié)點(diǎn)的上級(jí)結(jié)點(diǎn) B 結(jié)點(diǎn)，輸出 B ，然后進(jìn)入 B 結(jié)點(diǎn)的右孩子結(jié)點(diǎn) E 。再次進(jìn)入到 E 的最左孩子結(jié)點(diǎn) J ，然后參考 D 結(jié)點(diǎn)的遍歷形式完成整顆樹的遍歷。具體順序參考下圖：

后序遍歷

在學(xué)習(xí)了先序和中序之后，從名字就可以看出來后序就是在遍歷完一個(gè)結(jié)點(diǎn)的左右孩子之后最后輸出這個(gè)結(jié)點(diǎn)的內(nèi)容，代碼當(dāng)然也是簡單地微調(diào)一下就可以了。

/**
 * 后序遍歷
 */
function PostOrderTraverse(?BiTree $t)
{
    if ($t) {
        PostOrderTraverse($t->lChild);
        PostOrderTraverse($t->rChild);
        echo $t->data, ',';
    }
}

PostOrderTraverse($tree);

// H,I,D,J,K,E,B,L,M,F,N,O,G,C,A,

具體原理就不詳細(xì)說明了，相信在學(xué)習(xí)了先序和中序之后，你一定能馬上想明白后序遍歷到底是什么意思了。直接上圖：

層序遍歷

最后，我們要講的就是層序遍歷。既然有“層”這個(gè)關(guān)鍵字了，相信大家馬上就能聯(lián)想到，是不是一層一層地去遍歷啊！沒錯(cuò)，層序遍歷就是這個(gè)意思，我們按照樹的層次，一層一層地輸出相應(yīng)的結(jié)點(diǎn)信息。需要注意的，在這里我們會(huì)用到隊(duì)列，而不是棧了。

/**
 * 層序遍歷
 */
$q = InitLinkQueue();
function LevelOrderTraverse(?BiTree $t)
{
    global $q;
    if (!$t) {
        return;
    }

    EnLinkQueue($q, $t);
    $node = $q;
    while ($node) {
        $node = DeLinkQueue($q);
        if ($node->lChild) {
            EnLinkQueue($q, $node->lChild);
        }
        if ($node->rChild) {
            EnLinkQueue($q, $node->rChild);
        }
        echo $node->data, ',';
    }
}

LevelOrderTraverse($tree);

// A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,

InitLinkQueue() EnLinkQueue() 、 EnLinkQueue() 這些都是我們之前學(xué)習(xí)隊(duì)列的時(shí)候所寫的對(duì)于隊(duì)列的邏輯操作方法。是不是很開心呀，之前的知識(shí)又用上了。層序遍歷的核心思想就是運(yùn)用隊(duì)列的概念，遇到一個(gè)結(jié)點(diǎn)，就把這個(gè)結(jié)點(diǎn)入隊(duì)，然后判斷它是否有子結(jié)點(diǎn)，然后相繼把子結(jié)點(diǎn)入隊(duì)。每遍歷一個(gè)結(jié)點(diǎn)，就把隊(duì)首的結(jié)點(diǎn)出隊(duì)，這樣就完成了按樹的層次遍歷的能力。文字說明還是太抽象，我們還是通過圖片來展示這一過程：

大家有沒有發(fā)現(xiàn)，層序遍歷的輸出結(jié)果就和我們建樹時(shí)的數(shù)組順序完全相同了。很好玩吧，所以說代碼的世界總是有無窮的樂趣等著我們?nèi)グl(fā)現(xiàn)哦！

總結(jié)

今天的內(nèi)容有沒有懵圈？如果懵圈了就多找資料好好研究一下，先序、中序、后序都是利用棧來進(jìn)行樹的結(jié)點(diǎn)遍歷的，而層序遍歷則是利用了隊(duì)列。一環(huán)套一環(huán)呀，前面學(xué)習(xí)的內(nèi)容都派上用場了吧！不過這只是個(gè)開始，在學(xué)習(xí)圖的時(shí)候，我們會(huì)在深度遍歷和廣度遍歷中再次看到棧和隊(duì)列的身影，它們可都是親戚哦。

這四種遍歷方式在考試和面試中也是經(jīng)常出現(xiàn)的，不管是它們的原理還是畫圖或者是根據(jù)圖形來寫出各種遍歷的順序，都是非常常見的考核內(nèi)容，所以大家在這篇文章入門的基礎(chǔ)上還是要更加深入的去根據(jù)一些教材來深入的理解這幾種遍歷，熟練的掌握它們。

測試代碼：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/4.樹/source/4.2二叉樹的遍歷及邏輯操作.php

參考資料：

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

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

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