Go 數(shù)據(jù)結(jié)構(gòu)和算法篇（十五）：二叉樹的定義和存儲

一、樹的相關(guān)概念

樹這種數(shù)據(jù)結(jié)構(gòu)模擬了自然界中樹的概念，自然界中的樹有根、葉子、枝干，數(shù)據(jù)結(jié)構(gòu)中的樹也是如此，只不過是倒過來的：

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

節(jié)點擁有的子節(jié)點數(shù)目叫做節(jié)點的度，顯然，葉子節(jié)點的度為 0，樹的度是樹內(nèi)各節(jié)點度的最大值。

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

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

多個互不相交的樹可以構(gòu)成森林。

二、二叉樹的定義

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

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

三、二叉樹的特性

在討論二叉樹的創(chuàng)建和存儲之前，我們先來總結(jié)下二叉樹的一些特性，以便后續(xù)用到（這里二叉樹數(shù)的深度定義采用的最大層次數(shù)，如果從 0 開始計算的話，可以自行推演一下）：

性質(zhì)1：

在第 i 層最多有 2^i-1 個節(jié)點。

性質(zhì)2：

深度為 k 的二叉樹最多有 2^k-1 個節(jié)點。

性質(zhì)3：

對于任何一個二叉樹，葉子節(jié)點數(shù)為 n₀，度為 2 的節(jié)點數(shù)為 n₂，則 n₀ = n₂+1。

性質(zhì)4：

性質(zhì)5：

樹這種結(jié)構(gòu)不能簡單通過線性表的前后關(guān)系來存儲，在線性表中，一個節(jié)點只有至多一個前驅(qū)節(jié)點和至多一個后驅(qū)節(jié)點，樹則不然，一個節(jié)點可能有多個后驅(qū)節(jié)點，這個時候，我們需要通過更加復(fù)雜的結(jié)構(gòu)才能存儲樹。

二叉樹是一種特殊的樹，比多叉樹要簡單，因為特定節(jié)點至多只有兩個節(jié)點，這就極大簡化了相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，使得通過線性表就可以實現(xiàn)二叉樹的存儲。我們后面基本只討論二叉樹，下面我們通過數(shù)組和鏈表來演示如何存儲二叉樹。

四、通過數(shù)組存儲二叉樹

對于特定的二叉樹而言，比如滿二叉樹、完全二叉樹，它們的節(jié)點之間是有一定關(guān)聯(lián)關(guān)系的，以下面這棵完全二叉樹為例：

我們按照從上到下，從左到右對所有節(jié)點編號，可以看到，下一層的左右子節(jié)點和對應(yīng)父節(jié)點序號存在某種數(shù)學(xué)關(guān)系，如果父節(jié)點的序號是 i，其對應(yīng)左子節(jié)點位于 2i 的位置上，對應(yīng)右子節(jié)點位于 2i + 1 的位置上，我們可以參照這個規(guī)則將上述完全二叉樹存儲到數(shù)組中：

注意我們的下標(biāo)從 1 開始（根節(jié)點），索引為 0 的下標(biāo)舍棄，浪費這個空間，以方便計算。這樣，我們就可以從根節(jié)點開始，依次將所有節(jié)點元素存放到數(shù)組中，并且可以根據(jù)節(jié)點間的數(shù)學(xué)關(guān)系很方便地遍歷整棵樹。此外，由于完全二叉樹的特殊性，除了第一個元素之外，該數(shù)組不存在任何空間的浪費。由于滿二叉樹是完全二叉樹的子集，所以也可以通過這種方式來存儲。

那么其它二叉樹呢？當(dāng)然也可以按照這種思路來做，我們把不存在的節(jié)點補全，比如假設(shè)上述序號為 4、6、8、9 的元素不存在：

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

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

五、通過鏈表存儲二叉樹

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

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

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

不管是什么樣結(jié)構(gòu)的二叉樹，用鏈表來存儲都不會存在空間的浪費。關(guān)于二叉樹的創(chuàng)建、查找和刪除，需要等到介紹完二叉樹的遍歷才能開始，下一篇我們就來探討如何遍歷二叉樹。

（本文完）

學(xué)習(xí)過程中有任何問題，可以通過下面的評論功能或加入「Go 語言研習(xí)社」與學(xué)院君討論：

本系列教程首發(fā)在 geekr.dev，你可以點擊頁面左下角閱讀原文鏈接查看最新更新的教程。