【二叉樹的定義】

二叉樹（ binary tree）是 n 個(gè)結(jié)點(diǎn)的有限集合，該集合或?yàn)榭占?#xff08;空二叉樹），或由一個(gè)根結(jié)點(diǎn)與兩棵互不相交的，稱為根結(jié)點(diǎn)的左子樹、右子樹的二叉樹構(gòu)成。

二叉樹的特點(diǎn)是：

• 每個(gè)結(jié)點(diǎn)最多有兩棵子樹，故二叉樹中不存在度大于 2 的結(jié)點(diǎn)
• 二叉樹是有序的，其次序不能任意顛倒，即使樹中的某個(gè)結(jié)點(diǎn)只有一棵子樹，也要區(qū)分它是左子樹還是右子樹

二叉樹具有以下 5 種基本形態(tài)：

【特殊的二叉樹】

在實(shí)際應(yīng)用中，常會(huì)用到以下幾種特殊的二叉樹。

1.斜樹

所有的結(jié)點(diǎn)都只有左子樹的二叉樹稱為左斜樹，所有的結(jié)點(diǎn)都只有右子樹的二叉樹稱為右斜樹

在斜樹中，每層只有一個(gè)結(jié)點(diǎn)，因此斜樹的結(jié)點(diǎn)個(gè)數(shù)與其深度相同

2.滿二叉樹

在一棵二叉樹中，若所有的分支結(jié)點(diǎn)都存在左子樹和右子樹，且所有的葉子都在同一層上，則稱為滿二叉樹。

其特點(diǎn)是：

• 葉子只能出現(xiàn)在最下一層
• 只有度為 0、度為 2 的結(jié)點(diǎn)

由于滿二叉樹的特性可知：滿二叉樹在同樣深度的二叉樹中結(jié)點(diǎn)個(gè)數(shù)、葉結(jié)點(diǎn)個(gè)數(shù)最多。

3.完全二叉樹

對(duì)一棵具 n 個(gè)結(jié)點(diǎn)的二叉樹按層序編號(hào)，若編號(hào)為 i 的結(jié)點(diǎn)與同樣深度的滿二叉樹中編號(hào) i 的結(jié)點(diǎn)在二叉樹中的位置完全相同，則稱為完全二叉樹，那么顯然有：滿二叉樹是完全二叉樹

其特點(diǎn)是：

• 葉結(jié)點(diǎn)只能出現(xiàn)在最下兩層，且最下層的葉結(jié)點(diǎn)都集中在二叉樹左側(cè)連續(xù)的位置
• 若有度為 1 的結(jié)點(diǎn)，只可能有一個(gè)，且其只有左孩子
• 深度為 k 的完全二叉樹在 k -1 層上行一定是滿二叉樹

簡(jiǎn)單來(lái)說(shuō)，在滿二叉樹中，從最后一個(gè)結(jié)點(diǎn)開始，連續(xù)去掉任意個(gè)的結(jié)點(diǎn)，即是一棵完全二叉樹

【二叉樹的性質(zhì)】

1.二叉樹的第 i 層上行最多有??個(gè)結(jié)點(diǎn)

2.在一棵深度為 k 的二叉樹中，最多有? 個(gè)結(jié)點(diǎn)，最少有 k 個(gè)結(jié)點(diǎn)

推論：深度為 k 且具? 個(gè)結(jié)點(diǎn)的二叉樹一定是滿二叉樹，但深度為 k 具有 k 個(gè)結(jié)點(diǎn)的二叉樹不一定是斜樹

3.具有 n 個(gè)結(jié)點(diǎn)的二叉樹，其分支數(shù)：B=n-1，對(duì)于任意一個(gè)結(jié)點(diǎn)，每度貢獻(xiàn)一個(gè)分支，即：度為 0 的結(jié)點(diǎn)貢獻(xiàn) 0?個(gè)分支，度為 1 的結(jié)點(diǎn)貢獻(xiàn) 1 個(gè)分支，度為 2 的結(jié)點(diǎn)貢獻(xiàn) 2 個(gè)分支。

4.在一棵二叉樹中，若葉結(jié)點(diǎn)個(gè)數(shù)為 ，度為 2 結(jié)點(diǎn)個(gè)數(shù)為 ，那么有：

5.具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為?

6.對(duì)一棵具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹，從 1 開始按層序編號(hào)，則對(duì)于任意編號(hào) i 的結(jié)點(diǎn)，有：

