前言

樹和二叉樹是計(jì)算機(jī)科學(xué)中常用的數(shù)據(jù)結(jié)構(gòu)，它們?cè)跀?shù)據(jù)存儲(chǔ)、搜索、排序等多個(gè)領(lǐng)域都有著廣泛的應(yīng)用。從簡(jiǎn)單的二叉樹出發(fā)，我們可以逐步理解更復(fù)雜的樹結(jié)構(gòu)，如紅黑樹、AVL樹等。

二叉樹是一種每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)的樹結(jié)構(gòu)，通常子節(jié)點(diǎn)被稱為“左子節(jié)點(diǎn)”和“右子節(jié)點(diǎn)”。這種結(jié)構(gòu)使得二叉樹在編程中非常易于實(shí)現(xiàn)和操作。例如，我們可以使用數(shù)組或鏈表來存儲(chǔ)二叉樹，并通過遞歸算法來實(shí)現(xiàn)遍歷、查找和插入等操作。

然而，二叉樹并不是唯一的樹結(jié)構(gòu)。在實(shí)際應(yīng)用中，我們可能需要處理更復(fù)雜的樹形結(jié)構(gòu)，如多叉樹和森林等。多叉樹是指每個(gè)節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)的樹結(jié)構(gòu)，而森林則是由多個(gè)不相交的樹組成的集合。這些樹形結(jié)構(gòu)在處理實(shí)際問題時(shí)，往往能夠提供更好的解決方案。

除了上述的樹形結(jié)構(gòu)外，還有一些特殊的樹形結(jié)構(gòu)，如堆、并查集、字典樹等。堆是一種特殊的完全二叉樹，它可以用于實(shí)現(xiàn)優(yōu)先隊(duì)列等數(shù)據(jù)結(jié)構(gòu)；并查集則是一種用于處理不相交集合合并及查詢問題的數(shù)據(jù)結(jié)構(gòu)；字典樹則是一種用于快速查找字符串的數(shù)據(jù)結(jié)構(gòu)。

總的來說，樹形結(jié)構(gòu)是一種非常有用的數(shù)據(jù)結(jié)構(gòu)，它們?cè)谟?jì)算機(jī)科學(xué)中扮演著重要的角色。通過深入理解樹和二叉樹的基本原理和應(yīng)用場(chǎng)景，我們可以更好地應(yīng)用它們來解決實(shí)際問題，提高程序的效率和可靠性。因此，對(duì)于學(xué)習(xí)計(jì)算機(jī)科學(xué)的人來說，掌握樹形結(jié)構(gòu)是非常重要的。

一、樹概念及結(jié)構(gòu)

1.1樹的概念

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做樹是因?yàn)樗雌饋硐褚豢玫箳斓臉?，也就是說它是根朝上，而葉朝下的。

有一個(gè)特殊的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，根節(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，除根節(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成M(M>0)個(gè)互不相交的集合T1、T2、……、Tm，其中每一個(gè)集合Ti(1<= i <= m)又是一棵結(jié)構(gòu)與樹類似的子樹。每棵子樹的根結(jié)點(diǎn)有且只有一個(gè)前驅(qū)，可以有0個(gè)或多個(gè)后繼因此，樹是遞歸定義的。

注意：樹形結(jié)構(gòu)中，子樹之間不能有交集，否則就不是樹形結(jié)構(gòu)

1.2 樹的相關(guān)概念（重要）

• 節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度； 如上圖：A的為6

• 葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)； 如上圖：B、C、H、I…等節(jié)點(diǎn)為葉節(jié)點(diǎn)

• 非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)； 如上圖：D、E、F、G…等節(jié)點(diǎn)為分支節(jié)點(diǎn)

• 雙親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)； 如上圖：A是B的父節(jié)點(diǎn)

• 孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)； 如上圖：B是A的孩子節(jié)點(diǎn)

• 兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)； 如上圖：B、C是兄弟節(jié)點(diǎn)

• 樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度； 如上圖：樹的度為6

• 節(jié)點(diǎn)的層次：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推；這只是一般的認(rèn)知，有些書上也會(huì)將第一層看作0，具體按題目來分析。一般題目不說都是按1來看

• 樹的高度或深度：樹中節(jié)點(diǎn)的最大層次； 如上圖：樹的高度為4

• 堂兄弟節(jié)點(diǎn)：雙親在同一層的節(jié)點(diǎn)互為堂兄弟；如上圖：H、I互為兄弟節(jié)點(diǎn)

• 節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；如上圖：A是所有節(jié)點(diǎn)的祖先

• 子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。如上圖：所有節(jié)點(diǎn)都是A的子孫

• 森林：由m（m>0）棵互不相交的樹的集合稱為森林；

1.3 樹的表示

樹結(jié)構(gòu)相對(duì)線性表就比較復(fù)雜了，要存儲(chǔ)表示起來就比較麻煩了，既然保存值域，也要保存結(jié)點(diǎn)和結(jié)點(diǎn)之間的關(guān)系，實(shí)際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等。我們這里就簡(jiǎn)單的了解其中最常用的孩子兄弟表示法。

typedef int DataType;
struct Node
{
	 struct Node* _firstChild1; // 第一個(gè)孩子結(jié)點(diǎn)
	 struct Node* _pNextBrother; // 指向其下一個(gè)兄弟結(jié)點(diǎn)
	 DataType _data; // 結(jié)點(diǎn)中的數(shù)據(jù)域
};

