在上一章中我們正式開(kāi)啟了對(duì)數(shù)據(jù)結(jié)構(gòu)中樹(shù)的講解，介紹了樹(shù)的基礎(chǔ)。本章我們將學(xué)習(xí)二叉樹(shù)的概念，介紹滿二叉樹(shù)和完全二叉樹(shù)的定義，并對(duì)二叉樹(shù)的基本性質(zhì)進(jìn)行一個(gè)簡(jiǎn)單的介紹。本章附帶課后練習(xí)

?? 鏈接：C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)系列之樹(shù)的概念結(jié)構(gòu)和常見(jiàn)表示方法

0x00 概念

?? 定義：二叉樹(shù)既然叫二叉樹(shù)，顧名思義即度最大為2的樹(shù)稱為二叉樹(shù)。它的度可以為 1 也可以為 0，但是度最大為 2 。

?? 一顆二叉樹(shù)是節(jié)點(diǎn)的一個(gè)有限集合，該集合：

① 由一個(gè)根節(jié)點(diǎn)加上兩顆被稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成

② 或者為空

?? 觀察上圖我們可以得出如下結(jié)論：

① 二叉樹(shù)不存在度大于 2 的節(jié)點(diǎn)，換言之二叉樹(shù)最多也只能有兩個(gè)孩子。

② 二叉樹(shù)的子樹(shù)有左右之分，分別為左孩子和右孩子。次序不可顛倒，因此二叉樹(shù)是有序樹(shù)。

?? 注意：對(duì)于任意的二叉樹(shù)都是由以下幾種情況復(fù)合而成的：

0x01 滿二叉樹(shù)

?? 定義：一個(gè)二叉樹(shù)，如果每一層的節(jié)點(diǎn)數(shù)都達(dá)到了最大值（均為2），則這個(gè)二叉樹(shù)就可以被稱作為 "滿二叉樹(shù)" 。

?? 換言之，如果一個(gè)二叉樹(shù)的層數(shù)為 $h$ ，且節(jié)點(diǎn)總數(shù)是 $2^h - 1$ ，則他就是一個(gè)滿二叉樹(shù)。

?? 計(jì)算公式：

① 已知層數(shù)求總數(shù)： $N = 2^h-1$

② 已知總數(shù)求層數(shù)： $h = log_2(N+1)$

? 十億個(gè)節(jié)點(diǎn)，滿二叉樹(shù)是多少層？

?? $2^3^0$ ≈ 10億多

0x02 完全二叉樹(shù)

?? 定義：對(duì)于深度為 $K$ 的，有 $n$ 個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為 $K$ 的滿二叉樹(shù)中編號(hào)從 1 至 $n$ 的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱之為完全二叉樹(shù)。

?? 前 $h - 1$ 層是滿的，最后一層不滿，但是最后一層從左到右是連續(xù)的。

完全二叉樹(shù)是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹(shù)是由滿二叉樹(shù)而引出來(lái)的。所以，滿二叉樹(shù)是一種特殊的完全二叉樹(shù)（每一層節(jié)點(diǎn)均為2）。

?? 常識(shí)：

① 完全二叉樹(shù)中，度為 1 的最多只有 1 個(gè)。

② 高度為 $h$ 的完全二叉樹(shù)節(jié)點(diǎn)范圍是 $[ 2^{h-1} - 1 + 1, 2^{h} - 1 ]$

0x03 二叉樹(shù)的性質(zhì)

?? 四點(diǎn)規(guī)則：

① 若規(guī)定根節(jié)點(diǎn)的層數(shù)為 1 ，則一顆非空二叉樹(shù)的第 $i$ 層上最多有 $2^{(i-1)}$ 個(gè)節(jié)點(diǎn)。

② 若規(guī)定根節(jié)點(diǎn)的層數(shù)為 1 ，則深度為 $K$ 的二叉樹(shù)最大節(jié)點(diǎn)數(shù)是 $2^h-1$ .

③ 對(duì)任何一顆二叉樹(shù)，如果度為 0 其葉子結(jié)點(diǎn)個(gè)數(shù)為 $n_0$ ，度為 2 的分支節(jié)點(diǎn)個(gè)數(shù)為 $n_2$ ，則有 $n_0 = n_2 + 1$ 。換言之，度為 0 的永遠(yuǎn)比度為 2 的多一個(gè)葉子結(jié)點(diǎn)。

④ 若規(guī)定根節(jié)點(diǎn)的層數(shù)為 1 ，具有 $n$ 個(gè)節(jié)點(diǎn)的滿二叉樹(shù)的深度 $K = log_2 (n+1)$ （log是以2為底，n+1的對(duì)數(shù)）。

?? 對(duì)于有 $n$ 個(gè)節(jié)點(diǎn)的完全二叉樹(shù)，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點(diǎn)從 0 開(kāi)始編號(hào)，則對(duì)于序號(hào)為 $parent$ 的節(jié)點(diǎn)有：

（非完全二叉樹(shù)，也可以用數(shù)組存放，但會(huì)浪費(fèi)很多空間）

假設(shè) $parent$ 是父節(jié)點(diǎn)在數(shù)組中的下標(biāo)，此公式僅適用于完全二叉樹(shù)：

① 求左孩子： $leftChild = parent * 2 + 1$

② 求右孩子： $rightChild = parent*2+2$

③ 求父親（假設(shè)不關(guān)注是左孩子還是右孩子）： $parent = \frac{child-1}{2}$

④ 判斷是否有左孩子： $2*parent+1\geq n$

⑤ 判斷是否由右孩子： $2*parent+2 \geq n$

?? PS：二叉樹(shù)不一定要標(biāo)準(zhǔn)，比如這個(gè)其實(shí)也是二叉樹(shù)：

課后練習(xí)：

1. 某二叉樹(shù)共有 399 個(gè)結(jié)點(diǎn)，其中有 199 個(gè)度為 2 的結(jié)點(diǎn)，則該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)為（）

A. 不存在這樣的二叉樹(shù)

B. 200

C. 198

D. 199

2. 在具有 2n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，葉子結(jié)點(diǎn)個(gè)數(shù)為（）

A. n

B. n+1

C. n-1

D. n/2

3. 一棵完全二叉樹(shù)的節(jié)點(diǎn)數(shù)位為531個(gè)，那么這棵樹(shù)的高度為（）

A. 11

B. 10

C. 8

D. 12

5. 一個(gè)具有767個(gè)節(jié)點(diǎn)的完全二叉樹(shù)，其葉子節(jié)點(diǎn)個(gè)數(shù)為（）

A. 383

B. 384

C. 385

D. 386

參考資料：

Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .

百度百科[EB/OL]. []. https://baike.baidu.com/.

?? 筆者：王亦優(yōu)

?? 更新： 2021.11.24

? 勘誤：無(wú)

?? 聲明：由于作者水平有限，本文有錯(cuò)誤和不準(zhǔn)確之處在所難免，本人也很想知道這些錯(cuò)誤，懇望讀者批評(píng)指正！

本篇完。

到此這篇關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)系列篇二叉樹(shù)的概念及滿二叉樹(shù)與完全二叉樹(shù)的文章就介紹到這了,更多相關(guān)C語(yǔ)言二叉樹(shù)的概念內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: