摘要：每個(gè)節(jié)點(diǎn)都必須滿足這個(gè)屬性，這就是二叉搜索樹(shù)。自平衡二叉樹(shù)自平衡二叉搜索樹(shù)或高度平衡二叉搜索樹(shù)是一種特殊類型的二叉搜索樹(shù)，它試圖通過(guò)自動(dòng)調(diào)整來(lái)盡量保持樹(shù)的高度或?qū)哟伪M可能小。自平衡或高度平衡二叉搜索樹(shù)有不同的實(shí)現(xiàn)。

迄今為止，我們對(duì)數(shù)據(jù)結(jié)構(gòu)的探索僅觸及線性部分。無(wú)論我們使用數(shù)組、鏈表、棧還是隊(duì)列，都是線性數(shù)據(jù)結(jié)構(gòu)。我們已經(jīng)看到了線性數(shù)據(jù)結(jié)構(gòu)操作的復(fù)雜性，大多數(shù)時(shí)候，插入和刪除的復(fù)雜度可以用O(1)來(lái)表示。搜索有點(diǎn)復(fù)雜，需要O(n)復(fù)雜度。唯一的例外是PHP數(shù)組，它實(shí)際上是哈希表，如果索引或鍵在這樣的以這樣的方式管理，則可以達(dá)到O(1)的復(fù)雜度。為了解決這個(gè)問(wèn)題，我們可以使用分層數(shù)據(jù)結(jié)構(gòu)，而不是線性數(shù)據(jù)結(jié)構(gòu)。分層數(shù)據(jù)可以很好地解決線性數(shù)據(jù)結(jié)構(gòu)難以解決的許多問(wèn)題。

每當(dāng)我們談?wù)摷彝プ遄V、組織結(jié)構(gòu)和網(wǎng)絡(luò)連接圖時(shí)，我們實(shí)際上都在談?wù)摲謱訑?shù)據(jù)。樹(shù)是一種特殊的抽象數(shù)據(jù)類型（ADT）。不同于鏈表，樹(shù)是分層的。

樹(shù)是由邊連接的節(jié)點(diǎn)或頂點(diǎn)的分層集合。樹(shù)不能有循環(huán)，并且只有節(jié)點(diǎn)和它的下降節(jié)點(diǎn)或子節(jié)點(diǎn)之間存在邊。同一父級(jí)的兩個(gè)子節(jié)點(diǎn)在它們之間不能有任何邊。每個(gè)節(jié)點(diǎn)可以有一個(gè)父節(jié)點(diǎn)除非是頂部節(jié)點(diǎn)，也稱為根節(jié)點(diǎn)。每棵樹(shù)只能有一個(gè)根節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)可以有零個(gè)或多個(gè)子節(jié)點(diǎn)。在下面的圖中，A是根節(jié)點(diǎn)，B、C和D是A的子節(jié)點(diǎn)。我們也可以說(shuō)，A是B、C、D的父節(jié)點(diǎn)。B、C和D被稱為兄弟姐妹，因?yàn)樗鼈兪莵?lái)自同一父節(jié)點(diǎn)A。

沒(méi)有任何子節(jié)點(diǎn)的節(jié)點(diǎn)稱為葉子。在前面的圖中，K、L、F、G、M、I和J是葉子節(jié)點(diǎn)。葉子節(jié)點(diǎn)也稱為外部節(jié)點(diǎn)或終端節(jié)點(diǎn)。除根以外的節(jié)點(diǎn)具有至少一個(gè)子節(jié)點(diǎn)，稱為內(nèi)部節(jié)點(diǎn)。這里，B、C、D、E和H是內(nèi)部節(jié)點(diǎn)。這里是一些其他常用的術(shù)語(yǔ)，用于描述樹(shù)的數(shù)據(jù)結(jié)構(gòu)：

后裔：這是一個(gè)可以通過(guò)重復(fù)的程序從父節(jié)點(diǎn)到達(dá)的節(jié)點(diǎn)。例如，M是前一個(gè)圖中C的后裔。

祖先：這是一個(gè)可以通過(guò)重復(fù)方式從子節(jié)點(diǎn)到達(dá)父節(jié)點(diǎn)的節(jié)點(diǎn)。例如，B是L的祖先。

