日韩欧美熟女啪啪,国产一区亚洲人人

1. 樹(shù)(Tree)

(1) 基礎(chǔ)概念

1> 節(jié)點(diǎn)

節(jié)點(diǎn)、根節(jié)點(diǎn)、父節(jié)點(diǎn)、子節(jié)點(diǎn)、兄弟節(jié)點(diǎn)

2> 樹(shù)、子樹(shù)

一棵樹(shù)可以沒(méi)有任何節(jié)點(diǎn)，稱為空樹(shù)

一棵樹(shù)可以只有1個(gè)節(jié)點(diǎn)，也就是只有根節(jié)點(diǎn)

子樹(shù)、左子樹(shù)、右子樹(shù)

3> 度(degree)

節(jié)點(diǎn)的度：子樹(shù)的個(gè)數(shù)

樹(shù)的度：所有節(jié)點(diǎn)度中的最大值

4> 葉子節(jié)點(diǎn)(leaf)

葉子節(jié)點(diǎn)：度為0的節(jié)點(diǎn)

非葉子節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)

5> 層數(shù)(level)

層數(shù)：根節(jié)點(diǎn)在第1層，根節(jié)點(diǎn)的子節(jié)點(diǎn)在第2層，以此類推

6> 深度(depth)、高度(height)

節(jié)點(diǎn)的深度：從根節(jié)點(diǎn) 到當(dāng)前節(jié)點(diǎn) 的唯一路徑上的節(jié)點(diǎn)總數(shù)

節(jié)點(diǎn)的高度：從當(dāng)前節(jié)點(diǎn) 到最遠(yuǎn)葉子節(jié)點(diǎn) 的路徑上的節(jié)點(diǎn)總數(shù)

樹(shù)的深度：所有節(jié)點(diǎn)深度中的最大值

樹(shù)的高度：所有節(jié)點(diǎn)高度中的最大值

樹(shù)的深度等于樹(shù)的高度

二叉樹(shù)

(2) 樹(shù)的種類

有序樹(shù)：樹(shù)中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間有順序關(guān)系

無(wú)序樹(shù)(自由樹(shù))：樹(shù)中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間沒(méi)有順序關(guān)系

森林：由m(m≥0)棵互不相交的樹(shù)組成的集合

2. 二叉樹(shù)(Binary Tree)

(1) 基礎(chǔ)概念

1> 二叉樹(shù)的特點(diǎn)

每個(gè)節(jié)點(diǎn)的度最大為2 (最多擁有2棵子樹(shù))

左子樹(shù) 和右子樹(shù) 是有順序的

即使某節(jié)點(diǎn)只有一棵子樹(shù)，也要區(qū)分左右子樹(shù)

2> 二叉樹(shù)的性質(zhì)

非空二叉樹(shù)的第i層，最多有 $2^{(i-1)}$ 個(gè)節(jié)點(diǎn)(i≥1)

在高度為h的二叉樹(shù)上最多有 $2^{h}$ - 1個(gè)節(jié)點(diǎn)(h≥1)

對(duì)于任何一棵非空二叉樹(shù)，如果葉子節(jié)點(diǎn)個(gè)數(shù)為 $n_0$ ，度為1的節(jié)點(diǎn)個(gè)數(shù)為 $n_1$ ，度為2的節(jié)點(diǎn)個(gè)數(shù)為 $n_2$

則有: $n_0$ = $n_2$ + 1

二叉樹(shù)的節(jié)點(diǎn)總數(shù)n = $n_0$ + $n_1$ + $n_2$

二叉樹(shù)的邊數(shù)T = $n_1$ +2* $n_2$ = n-1 = n0+ $n_1$ + $n_2$ -1

(2) 真二叉樹(shù)(Proper Binary Tree)

真二叉樹(shù)：所有節(jié)點(diǎn)的度要么為0，要么為2

真二叉樹(shù)、滿二叉樹(shù)

(3) 滿二叉樹(shù)(Full Binary Tree)

滿二叉樹(shù)：最后一層節(jié)點(diǎn)的度都為0，其他節(jié)點(diǎn)的度都為2

在同樣高度的二叉樹(shù)中，滿二叉樹(shù)的葉子節(jié)點(diǎn) 數(shù)量最多、總節(jié)點(diǎn) 數(shù)量最多

滿二叉樹(shù) 一定是真二叉樹(shù)，真二叉樹(shù) 不一定是滿二叉樹(shù)

假設(shè)滿二叉樹(shù)的高度為h(h≥1)，那么

第i層的節(jié)點(diǎn)數(shù)量： $2^{i}$ - 1

葉子節(jié)點(diǎn)數(shù)量： $2^{h}$ - 1

總節(jié)點(diǎn)數(shù)量n

n= $2^{h}$ - 1= $2^{0}$ + $2^{1}$ + $2^{2}$ + ... + $2^{(h-1)}$

h = $log_2{(n+1)}$

(4) 完全二叉樹(shù)(Complete Binary Tree)

1> 概念

完全二叉樹(shù)：對(duì)節(jié)點(diǎn)從上至下、左至右開(kāi)始編號(hào)，其所有編號(hào)都能與相同高度的滿二叉樹(shù)中的編號(hào)對(duì)應(yīng)

葉子節(jié)點(diǎn) 只會(huì)出現(xiàn) 最后2層，最后1層的葉子結(jié)點(diǎn) 都靠左對(duì)齊

完全二叉樹(shù)從根結(jié)點(diǎn) 至倒數(shù)第2層是一棵滿二叉樹(shù)

滿二叉樹(shù) 一定是完全二叉樹(shù)，完全二叉樹(shù) 不一定是滿二叉樹(shù)