• 若 i=1，則：結(jié)點(diǎn) i 為根節(jié)點(diǎn)；若 i>1，則：結(jié)點(diǎn) i 的父結(jié)點(diǎn)編號(hào)為?
• 若 2i<=n，則：結(jié)點(diǎn) i 的左孩子編號(hào)為 2i；若 2i>n，則結(jié)點(diǎn) i 無(wú)左孩子
• 若 2i+1<=n，則：結(jié)點(diǎn) i 的右孩子編號(hào)為 2i+1；若 2i+1>n，則結(jié)點(diǎn) i 無(wú)右孩子

【二叉樹的遍歷】

二叉樹中最基本的操作是遍歷。

二叉樹的遍歷是從根節(jié)點(diǎn)出發(fā)，按照某種次序訪問(wèn)二叉樹中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次。

根據(jù)二叉樹的定義可知：一棵二叉樹由根節(jié)點(diǎn)、根節(jié)點(diǎn)的左子樹、根節(jié)點(diǎn)的右子樹三部分構(gòu)成，因此只要遞歸的遍歷這三部分即可遍歷整棵樹。

二叉樹的遍歷通常分為四種方式：

• 前序遍歷：先訪問(wèn)根結(jié)點(diǎn)，再前序遍歷根節(jié)點(diǎn)的左子樹，然后再前序遍歷根節(jié)點(diǎn)的右子樹（根左右）
• 中序遍歷：先中序遍歷根結(jié)點(diǎn)的左子樹，再訪問(wèn)根節(jié)點(diǎn)，然后再中序遍歷根結(jié)點(diǎn)的右子樹（左根右）
• 后序遍歷：先后序遍歷根結(jié)點(diǎn)的左子樹，再后序遍歷根結(jié)點(diǎn)的右子樹，然后再訪問(wèn)根結(jié)點(diǎn)（左右根）
• 層次遍歷：從根節(jié)點(diǎn)開始，按層次從小到大逐個(gè)訪問(wèn)，同一層次按照從左到右的次序

二叉樹遍歷的性質(zhì)：

• 已知前序遍歷序列和中序遍歷序列，可以確定唯一的一棵二叉樹
• 已知后序遍歷序列和中序遍歷序列，可以確定唯一的一棵二叉樹

【二叉樹的存儲(chǔ)結(jié)構(gòu)】

二叉樹的存儲(chǔ)結(jié)構(gòu)分為：順序存儲(chǔ)結(jié)構(gòu)、二叉鏈表、三叉鏈表、線索鏈表等，其各有優(yōu)劣，在應(yīng)用時(shí)應(yīng)根據(jù)實(shí)際情況靈活使用。

• 順序存儲(chǔ)結(jié)構(gòu)：點(diǎn)擊這里
• 二叉鏈表：點(diǎn)擊這里
• 三叉鏈表：點(diǎn)擊這里
• 線索鏈表：點(diǎn)擊這里

【樹、森林、二叉樹的轉(zhuǎn)換】

從樹的孩子兄弟表示法和二叉樹的二叉鏈表表示法可以看出，樹的孩子兄弟表示法實(shí)質(zhì)上是二叉樹的二叉鏈表存儲(chǔ)形式，因此，從物理結(jié)構(gòu)上來(lái)看，兩者是相同的，只是解釋不同。

因此，以二叉鏈表為媒介，可導(dǎo)出樹與二叉樹間的對(duì)應(yīng)關(guān)系，也就是說(shuō)，給出一棵樹，可以找到一棵唯一的二叉樹與之對(duì)應(yīng)，這樣一來(lái)，對(duì)樹的操作即可借助二叉樹的存儲(chǔ)，利用二叉樹上的操作實(shí)現(xiàn)。

具體內(nèi)容：點(diǎn)擊這里

【哈夫曼樹及哈夫曼編碼】

哈夫曼樹（Huffman Tree）又稱最優(yōu)二叉樹，而哈夫曼編碼（Huffman Coding）又稱最優(yōu)編碼，是一種編碼方式，屬于可變字長(zhǎng)編碼（VLC）一種，其根據(jù)字符出現(xiàn)的概率來(lái)構(gòu)造異字頭的平均長(zhǎng)度最短的碼字。

哈夫曼樹與哈夫曼編碼是二叉樹的經(jīng)典應(yīng)用，在實(shí)際中有著廣泛的應(yīng)用。

具體內(nèi)容：點(diǎn)擊這里

總結(jié)

以上是生活随笔為你收集整理的理论基础 —— 二叉树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。