目錄

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

1.1樹的概念

1.2樹的表示

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

2.1概念

2.2二叉樹的特點(diǎn)

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

2.4數(shù)據(jù)結(jié)構(gòu)中的二叉樹

2.5 特殊的二叉樹

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

2.6.1二叉樹的性質(zhì)

2.6.2 順序結(jié)構(gòu)

2.6.3鏈?zhǔn)酱鎯?chǔ)

三. 二叉樹的鏈?zhǔn)浇Y(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)樗雌饋硐褚豢玫箳斓臉?#xff0c;也就是說它是根朝上，而葉朝下的。

有一個(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é)點(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層，以此類推；

樹的高度或深度：樹中節(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.2樹的表示

樹結(jié)構(gòu)相對線性表就比較復(fù)雜了，要存儲(chǔ)表示起來就比較麻煩了，實(shí)際中樹有很多種表示方式，如：雙親表示法，孩子表示法、孩子兄弟表示法等等。我們這里就簡單的了解其中最常用的孩子兄弟表示法

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ù)域
};

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

2.1概念

一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根節(jié)點(diǎn)加上兩棵別稱為左子樹和右子樹的二叉樹組成。

2.2二叉樹的特點(diǎn)

1. 每個(gè)結(jié)點(diǎn)最多有兩棵子樹，即二叉樹不存在度大于2的結(jié)點(diǎn)。
2. 二叉樹的子樹有左右之分，其子樹的次序不能顛倒。

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

2.4數(shù)據(jù)結(jié)構(gòu)中的二叉樹

2.5 特殊的二叉樹

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)，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對應(yīng)時(shí)稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹

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

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

2.6.1二叉樹的性質(zhì)

1. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第i層上最多有2^(i-1) 個(gè)結(jié)點(diǎn).
2. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點(diǎn)數(shù)是2^h- 1.
3. 對任何一棵二叉樹, 如果度為0其葉結(jié)點(diǎn)個(gè)數(shù)為 n0, 度為2的分支結(jié)點(diǎn)個(gè)數(shù)為 n2,則有n0＝n2＋1
4. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個(gè)結(jié)點(diǎn)的滿二叉樹的深度，h=Log2(n+1). (ps：Log2(n+1)是log以2為底，n+1為對數(shù))
5. 對于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點(diǎn)從0開始編號(hào)，則對于序號(hào)為i的結(jié)點(diǎn)有：
1. 若i>0，i位置節(jié)點(diǎn)的雙親序號(hào)：(i-1)/2；i=0，i為根節(jié)點(diǎn)編號(hào)，無雙親節(jié)點(diǎn)
2. 若2i+1<n，左孩子序號(hào)：2i+1，2i+1>=n否則無左孩子
3. 若2i+2<n，右孩子序號(hào)：2i+2，2i+2>=n否則無右孩子

2.6.2 順序結(jié)構(gòu)

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

2.6.3鏈?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ì)用到三叉鏈

三. 二叉樹的鏈?zhǔn)浇Y(jié)構(gòu)的遍歷

所謂遍歷(Traversal)是指沿著某條搜索路線，依次對樹中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問。訪問結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問 題。 遍歷是二叉樹上最重要的運(yùn)算之一，是二叉樹上進(jìn)行其它運(yùn)算之基礎(chǔ)

前序/中序/后序的遞歸結(jié)構(gòu)遍歷：是根據(jù)訪問結(jié)點(diǎn)操作發(fā)生位置命名
?

1. NLR：前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前。
2. LNR：中序遍歷(Inorder Traversal)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之中（間）。

3. LRN：后序遍歷(Postorder Traversal)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后。

由于被訪問的結(jié)點(diǎn)必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。

層序遍歷：除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進(jìn)行層序遍歷。設(shè)二叉樹的根節(jié)點(diǎn)所在層數(shù)為1，層序遍歷就是從所在二叉樹的根節(jié)點(diǎn)出發(fā)，首先訪問第一層的樹根節(jié)點(diǎn)，然后從左到右訪問第2層上的節(jié)點(diǎn)，接著是第三層的節(jié)點(diǎn)，以此類推，自上而下，自左至右逐層訪問樹的結(jié)點(diǎn)的過程就是層序遍歷。