---

二叉樹

---

一、樹的概念

1.樹形結(jié)構(gòu)

1.1. 樹的特點(diǎn)：

1.根節(jié)點(diǎn)沒有前驅(qū)節(jié)點(diǎn)
2.除根節(jié)點(diǎn)外，其余結(jié)點(diǎn)分成了M個(gè)互不相交的集合
3.子樹的根節(jié)點(diǎn)有且只有一個(gè)前驅(qū)
4.樹是遞歸定義的

• 樹形結(jié)構(gòu)中，子樹不能相交；
• 除了根節(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且只有一個(gè)父結(jié)點(diǎn)；
• 一顆N個(gè)結(jié)點(diǎn)的樹，有N-1條邊；

1.2 概念：

• 1.結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)含子樹的個(gè)數(shù) ，如上圖：A的度為3；
• 2.樹的度：樹中，結(jié)點(diǎn)的度最大值 ，數(shù)的度為3 ；
• 3.葉子結(jié)點(diǎn)/終端結(jié)點(diǎn)：度為0的結(jié)點(diǎn)（沒有子結(jié)點(diǎn)）如J、F、K、L、H、I；
• 4.父結(jié)點(diǎn)/雙親節(jié)點(diǎn)：含有子節(jié)點(diǎn)的結(jié)點(diǎn). 如A是C的父結(jié)點(diǎn)；
• 5.子結(jié)點(diǎn)/孩子結(jié)點(diǎn)：如B是A的子結(jié)點(diǎn)
• 6.根結(jié)點(diǎn)：一棵樹中，沒有父結(jié)點(diǎn)的結(jié)點(diǎn)： A
• 7.結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開始，根為第1層，根的子結(jié)點(diǎn)為第2層…
• 8.樹的高度/深度:樹中結(jié)點(diǎn)的最大層次。 上圖中樹的高度為4；
• 9.分支結(jié)點(diǎn)/非終端結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)：E,G…
• 10.兄弟結(jié)點(diǎn)：具有相同的父結(jié)點(diǎn)：E、F
• 11.堂兄弟結(jié)點(diǎn)：其父結(jié)點(diǎn)都在同一層；F、G
• 12.森林:多棵互不相交的的數(shù)的結(jié)合

1.3 樹的表示形式

孩子兄弟表示法：

class Node{int val;//存儲(chǔ)的數(shù)據(jù)Node firstChild;//第一個(gè)孩子引用Node nextBrother;//下一個(gè)兄弟引用
}

一個(gè)結(jié)點(diǎn)中，val存儲(chǔ)數(shù)據(jù)
firstChild存該結(jié)點(diǎn)的第一個(gè)子結(jié)點(diǎn)
nextBrother存該結(jié)點(diǎn)下一個(gè)兄弟結(jié)點(diǎn)
沒有孩子兄弟的時(shí)候?yàn)閚ull

孩子雙親表示法

2.樹的應(yīng)用

文件夾結(jié)構(gòu)

二、二叉樹

1.二叉數(shù)的概念

• 一個(gè)根節(jié)點(diǎn)加上它的左子樹和右子樹
• 二叉樹不存在度大于2的結(jié)點(diǎn)（一個(gè)結(jié)點(diǎn)只能有兩個(gè)子節(jié)點(diǎn)）
• 二叉樹是有序樹，子樹的左右不能顛倒

2.滿二叉樹

1.每一層的結(jié)點(diǎn)都是滿的，除了最后一層，每個(gè)結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)
2.每層的結(jié)點(diǎn)數(shù)都達(dá)到最大值
3.如果二叉樹的層數(shù)為K,結(jié)點(diǎn)總數(shù)為2^k-1,則為滿二叉樹
4.結(jié)點(diǎn)為n,層數(shù) = log2(n+1),向上取整

3.完全二叉樹

1.從0開始依次從左往右按順序一一對(duì)應(yīng)
2.滿二叉樹是一種特殊的完全二叉樹

4.二叉樹的性質(zhì)

• 1.根結(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第i層上最多有 2^(i-1) 個(gè)結(jié)點(diǎn)
• 2.根結(jié)點(diǎn)的二叉樹的深度為1，深度為K的二叉樹的最大結(jié)點(diǎn)數(shù)是 2^K-1
• 3.具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度k==log2(n+1) ,向上取整
• 4.對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上至下從左至右的順序?qū)λ泄?jié)點(diǎn)從0開始編號(hào)，則對(duì)于序號(hào)為i的結(jié)點(diǎn)有：

父結(jié)點(diǎn)下標(biāo)為 i : 左孩子的下標(biāo)：2i+1 ; 右孩子的下標(biāo) 2i+2;
子結(jié)點(diǎn)下標(biāo)為 i : 父結(jié)點(diǎn)下標(biāo)：（i - 1）/ 2

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

也就是說：度為0的結(jié)點(diǎn)比度為2的結(jié)點(diǎn)多一個(gè)==有兩個(gè)子節(jié)點(diǎn)的結(jié)點(diǎn)數(shù)=葉子結(jié)點(diǎn)數(shù)-1
n0＝n2＋1

練習(xí)：

A.n
完全二叉樹結(jié)點(diǎn)的個(gè)數(shù)分奇數(shù)和偶數(shù)兩種情況
奇數(shù)個(gè)結(jié)點(diǎn)，度為1的結(jié)點(diǎn)數(shù)為1
偶數(shù)個(gè)結(jié)點(diǎn)，度為1的結(jié)點(diǎn)數(shù)為0
聯(lián)立總結(jié)點(diǎn)數(shù)之和的式子和 n0-1=n2

點(diǎn)擊移步博客主頁，歡迎光臨~