溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容主要講解“php二叉樹的遍歷以及進行邏輯操作的方法介紹”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“php二叉樹的遍歷以及進行邏輯操作的方法介紹”吧!
首先，我們還是要說明一下，我們學習的主要內容是二叉樹，因為二叉樹是最典型的一種樹的應用，不管是考試還是面試，它都是必知必學的內容。
首先，在學習樹的操作之前，我們先要明白在樹的操作中，最核心的就是“遍歷”。為什么這么說呢？不同于棧和隊列，樹結構其實已經不是一維的了，它有分支，有不同的角度，更重要的是它有了層級的概念。
一維空間的東西就是我們常見的“線”，它只有長度，沒有高度，而這個長度就是它唯一的維度，棧和隊列很明顯都是一維的。而樹就不同了，因為層級的概念，所以它有了“高度”，也就是說，它升級到了二維的概念。就像上一篇文章中介紹的那一堆名詞中，就有“樹的高度（深度）”的概念。
能夠遍歷一顆樹之后，我們就可以在遍歷的基礎上對這顆樹的結點進行增、刪、改等操作，這些基本的邏輯操作全都是建立在遍歷的基礎之上的，仔細回想一下棧和隊列，其實它們的這些邏輯操作不也是從遍歷入手嗎？不管是出棧入棧還是出隊入隊，我們都是建立在一種固定的遍歷規則之下的（FILO、FIFO）。
對于二維的事物，如何遍歷它就是一個重點的內容。一維的數據結構我們只要順序地去遍歷就可以了，而二維的數據結果則不能簡單的按順序一個一個地去遍歷了，因為結點之間有層次關系的存在，所以我們要考慮當前的結點如果沒有子結點了，我們的遍歷操作應該怎么辦呢？
幸好，我們是站在巨人的肩膀上來學習這些知識。許多的前輩已經為我們總結出來了一些非常簡單的對于樹的遍歷方法，有多簡單呢？先賣個關子，我們先來看看如何建立一顆樹，也就是我們在上篇文章中展示過的那顆二叉樹。
使用鏈式存儲二叉樹非常簡單，而且也很形象，小伙伴們先收起對順序存儲二叉樹的疑問，因為在下一篇文章中我們就會講解在什么情況下使用順序存儲。
class BiTree
{
public $data;
public $lChild;
public $rChild;
}其實，在鏈式存儲中，我們就是使用一個個地結點來保存這顆樹。每個二叉樹結點都有一個數據域，也就是 data 屬性。另外兩個屬性就可以看做是兩個分叉的指針，分別是這個結點的左孩子結點 lChild 和右孩子結點 rChild 。
對比棧和隊列來說，我們只是將 next 結點換成了左、右兩個孩子結點而已，本質上其實與棧和隊列并沒有太大的差別。說白了，從數據結構上來看，我們還是用一維的存儲來表示二維的概念，而這個概念的轉變則是我們需要從對概念理解的角度出發的。
// 建立二叉樹
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;
}就這么一個簡單的方法，我們就可以完成一個鏈式二叉樹的建立。小伙伴們請仔細看好了，這一個簡單的建樹操作其實內含不少玄機：
我們使用一個數組來依次表示樹的各個結點，比如依次輸入 A 、 B 、 C 、 D 、 E …… （樹的順序存儲中我們會再次看到它們的身影）
賦值的內容是當前 $i 下標的數據，注意我們在給左、右孩子賦值時進行了遞歸操作
在學習棧的時候，我們學習過“遞歸”就是一種棧式的操作，所以，在這段代碼中，我們是以棧的形式來建樹的
注意到每次的 i 2 和 i 2 + 1 了吧？請復習二叉樹的 性質5
最后我們測試一下這個方法是否能夠成功的建立一顆鏈式樹結構。
$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] => // ) // ) // ) // )
打印出來的內容應該非常清晰了吧？A 結點有左右兩個孩子結點分別是 B 和 C ，B 結點有左右兩個孩子分別是 D 和 E ，依次類推。最終的結構和我們上面那個二叉樹圖的結構完全一致。在這里，我們還需要注意的一點是，對于傳遞進來的數組，我們給第一個元素，也就是 0 下標的數據為空，并且是從第二個元素也就是 1 下標的元素開始建樹的。這樣也是為了能夠直觀方便的利用二叉樹的 性質5 來快速地建立這顆樹。
說完二叉樹的建樹了，其實我們就已經接觸到了一種二叉樹的遍歷形式。注意看我們建樹方法中的代碼，我們是先給結點的 data 賦值，然后建立這個結點的左、右孩子結點，并為它們賦值后再繼續使用同樣的操作一路建立完成所有的結點。現在，我們將這個操作反過來，不是建立結點，而是讀取這些結點的內容，先讀取結點的內容，然后再讀取這個結點左右孩子結點的內容，這就是“先序遍歷”。
先序遍歷
/**
* 前序遍歷
*/
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,是不是很神奇？就連建樹我們竟然也使用的是同一種遍歷的方法，可以看出對于二叉樹這種復雜的數據結構來說，遍歷的重要作用了吧。
大家可以看一個遍歷讀取出來的結點順序，貌似和我們輸入的順序不一樣呀！沒錯，先序遍歷是通過遞歸，先按一個方向走到底，當這個結點沒有子結點之后，通過遞歸棧的特性再向上彈出。并且在遍歷孩子結點之前先輸出當前這個結點的內容。注意，這一句話很重要！所以我們的順序就是 A,B,D,H ，當 H 沒有子結點之后，我們就回到父結點 D 再進入它的右子結點 I ，具體順序可以參考下圖：
我們代碼中的先序遍歷和先序建樹的結點順序是完全不一樣的，這一點也是要搞清楚的。建樹的過程我們根據二叉樹的 性質5 直接為它指定了數據下標。而在遍歷過程中則是一個結點一個結點的去掃描遍歷整顆樹的。
中序遍歷
顧名思義，中序遍歷其實就是在遍歷完左孩子結點之后再輸出當前這個結點的內容，所以我們只需要微調先序遍歷的代碼即可。
/**
* 中序遍歷
*/
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,中序遍歷的步驟就是我們會直接先走到最左邊的子結點，當遇到最后一個結點時，輸出內容，也就是圖中的 H 結點，接著回到它的父結點 D 結點，這時根據中序的原理輸出 D ，再進入它的右孩子結點并輸出 I 。
D 結點的子樹及它本身遍歷完成后，返回 D 結點的上級結點 B 結點，輸出 B ，然后進入 B 結點的右孩子結點 E 。再次進入到 E 的最左孩子結點 J ，然后參考 D 結點的遍歷形式完成整顆樹的遍歷。具體順序參考下圖：
后序遍歷
在學習了先序和中序之后，從名字就可以看出來后序就是在遍歷完一個結點的左右孩子之后最后輸出這個結點的內容，代碼當然也是簡單地微調一下就可以了。
/**
* 后序遍歷
*/
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,具體原理就不詳細說明了，相信在學習了先序和中序之后，你一定能馬上想明白后序遍歷到底是什么意思了。直接上圖：
層序遍歷
最后，我們要講的就是層序遍歷。既然有“層”這個關鍵字了，相信大家馬上就能聯想到，是不是一層一層地去遍歷啊！沒錯，層序遍歷就是這個意思，我們按照樹的層次，一層一層地輸出相應的結點信息。需要注意的，在這里我們會用到隊列，而不是棧了。
/**
* 層序遍歷
*/
$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() 這些都是我們之前學習隊列的時候所寫的對于隊列的邏輯操作方法。是不是很開心呀，之前的知識又用上了。層序遍歷的核心思想就是運用隊列的概念，遇到一個結點，就把這個結點入隊，然后判斷它是否有子結點，然后相繼把子結點入隊。
每遍歷一個結點，就把隊首的結點出隊，這樣就完成了按樹的層次遍歷的能力。文字說明還是太抽象，我們還是通過圖片來展示這一過程：
大家有沒有發現，層序遍歷的輸出結果就和我們建樹時的數組順序完全相同了。很好玩吧，所以說代碼的世界總是有無窮的樂趣等著我們去發現哦！
今天的內容有沒有懵圈？如果懵圈了就多找資料好好研究一下，先序、中序、后序都是利用棧來進行樹的結點遍歷的，而層序遍歷則是利用了隊列。一環套一環呀，前面學習的內容都派上用場了吧！不過這只是個開始，在學習圖的時候，我們會在深度遍歷和廣度遍歷中再次看到棧和隊列的身影，它們可都是親戚哦。
這四種遍歷方式在考試和面試中也是經常出現的，不管是它們的原理還是畫圖或者是根據圖形來寫出各種遍歷的順序，都是非常常見的考核內容，所以大家在這篇文章入門的基礎上還是要更加深入的去根據一些教材來深入的理解這幾種遍歷，熟練的掌握它們。
測試代碼：
https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/4.樹/source/4.2二叉樹的遍歷及邏輯操作.php
到此，相信大家對“php二叉樹的遍歷以及進行邏輯操作的方法介紹”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