度：特定父節(jié)點(diǎn)的子節(jié)點(diǎn)的總數(shù)被稱為它的度數(shù)。在我們的例子中，A有3度，B有1度，C有度3，D有度2。

路徑：從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn)和邊的序列稱為兩個(gè)節(jié)點(diǎn)之間的路徑。路徑的長(zhǎng)度是路徑中節(jié)點(diǎn)的數(shù)目。A到M之間的路徑是A-C-H-M，路徑的長(zhǎng)度為4。

節(jié)點(diǎn)的高度：節(jié)點(diǎn)的高度由節(jié)點(diǎn)與最深節(jié)點(diǎn)之間的邊數(shù)決定。例如，節(jié)點(diǎn)B的高度為2。

層次：層次代表節(jié)點(diǎn)的生成。如果父節(jié)點(diǎn)處于層次N，則其子節(jié)點(diǎn)將位于N+ 1層次。因此，該層次由節(jié)點(diǎn)和根之間的邊數(shù)定義。

A在0層

B，C和D是1層

E，F(xiàn)，G，H，I，J是2層

K，L，M都在第3層。

樹(shù)的高度：樹(shù)的高度是由它的根節(jié)點(diǎn)的高度定義的。上圖樹(shù)的高度是3。

子樹(shù)：在樹(shù)結(jié)構(gòu)中，每個(gè)孩子遞歸地形成子樹(shù)。換句話說(shuō)，樹(shù)由許多子樹(shù)組成。例如，B和E、K和L構(gòu)成了一個(gè)子樹(shù)，E、K和 L構(gòu)成了一個(gè)子樹(shù)，每個(gè)不同的陰影中都對(duì)它們進(jìn)行了識(shí)別。

深度：節(jié)點(diǎn)的深度由節(jié)點(diǎn)和根節(jié)點(diǎn)之間的邊數(shù)決定。例如，H的深度是2，L的深度是3。

森林：森林是由一組或更多的不相交的樹(shù)組成。

遍歷：這表示按特定順序訪問(wèn)節(jié)點(diǎn)的過(guò)程。

鍵：用于搜索，表示節(jié)點(diǎn)的值。

到目前為止，我們已經(jīng)了解了樹(shù)的不同屬性。如果我們對(duì)比樹(shù)和現(xiàn)實(shí)的例子，我們發(fā)現(xiàn)組織結(jié)構(gòu)或族譜樹(shù)可以用數(shù)表示。對(duì)于一個(gè)組織結(jié)構(gòu)，有一個(gè)根節(jié)點(diǎn)可以是公司的CEO，其次是CXO級(jí)別的員工，其次是其他級(jí)別的員工。這里，我們不限制特定節(jié)點(diǎn)的任何度。這意味著一個(gè)節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)。因此，下面是一個(gè)節(jié)點(diǎn)結(jié)構(gòu)，我們可以定義節(jié)點(diǎn)屬性、它的父節(jié)點(diǎn)和它的子節(jié)點(diǎn)：

class TreeNode
{
    public $data = null;

    public $children = [];

    public function __construct(string $data = null)
    {
        $this->data = $data;
    }

    public function addChildren(TreeNode $treeNode)
    {
        $this->children[] = $treeNode;
    }
}

我們可以看到我們聲明了兩個(gè)公共屬性分別為數(shù)據(jù)和孩子。我們還有一個(gè)方法將孩子添加到一個(gè)特定的節(jié)點(diǎn)。這里，我們只是在數(shù)組末尾添加新的子節(jié)點(diǎn)。樹(shù)是遞歸結(jié)構(gòu)，它將幫助我們遞歸地構(gòu)建樹(shù)，并遞歸地遍歷樹(shù)。

現(xiàn)在，我們有了節(jié)點(diǎn)，讓我們構(gòu)建一個(gè)樹(shù)結(jié)構(gòu)，它將定義樹(shù)的根節(jié)點(diǎn)，也可以遍歷整個(gè)樹(shù)。因此，基本樹(shù)結(jié)構(gòu)將是這樣的：

class Tree
{
    public $root = null;

    public function __construct(TreeNode $treeNode)
    {
        $this->root = $treeNode;
    }

