摘要：每個節點都必須滿足這個屬性，這就是二叉搜索樹。自平衡二叉樹自平衡二叉搜索樹或高度平衡二叉搜索樹是一種特殊類型的二叉搜索樹，它試圖通過自動調整來盡量保持樹的高度或層次盡可能小。自平衡或高度平衡二叉搜索樹有不同的實現。

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

每當我們談論家庭族譜、組織結構和網絡連接圖時，我們實際上都在談論分層數據。樹是一種特殊的抽象數據類型（ADT）。不同于鏈表，樹是分層的。

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

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

后裔：這是一個可以通過重復的程序從父節點到達的節點。例如，M是前一個圖中C的后裔。

祖先：這是一個可以通過重復方式從子節點到達父節點的節點。例如，B是L的祖先。

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

路徑：從源節點到目標節點的節點和邊的序列稱為兩個節點之間的路徑。路徑的長度是路徑中節點的數目。A到M之間的路徑是A-C-H-M，路徑的長度為4。

節點的高度：節點的高度由節點與最深節點之間的邊數決定。例如，節點B的高度為2。

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

A在0層

B，C和D是1層

E，F，G，H，I，J是2層

K，L，M都在第3層。

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

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

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

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

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

鍵：用于搜索，表示節點的值。

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

class TreeNode
{
    public $data = null;

    public $children = [];

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

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

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

現在，我們有了節點，讓我們構建一個樹結構，它將定義樹的根節點，也可以遍歷整個樹。因此，基本樹結構將是這樣的：

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);
            }
        }
    }
}

前面的代碼顯示了一個簡單的樹類，我們可以存儲根節點引用，也可以從任意節點遍歷樹。在遍歷部分中，我們訪問每個子節點，然后立即遞歸調用遍歷方法來獲取當前節點的子節點。我們通過一個level，在節點名稱的開頭打印出一個破折號（-），這樣我們就可以很容易地理解子級數據。

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);

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

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

二叉樹是一種基本的樹結構，二叉樹的每個節點最多有兩個孩子。

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

自平衡二叉搜索樹或高度平衡二叉搜索樹是一種特殊類型的二叉搜索樹，它試圖通過自動調整來盡量保持樹的高度或層次盡可能小。下圖左側的展示了二叉搜索樹，右邊的是自平衡二叉搜索樹：

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

AA樹

AVL樹

紅黑樹

替罪羊樹

八叉樹

2-3樹

Treap

我們將在以后的內容介紹他們，敬請期待吧。

PHP基礎數據結構專題系列目錄: 地址。主要使用PHP語法總結基礎的數據結構和算法。還有我們日常PHP開發中容易忽略的基礎知識和現代PHP開發中關于規范、部署、優化的一些實戰性建議，同時還有對Javascript語言特點的深入研究。