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

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

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

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

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

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

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

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

二、二叉樹的定義

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

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

三、二叉樹的特性

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

性質(zhì)1：

在第 i 層最多有 2^i-1 個(gè)節(jié)點(diǎn)。

性質(zhì)2：

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

性質(zhì)3：

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

性質(zhì)4：

性質(zhì)5：

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

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

四、通過(guò)數(shù)組存儲(chǔ)二叉樹

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

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

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

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

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

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

五、通過(guò)鏈表存儲(chǔ)二叉樹

理論上來(lái)說(shuō)，鏈表適用于所有的二叉樹存儲(chǔ)，只不過(guò)這里我們需要對(duì)線性表中的鏈表進(jìn)行擴(kuò)展，因?yàn)槎鏄涮囟ü?jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，所有我們?cè)阪湵斫Y(jié)點(diǎn)上設(shè)置兩個(gè)指針域，分別指向左右子節(jié)點(diǎn)，所以這種鏈表結(jié)構(gòu)又被稱作二叉鏈表。我們可以通過(guò)一個(gè)結(jié)構(gòu)體表示二叉鏈表的節(jié)點(diǎn)：

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

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

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

（本文完）

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

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