    public function traverse(TreeNode $treeNode, int $level = 0)
    {
        if ($treeNode) {
            echo str_repeat("-", $level) . $treeNode->data . PHP_EOL;

            foreach ($treeNode->children as $child) {
                $this->traverse($child, $level + 1);
            }
        }
    }
}

前面的代碼顯示了一個(gè)簡(jiǎn)單的樹(shù)類，我們可以存儲(chǔ)根節(jié)點(diǎn)引用，也可以從任意節(jié)點(diǎn)遍歷樹(shù)。在遍歷部分中，我們?cè)L問(wèn)每個(gè)子節(jié)點(diǎn)，然后立即遞歸調(diào)用遍歷方法來(lái)獲取當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)。我們通過(guò)一個(gè)level，在節(jié)點(diǎn)名稱的開(kāi)頭打印出一個(gè)破折號(hào)（-），這樣我們就可以很容易地理解子級(jí)數(shù)據(jù)。

require "./TreeNode.php";

$ceo = new TreeNode("ceo");

$tree = new Tree($ceo);

$cfo = new TreeNode("cfo");
$cto = new TreeNode("cto");
$cmo = new TreeNode("cmo");
$coo = new TreeNode("coo");

$ceo->addChildren($cfo);
$ceo->addChildren($cto);
$ceo->addChildren($cmo);
$ceo->addChildren($coo);

$seniorArchitect = new TreeNode("Senior Architect");
$softwareEngineer = new TreeNode("SoftwareEngineer");

$userInterfaceDesigner = new TreeNode("userInterface Designer");
$qualityAssuranceEngineer = new TreeNode("qualityAssurance Engineer");


$cto->addChildren($seniorArchitect);
$seniorArchitect->addChildren($softwareEngineer);

$cto->addChildren($userInterfaceDesigner);
$cto->addChildren($qualityAssuranceEngineer);

$tree->traverse($tree->root);

最后輸出的結(jié)果類似這樣，完整的代碼可以在這里看到

在代碼世界中有很多不同類型的樹(shù)，我們一起來(lái)看下。

二叉樹(shù)是一種基本的樹(shù)結(jié)構(gòu)，二叉樹(shù)的每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子。

二叉搜索樹(shù)（BST）是一種特殊類型的二叉樹(shù)，其中節(jié)點(diǎn)以排序的方式存儲(chǔ)，即在任何給定的點(diǎn)上，節(jié)點(diǎn)值必須大于或等于左子節(jié)點(diǎn)值，小于右子節(jié)點(diǎn)值。每個(gè)節(jié)點(diǎn)都必須滿足這個(gè)屬性，這就是二叉搜索樹(shù)。二叉搜索樹(shù)算法總是優(yōu)于線性搜索(它的時(shí)間復(fù)雜度是O(n))，我們將在以后的內(nèi)容詳細(xì)解釋。

自平衡二叉搜索樹(shù)或高度平衡二叉搜索樹(shù)是一種特殊類型的二叉搜索樹(shù)，它試圖通過(guò)自動(dòng)調(diào)整來(lái)盡量保持樹(shù)的高度或?qū)哟伪M可能小。下圖左側(cè)的展示了二叉搜索樹(shù)，右邊的是自平衡二叉搜索樹(shù)：

高度平衡的二叉樹(shù)總是更好的選擇，因?yàn)樗瘸Ｒ?guī)BST有助于更快地搜索操作。自平衡或高度平衡二叉搜索樹(shù)有不同的實(shí)現(xiàn)。一些常見(jiàn)到的如下：

AA樹(shù)

AVL樹(shù)

紅黑樹(shù)

替罪羊樹(shù)

八叉樹(shù)

2-3樹(shù)

Treap

我們將在以后的內(nèi)容介紹他們，敬請(qǐng)期待吧。

PHP基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)專題系列目錄: 地址。主要使用PHP語(yǔ)法總結(jié)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和算法。還有我們?nèi)粘HP開(kāi)發(fā)中容易忽略的基礎(chǔ)知識(shí)和現(xiàn)代PHP開(kāi)發(fā)中關(guān)于規(guī)范、部署、優(yōu)化的一些實(shí)戰(zhàn)性建議，同時(shí)還有對(duì)Javascript語(yǔ)言特點(diǎn)的深入研究。