目錄

二叉樹基礎(chǔ)知識(shí)

概念 :?

根節(jié)點(diǎn)的五個(gè)形態(tài) :?

特殊的二叉樹

滿二叉樹 :?

?完全二叉樹 :?

二叉搜索樹? :

平衡二叉搜索樹 :?

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

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

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

二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

?二叉樹的遍歷方式 :?

基礎(chǔ)概念

前中后遍歷

?層序遍歷 :?

---

二叉樹基礎(chǔ)知識(shí)

概念 :?

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

根節(jié)點(diǎn)的五個(gè)形態(tài) :?

1. 空二叉樹

2. 只有一個(gè)根結(jié)點(diǎn)

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

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

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

特殊的二叉樹

滿二叉樹 :?

概念 :?

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

圖例 :?

?完全二叉樹 :?

概念 :?

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

圖例 :?

?而

?這個(gè)就不是一顆完全二叉樹!

二叉搜索樹? :

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

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

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

?二叉搜索樹最大的特點(diǎn)就是左<父<右 ;

平衡二叉搜索樹 :?

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

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

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

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

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

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

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

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

   ⑴i =1 時(shí)，該節(jié)點(diǎn)為根，它無(wú)雙親節(jié)點(diǎn) 。

   ⑵ i > 1 時(shí)，該節(jié)點(diǎn)的雙親節(jié)點(diǎn)的編號(hào)為i/2 。

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

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

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

二叉樹可以順序存儲(chǔ)，也可以鏈?zhǔn)酱鎯?chǔ) ;

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

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

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

?可以采用以下線性表來存儲(chǔ):

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

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

二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

在鏈?zhǔn)浇Y(jié)構(gòu)中，一個(gè)二叉樹的結(jié)點(diǎn)包含左孩子指針，數(shù)據(jù)，右孩子指針 ;

鏈?zhǔn)酱鎯?chǔ)效果如圖 :?

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

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

?二叉樹的遍歷方式 :?

基礎(chǔ)概念

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

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

這兩種遍歷方法又可以細(xì)分 :?

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

前中后遍歷

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

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

圖例 :?

?層序遍歷 :?

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

如下圖 :?

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

ABCDEFGHI?

參考 :?

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

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

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

4. 代碼隨想錄