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

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

展開全文

二叉樹的遍歷及邏輯操作

上篇文章我們講了許多理論方面的知識，雖說很枯燥，但那些都是我們今天學(xué)習的前提，一會看代碼的時候你就會發(fā)現(xiàn)這些理論知識是多么地重要了。首先，我們還是要說明一下，我們學(xué)習的主要內(nèi)容是二叉樹，因為二叉樹是最典型的一種樹的應(yīng)用，不管是考試還是面試，它都是必知必學(xué)的內(nèi)容。

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

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

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

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

二叉樹的鏈式存儲結(jié)構(gòu)

使用鏈式存儲二叉樹非常簡單，而且也很形象，小伙伴們先收起對順序存儲二叉樹的疑問，因為在下一篇文章中我們就會講解在什么情況下使用順序存儲。

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

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

就這么一個簡單的方法，我們就可以完成一個鏈式二叉樹的建立。小伙伴們請仔細看好了，這一個簡單的建樹操作其實內(nèi)含不少玄機：

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

最后我們測試一下這個方法是否能夠成功的建立一顆鏈式樹結(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é)點有左右兩個孩子結(jié)點分別是 B 和 C ，B 結(jié)點有左右兩個孩子分別是 D 和 E ，依次類推。最終的結(jié)構(gòu)和我們上面那個二叉樹圖的結(jié)構(gòu)完全一致。在這里，我們還需要注意的一點是，對于傳遞進來的數(shù)組，我們給第一個元素，也就是 0 下標的數(shù)據(jù)為空，并且是從第二個元素也就是 1 下標的元素開始建樹的。這樣也是為了能夠直觀方便的利用二叉樹的性質(zhì)5 來快速地建立這顆樹。

二叉樹的遍歷

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

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

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

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

中序遍歷

顧名思義，中序遍歷其實就是在遍歷完左孩子結(jié)點之后再輸出當前這個結(jié)點的內(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,

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

后序遍歷

在學(xué)習了先序和中序之后，從名字就可以看出來后序就是在遍歷完一個結(jié)點的左右孩子之后最后輸出這個結(jié)點的內(nèi)容，代碼當然也是簡單地微調(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,

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

層序遍歷

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

/**
 * 層序遍歷
 */
$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é)習隊列的時候所寫的對于隊列的邏輯操作方法。是不是很開心呀，之前的知識又用上了。層序遍歷的核心思想就是運用隊列的概念，遇到一個結(jié)點，就把這個結(jié)點入隊，然后判斷它是否有子結(jié)點，然后相繼把子結(jié)點入隊。每遍歷一個結(jié)點，就把隊首的結(jié)點出隊，這樣就完成了按樹的層次遍歷的能力。文字說明還是太抽象，我們還是通過圖片來展示這一過程：

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

總結(jié)

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

這四種遍歷方式在考試和面試中也是經(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)》第二版，嚴蔚敏

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

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