手機(jī)網(wǎng)站會員識別功能縱橫seo
目錄
一、樹
1.定義
（1）樹的構(gòu)成
（2）度
2.二叉樹
（1）定義
（2）二叉樹的遍歷
（3）遍歷特性
二、練習(xí)?
1.二叉樹
（1）創(chuàng)建二叉樹
（2）前序遍歷
（3）中序遍歷
（4）后序遍歷
（5）獲取結(jié)點(diǎn)個數(shù)
（6）獲取層數(shù)
（7）層序遍歷
（8）銷毀二叉樹
一、樹
1.定義
（1）樹的構(gòu)成
? ? ?①樹：樹是由n個結(jié)點(diǎn)組成的有限集
? ? ? ? ? 若n = 0， 則為空樹。
? ? ?②根：樹只有一個根結(jié)點(diǎn)
? ? ? ? ? 除根外，其他所有結(jié)點(diǎn)只有一個前驅(qū)結(jié)點(diǎn)，但可以有多個后繼結(jié)點(diǎn)。(一對多)
? ? ?③葉子：葉子結(jié)點(diǎn)，即終端結(jié)點(diǎn)
? ? ? ? ??只有前驅(qū)結(jié)點(diǎn)，沒有后繼結(jié)點(diǎn)。
? ? ?④分支：分支結(jié)點(diǎn)，即非終端結(jié)點(diǎn)
? ? ? ? ??既有前驅(qū)節(jié)點(diǎn)，也有后繼的結(jié)點(diǎn)。
?? ? ⑤森林：n個互不相交的樹的集合。
（2）度
???????①結(jié)點(diǎn)度：子節(jié)點(diǎn)（后繼結(jié)點(diǎn)）的個數(shù)
? ? ? ?②樹的（廣）度：樹中各結(jié)點(diǎn)度的最大值?
? ? ? ?③深度：從根節(jié)點(diǎn)到最底層節(jié)點(diǎn)的層數(shù)
2.二叉樹
（1）定義
???????①二叉樹：任意一個節(jié)點(diǎn)的子節(jié)點(diǎn)個數(shù)不能超過2個(樹的度為2)，且子節(jié)點(diǎn)的位置不可更改。
? ? ? ?②滿二叉樹：在不增加樹的層數(shù)的前提下，無法再增加一個結(jié)點(diǎn)的二叉樹
?? ??? ?
? ? ? ? ? ? ? ? ? ? ? ?特性：滿二叉樹第K層有2^(k-1)個節(jié)點(diǎn)
? ? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? K層滿二叉樹總共有2^k-1個節(jié)點(diǎn)
? ? ? ?③完全二叉樹：只是刪除了滿二叉樹最底層最右邊的連續(xù)若干個節(jié)點(diǎn)，形成了完全二叉樹。
???????????????????在滿二叉樹的基礎(chǔ)上，按照從左向右，從上至下的順序刪除若干個連續(xù)的結(jié)點(diǎn)，構(gòu)成完全二叉樹；
? ? ? ? ? ? ? ? ? ?在滿二叉樹的基礎(chǔ)上，按照從右至左，從下至上的順序插入若干個連續(xù)的結(jié)點(diǎn) ，構(gòu)成完全二叉樹；
? ? ? ? ? ? ? ? ? ? 滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹。
? ? ? ? ? ? ? ? ? ? ? ? ? ? 滿二叉樹 ==> 完全二叉樹
? ? ? ?????????????????? ? ?完全二叉樹 =/=> 滿二叉樹
（2）二叉樹的遍歷
- 深度優(yōu)先遍歷算法：
????????①前序遍歷：根結(jié)點(diǎn)，左子樹，右子樹? ? ? ? 例：ABEHMFDICG
????????②中序遍歷：左子樹，根結(jié)點(diǎn)，右子樹? ? ? ? 例：HEMBFAICDG
????????③后序遍歷：左子樹，右子樹，根結(jié)點(diǎn)? ? ? ? 例：HMEFBCIGDA
- 廣度優(yōu)先遍歷算法：
????????④層序遍歷：從上至下，從左到右，逐層遍歷? ? ? ? 例：ABDEFIGHMC
（3）遍歷特性
????????已知前序遍歷序列和中序遍歷序列，可以唯一確定一棵二叉樹；
????????已知后序遍歷序列和中序遍歷序列，可以唯一確定一棵二叉樹；
在編程中，我們常在葉子結(jié)點(diǎn)后添上“#”，用作識別終止的標(biāo)志，等價于NULL。
例如：ABEH##M##F##DI#C##G##
在創(chuàng)建二叉樹時，常將每個結(jié)點(diǎn)設(shè)置成三部分，分別裝數(shù)據(jù)與左右后繼結(jié)點(diǎn)的地址。
二、練習(xí)?
1.二叉樹
（1）創(chuàng)建二叉樹
?（2）前序遍歷
（3）中序遍歷
（4）后序遍歷
?（5）獲取結(jié)點(diǎn)個數(shù)
（6）獲取層數(shù)
?（7）層序遍歷
（8）銷毀二叉樹
