目錄

二叉樹基礎知識

概念 :?

根節(jié)點的五個形態(tài) :?

特殊的二叉樹

滿二叉樹 :?

?完全二叉樹 :?

二叉搜索樹? :

平衡二叉搜索樹 :?

二叉樹的性質(zhì) :?

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

二叉樹的順序存儲結(jié)構(gòu)

二叉樹的鏈式存儲結(jié)構(gòu)

?二叉樹的遍歷方式 :?

基礎概念

前中后遍歷

?層序遍歷 :?

---

二叉樹基礎知識

概念 :?

二叉樹（binary tree）是指樹中節(jié)點的度不大于2的有序樹，它是一種最簡單且最重要的樹。二叉樹的遞歸定義為：二叉樹是一棵空樹，或者是一棵由一個根節(jié)點和兩棵互不相交的，分別稱作根的左子樹和右子樹組成的非空樹；左子樹和右子樹又同樣都是二叉樹。

根節(jié)點的五個形態(tài) :?

1. 空二叉樹

2. 只有一個根結(jié)點

3. 根結(jié)點只有左子樹

4. 根結(jié)點只有右子樹

5. 根結(jié)點既有左子樹又有右子樹

特殊的二叉樹

滿二叉樹 :?

概念 :?

如果一棵二叉樹只有度為0的結(jié)點和度為2的結(jié)點，并且度為0的結(jié)點在同一層上，則這棵二叉樹為滿二叉樹。

圖例 :?

?完全二叉樹 :?

概念 :?

????????在完全二叉樹中，除了最底層節(jié)點可能沒填滿外，其余每層節(jié)點數(shù)都達到最大值，并且最下面一層的節(jié)點都集中在該層最左邊的若干位置。若最底層為第 h 層（h從1開始），則該層包含 1~ 2^(h-1) 個節(jié)點。

圖例 :?

?而

?這個就不是一顆完全二叉樹!

二叉搜索樹? :

前面介紹的樹，都沒有數(shù)值的，而二叉搜索樹是有數(shù)值的了，二叉搜索樹是一個有序樹。

• 若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；
• 若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；
• 它的左、右子樹也分別為二叉排序樹

下面的就是一顆二叉搜索樹;

?二叉搜索樹最大的特點就是左<父<右 ;

平衡二叉搜索樹 :?

又被稱為AVL（Adelson-Velsky and Landis）樹，且具有以下性質(zhì)：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。

其中c++中的map、set、multimap，multiset的底層實現(xiàn)都是平衡二叉搜索樹，所以map、set的增刪操作時間時間復雜度是logn , 而unordered_map、unordered_set，unordered_map、unordered_set底層實現(xiàn)是哈希表。

二叉樹的性質(zhì) :?

1. 二叉樹的第i層上至多有2 ^ (i-1)（i≥1）個節(jié)點。

2. 深度為h的二叉樹中至多含有2^h-1個節(jié)點

3. 若在任意一棵二叉樹中，有 n0 個葉子節(jié)點，有 n2 個度為2的節(jié)點，則必有n0 = n2 + 1

4. 具有n個節(jié)點的完全二叉樹深為log2(x) + 1（其中x表示不大于n的最大整數(shù)）

5. 若對一棵有n個節(jié)點的完全二叉樹進行順序編號（1<=i<=n），那么，對于編號為i（i>=1）的節(jié)點:

   ⑴i =1 時，該節(jié)點為根，它無雙親節(jié)點 。

   ⑵ i > 1 時，該節(jié)點的雙親節(jié)點的編號為i/2 。

   ⑶2i<= n，則有編號為2i的左節(jié)點，否則沒有左節(jié)點 。

   ⑷2i+1<=n ，則有編號為2i+1的右節(jié)點，否則沒有右節(jié)點 。

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

二叉樹可以順序存儲，也可以鏈式存儲 ;

二叉樹的順序存儲結(jié)構(gòu)

二叉樹的順序存儲結(jié)構(gòu)就是用一維數(shù)組存儲二叉樹中的結(jié)點，并且結(jié)點的存儲位置，也就是數(shù)組的下標要能體現(xiàn)結(jié)點之間的邏輯關系，比如雙親與孩子的關系，左右兄弟的關系等。

如以下這顆完全二叉樹 :?

?可以采用以下線性表來存儲:

下標	1	2	3	4	5	6	7	8	9	10
數(shù)據(jù)	A	B	C	D	E	F	G	H	I	J

?如果父節(jié)點的數(shù)組下標是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

二叉樹的鏈式存儲結(jié)構(gòu)

在鏈式結(jié)構(gòu)中，一個二叉樹的結(jié)點包含左孩子指針，數(shù)據(jù)，右孩子指針 ;

鏈式存儲效果如圖 :?

二叉鏈表的結(jié)構(gòu)體定義 :?

typedef struct BiTNode
{TElemType data;  //數(shù)據(jù)域struct BiTNode *lchild,*rchild; //指針域
}BiTNode，*BiTree;

?二叉樹的遍歷方式 :?

基礎概念

首先，主要的兩種遍歷方式為 :?

1. 深度優(yōu)先遍歷：先往深走，遇到葉子節(jié)點再往回走。
2. 廣度優(yōu)先遍歷：一層一層的去遍歷。

這兩種遍歷方法又可以細分 :?

• 深度優(yōu)先遍歷
  • 前序遍歷（遞歸法，迭代法）
  • 中序遍歷（遞歸法，迭代法）
  • 后序遍歷（遞歸法，迭代法）
• 廣度優(yōu)先遍歷
  • 層次遍歷（迭代法）

前中后遍歷

其中前中后三種結(jié)點的遍歷順序 如下 :

• 前序遍歷：中左右
• 中序遍歷：左中右
• 后序遍歷：左右中

圖例 :?

?層序遍歷 :?

從樹的第一層開始訪問，從上而下逐層遍歷，在同一層中，按從左到右的順序?qū)Y(jié)點逐個訪問 ;

如下圖 :?

?層序遍歷的結(jié)果為 :?

ABCDEFGHI?

參考 :?

1. 《大話數(shù)據(jù)結(jié)構(gòu)》

2. 《數(shù)據(jù)結(jié)構(gòu)》C語言版（清華嚴蔚敏考研版）

3. 【數(shù)據(jù)結(jié)構(gòu)與算法】二叉樹

4. 代碼隨想錄