完全二叉樹(shù)

2> 性質(zhì)

度為1的節(jié)點(diǎn)只有左子樹(shù)

度為1的節(jié)點(diǎn)要么是1個(gè)，要么是0個(gè)

同樣節(jié)點(diǎn)數(shù)量的二叉樹(shù)，完全二叉樹(shù)的高度最小

假設(shè)完全二叉樹(shù)的高度為h (h≥1)，那么

至少有 $2^{(h-1)}$ 個(gè)節(jié)點(diǎn)( $2^{0}$ + $2^{1}$ + $2^{2}$ + ... + $2^{(h-2)}$ + 1 )

最多有 $2^{h}$ - 1 個(gè)節(jié)點(diǎn)( $2^{0}$ + $2^{1}$ + $2^{2}$ + ... + $2^{(h-1)}$ ，滿二叉樹(shù) )

總節(jié)點(diǎn)數(shù)量為n

$2^{(h-1)}$ ≤ n < $2^{h}$

h - 1 ≤ $log_2{n}$ < h

h = floor( $log_2{n}$ ) + 1

【floor是向下取整，ceiling是向上取整】

一棵有 n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)(n>0)，從上到下、從左到右對(duì)節(jié)點(diǎn)從1開(kāi)始進(jìn)行編號(hào)，對(duì)任意第i個(gè)節(jié)點(diǎn)

如果 i = 1，它是根節(jié)點(diǎn)

如果 i > 1，它的父節(jié)點(diǎn)編號(hào)為 floor( i / 2 )

如果 2i ≤ n，它的左子節(jié)點(diǎn)編號(hào)為 2i

如果 2i > n，它無(wú)左子節(jié)點(diǎn)

如果 2i + 1 ≤ n，它的右子節(jié)點(diǎn)編號(hào)為 2i + 1

如果 2i + 1 > n，它無(wú)右子節(jié)點(diǎn)

3. 面試題

Q: 如果一棵完全二叉樹(shù)有768個(gè)節(jié)點(diǎn)，求葉子節(jié)點(diǎn)的個(gè)數(shù)？

解題步驟一：

假設(shè)葉子節(jié)點(diǎn)個(gè)數(shù)為 $n_0$ ，度為1的節(jié)點(diǎn)個(gè)數(shù)為 $n_1$ ，度為2的節(jié)點(diǎn)個(gè)數(shù)為 $n_2$
總結(jié)點(diǎn)個(gè)數(shù)n = $n_0$ + $n_1$ + $n_2$ ，而且 $n_0$ = $n_2$ + 1
n = 2 $n_0$ + $n_1$ - 1

解題步驟二：

完全二叉樹(shù)的 $n_1$ 要么為0，要么為1：
$n_1$ 為1時(shí)，n = 2 $n_0$ ，n必然是偶數(shù)
葉子節(jié)點(diǎn)個(gè)數(shù) $n_0$ = n / 2，非葉子節(jié)點(diǎn)個(gè)數(shù) $n_1$ + $n_2$ = n / 2
$n_1$ 為0時(shí)，n = 2 $n_0$ - 1，n必然是奇數(shù)
葉子節(jié)點(diǎn)個(gè)數(shù) $n_0$ = (n + 1) / 2，非葉子節(jié)點(diǎn)個(gè)數(shù) $n_1$ + $n_2$ = (n - 1) / 2

解題步驟三：

葉子節(jié)點(diǎn)個(gè)數(shù) $n_0$ = floor((n + 1) / 2) = ceiling(n / 2)

非葉子節(jié)點(diǎn)個(gè)數(shù) $n_1$ + $n_2$ = floor(n / 2) = ceiling((n - 1) / 2)

floor((n + 1) / 2) 即 (n + 1) / 2 或 (n + 1) >> 1

得出答案：

因此葉子節(jié)點(diǎn)個(gè)數(shù)為 768 / 2 = 384

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

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

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

1. 樹(shù)(Tree)

(1) 基礎(chǔ)概念

1> 節(jié)點(diǎn)

2> 樹(shù)、子樹(shù)

3> 度(degree)

4> 葉子節(jié)點(diǎn)(leaf)

5> 層數(shù)(level)

6> 深度(depth)、高度(height)

(2) 樹(shù)的種類

2. 二叉樹(shù)(Binary Tree)

(1) 基礎(chǔ)概念

1> 二叉樹(shù)的特點(diǎn)

2> 二叉樹(shù)的性質(zhì)

(2) 真二叉樹(shù)(Proper Binary Tree)

(3) 滿二叉樹(shù)(Full Binary Tree)

(4) 完全二叉樹(shù)(Complete Binary Tree)

1> 概念

2> 性質(zhì)

3. 面試題

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

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

1. 樹(shù)(Tree)

(1) 基礎(chǔ)概念

1> 節(jié)點(diǎn)

2> 樹(shù)、子樹(shù)

3> 度(degree)

4> 葉子節(jié)點(diǎn)(leaf)

5> 層數(shù)(level)

6> 深度(depth)、高度(height)

(2) 樹(shù)的種類

2. 二叉樹(shù)(Binary Tree)

(1) 基礎(chǔ)概念

1> 二叉樹(shù)的特點(diǎn)

2> 二叉樹(shù)的性質(zhì)

(2) 真二叉樹(shù)(Proper Binary Tree)

(3) 滿二叉樹(shù)(Full Binary Tree)

(4) 完全二叉樹(shù)(Complete Binary Tree)

1> 概念

2> 性質(zhì)

3. 面試題

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

6> 深度(depth)、高度(height)