Go 數據結構和算法篇：二叉樹的定義和存儲

一、樹的相關概念

樹這種數據結構模擬了自然界中樹的概念，自然界中的樹有根、葉子、枝幹，數據結構中的樹也是如此，只不過是倒過來的：

二叉樹圖示

其中的每個元素叫做節點。樹的頂點（沒有父元素的節點）叫根節點，如 E；每個分支的末端節點（沒有子元素的節點）叫葉子節點，如 G、H、I、J、K、L；用來連接相鄰節點之間的關係叫父子關係，比如 E 是 A、F 的父節點，A、F 是 E 的子節點；具有同一個父節點的多個子節點叫做兄弟節點，比如 A、F 是兄弟節點。

節點擁有的子節點數目叫做節點的度，顯然，葉子節點的度爲 0，樹的度是樹內各節點度的最大值。

除此之外，樹還有高度、深度和層的概念：

注：其實線性表也可以看作一種特殊的樹，只不過所有節點都在一個分支上，第一個元素是根節點，最後一個元素是子節點，沒有兄弟節點。層數就是線性表的長度。

多個互不相交的樹可以構成森林。

二、二叉樹的定義

二叉樹是我們平時遇到的最常見的樹結構，它是一種特殊的樹，顧名思義，就是每個節點最多有兩個「分叉」，即兩個子節點，分別是左子節點和右子節點，不過，二叉樹並不要求每個節點都有兩個子節點，有的節點只有左子節點，有的節點只有右子節點。比如下面這些都是二叉樹：

根據左右子節點的飽和度，我們又從二叉樹中提取出兩種特殊的二叉樹 —— 滿二叉樹和完全二叉樹。滿二叉樹即所有分支節點都有左右子節點，並且所有葉子節點都在同一層上，如上面的圖 2 便是滿二叉樹。完全二叉樹要複雜一些，深度爲 k 有 n 個節點的二叉樹，當且僅當其中的每一節點，都可以和同樣深度 k 的滿二叉樹，序號爲 1 到 n 的節點一對一對應時，稱爲完全二叉樹，比如上面的圖 3 就是完全二叉樹。

三、二叉樹的特性

在討論二叉樹的創建和存儲之前，我們先來總結下二叉樹的一些特性，以便後續用到（這裏二叉樹數的深度定義採用的最大層次數，如果從 0 開始計算的話，可以自行推演一下）：

性質 1：

在第 i 層最多有 2i-1 個節點。

性質 2：

深度爲 k 的二叉樹最多有 2k-1 個節點。

性質 3：

對於任何一個二叉樹，葉子節點數爲 n0，度爲 2 的節點數爲 n2，則 n0 = n2+1。

性質 4：

性質 5：

樹這種結構不能簡單通過線性表的前後關係來存儲，在線性表中，一個節點只有至多一個前驅節點和至多一個後驅節點，樹則不然，一個節點可能有多個後驅節點，這個時候，我們需要通過更加複雜的結構才能存儲樹。

二叉樹是一種特殊的樹，比多叉樹要簡單，因爲特定節點至多隻有兩個節點，這就極大簡化了相應的數據結構，使得通過線性表就可以實現二叉樹的存儲。我們後面基本只討論二叉樹，下面我們通過數組和鏈表來演示如何存儲二叉樹。

四、通過數組存儲二叉樹

對於特定的二叉樹而言，比如滿二叉樹、完全二叉樹，它們的節點之間是有一定關聯關係的，以下面這棵完全二叉樹爲例：

完全二叉樹

我們按照從上到下，從左到右對所有節點編號，可以看到，下一層的左右子節點和對應父節點序號存在某種數學關係，如果父節點的序號是 i，其對應左子節點位於 2i 的位置上，對應右子節點位於 2i + 1 的位置上，我們可以參照這個規則將上述完全二叉樹存儲到數組中：

數組存儲二叉樹

注意我們的下標從 1 開始（根節點），索引爲 0 的下標捨棄，浪費這個空間，以方便計算。這樣，我們就可以從根節點開始，依次將所有節點元素存放到數組中，並且可以根據節點間的數學關係很方便地遍歷整棵樹。此外，由於完全二叉樹的特殊性，除了第一個元素之外，該數組不存在任何空間的浪費。由於滿二叉樹是完全二叉樹的子集，所以也可以通過這種方式來存儲。

那麼其它二叉樹呢？當然也可以按照這種思路來做，我們把不存在的節點補全，比如假設上述序號爲 4、6、8、9 的元素不存在：

二叉樹存儲

可以看到，我們將不存在的元素補上，只是對應位置值爲 null，缺失的節點越多，數組的「空洞」也就越多，如果是極端情況，比如二叉樹只包含 1、3、7 三個元素，那麼數組中將會存在大量的「空洞」，浪費大量的空間，而且也會影響性能。

綜上，數組適合滿二叉樹、完全二叉樹這些特殊二叉樹的存儲，一些比較稠密的二叉樹也可以用數組，如果二叉樹比較稀疏就不適合用數組了，我們可以通過鏈表來存儲它們。

五、通過鏈表存儲二叉樹

理論上來說，鏈表適用於所有的二叉樹存儲，只不過這裏我們需要對線性表中的鏈表進行擴展，因爲二叉樹特定節點最多有兩個子節點，所有我們在鏈表結點上設置兩個指針域，分別指向左右子節點，所以這種鏈表結構又被稱作二叉鏈表。我們可以通過一個結構體表示二叉鏈表的節點：

// 節點類
type Node struct {
    Value string
    Left *Node
    Right *Node
}
// 初始化根節點
func NewNode(data string) *Node {
    return &Node{data, nil, nil}
}

如果要用二叉鏈表表示上面的完全二叉樹，對應的圖示如下：

鏈表存儲二叉樹

不管是什麼樣結構的二叉樹，用鏈表來存儲都不會存在空間的浪費。關於二叉樹的創建、查找和刪除，需要等到介紹完二叉樹的遍歷才能開始，下一篇我們就來探討如何遍歷二叉樹。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/cWBrgJnJcidlbE5bs0QlhQ