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

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

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

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

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

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

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

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

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

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

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

A在0層

B，C和D是1層

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

K，L，M都在第3層。

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

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

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

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

遍歷：這表示按特定順序訪問節(jié)點的過程。

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

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

class TreeNode
{
    public $data = null;

    public $children = [];

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

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

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

現(xiàn)在，我們有了節(jié)點，讓我們構(gòu)建一個樹結(jié)構(gòu)，它將定義樹的根節(jié)點，也可以遍歷整個樹。因此，基本樹結(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);
            }
        }
    }
}

前面的代碼顯示了一個簡單的樹類，我們可以存儲根節(jié)點引用，也可以從任意節(jié)點遍歷樹。在遍歷部分中，我們訪問每個子節(jié)點，然后立即遞歸調(diào)用遍歷方法來獲取當(dāng)前節(jié)點的子節(jié)點。我們通過一個level，在節(jié)點名稱的開頭打印出一個破折號（-），這樣我們就可以很容易地理解子級數(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é)果類似這樣，完整的代碼可以在這里看到

在代碼世界中有很多不同類型的樹，我們一起來看下。

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

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

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

高度平衡的二叉樹總是更好的選擇，因為它比常規(guī)BST有助于更快地搜索操作。自平衡或高度平衡二叉搜索樹有不同的實現(xiàn)。一些常見到的如下：

AA樹

AVL樹

紅黑樹

替罪羊樹

八叉樹

2-3樹

Treap

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

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