1.4 樹在實(shí)際中的運(yùn)用（表示文件系統(tǒng)的目錄樹結(jié)構(gòu)）

二、二叉樹概念及結(jié)構(gòu)

2.1二叉樹概念

一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合:

1. 或者為空
2. 由一個(gè)根節(jié)點(diǎn)加上兩棵別稱為左子樹和右子樹的二叉樹組成

從上圖可以看出：

1. 二叉樹不存在度大于2的結(jié)點(diǎn)
2. 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹

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

2.2現(xiàn)實(shí)中的二叉樹

2.3 特殊的二叉樹

1. 滿二叉樹：一個(gè)二叉樹，如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹就是滿二叉樹。也就是說，如果一個(gè)二叉樹的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是2^k - 1 ，則它就是滿二叉樹。
2. 完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對(duì)于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。

2.4 二叉樹的性質(zhì)

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

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

• 對(duì)任何一棵二叉樹, 如果度為0其葉結(jié)點(diǎn)個(gè)數(shù)為n₀ , 度為2的分支結(jié)點(diǎn)個(gè)數(shù)為n₂ ,則有n₀ ＝ n₂＋1

• 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個(gè)結(jié)點(diǎn)的滿二叉樹的深度，h=log₂ (n + 1 ) (ps：log₂ (n + 1 ) 是log以2為底，n+1為對(duì)數(shù))

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

  • 若i>0，i位置節(jié)點(diǎn)的雙親序號(hào)：(i-1)/2；i=0，i為根節(jié)點(diǎn)編號(hào)，無雙親節(jié)點(diǎn)
  • 若2i+1<n，左孩子序號(hào)：2i+1，2i+1>=n否則無左孩子
  • 若2i+2<n，右孩子序號(hào)：2i+2，2i+2>=n否則無右孩子

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

二叉樹一般可以使用兩種結(jié)構(gòu)存儲(chǔ)，一種順序結(jié)構(gòu)，一種鏈?zhǔn)浇Y(jié)構(gòu)。

1. 順序存儲(chǔ)
   順序結(jié)構(gòu)存儲(chǔ)就是使用數(shù)組來存儲(chǔ)，一般使用數(shù)組只適合表示完全二叉樹，因?yàn)椴皇峭耆鏄鋾?huì)有空間的浪費(fèi)。而現(xiàn)實(shí)中使用中只有堆才會(huì)使用數(shù)組來存儲(chǔ)，關(guān)于堆我會(huì)在后面的文章進(jìn)行講解。二叉樹順序存儲(chǔ)在物理上是一個(gè)數(shù)組，在邏輯上是一顆二叉樹。
   

2. 鏈?zhǔn)酱鎯?chǔ)
   二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。 通常的方法是鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址 。鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈，當(dāng)前我們學(xué)習(xí)中一般都是二叉鏈，等學(xué)到高階數(shù)據(jù)結(jié)構(gòu)如紅黑樹等會(huì)用到三叉鏈。

typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{
	struct BinTreeNode* _pLeft; // 指向當(dāng)前節(jié)點(diǎn)左孩子
	struct BinTreeNode* _pRight; // 指向當(dāng)前節(jié)點(diǎn)右孩子
	BTDataType _data; // 當(dāng)前節(jié)點(diǎn)值域
}
 
// 三叉鏈
struct BinaryTreeNode
{
 	struct BinTreeNode* _pParent; // 指向當(dāng)前節(jié)點(diǎn)的雙親
 	struct BinTreeNode* _pLeft; // 指向當(dāng)前節(jié)點(diǎn)左孩子
 	struct BinTreeNode* _pRight; // 指向當(dāng)前節(jié)點(diǎn)右孩子
 	BTDataType _data; // 當(dāng)前節(jié)點(diǎn)值域
}；

三、樹和二叉樹的練習(xí)題

1. 某二叉樹共有 399 個(gè)結(jié)點(diǎn)，其中有 199 個(gè)度為 2 的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)為（ ）
   A、 不存在這樣的二叉樹
   B、 200
   C 、198
   D、 199

2. 下列數(shù)據(jù)結(jié)構(gòu)中，不適合采用順序存儲(chǔ)結(jié)構(gòu)的是（ ）
   A 、非完全二叉樹
   B 、堆
   C 、隊(duì)列
   D 、棧

3. 在具有 2n 個(gè)結(jié)點(diǎn)的完全二叉樹中，葉子結(jié)點(diǎn)個(gè)數(shù)為（ ）
   A、 n
   B、 n+1
   C 、n-1
   D 、n/2

4. 一棵完全二叉樹的節(jié)點(diǎn)數(shù)位為531個(gè)，那么這棵樹的高度為（ ）
   A 、11
   B 、10
   C、 8
   D、12

5. 一個(gè)具有767個(gè)節(jié)點(diǎn)的完全二叉樹，其葉子節(jié)點(diǎn)個(gè)數(shù)為（）
   A 、383
   B、 384
   C、 385
   D、 386

答案

1.B
2.A
3.A 按1來排序，左子樹的值是其根的2倍，右子樹是2倍加1，故沒有右子樹 根據(jù) n₀ = n₂ + 1 且少一顆右子樹 即n₁ = 1 2n₂ + 2 = 2n n₂ = n - 1 n₀ = n

4.B
5.B (767 - 1)/ 2 + 1文章來源地址http://www.zghlxwxcb.cn/news/detail-840299.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)從入門到精通——樹和二叉樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！