快捷導(dǎo)航

樹(shù),二叉樹(shù)(完全二叉樹(shù),滿(mǎn)二叉樹(shù))概念圖解

更新時(shí)間：2021年07月02日 09:19:38 作者：摸金青年v

今天小編就為大家分享一篇關(guān)于二叉樹(shù)的圖文詳解，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧,希望能對(duì)你有所幫助

1、樹(shù)的定義

樹(shù)是n個(gè)結(jié)點(diǎn)的有限集合，有且僅有一個(gè)根結(jié)點(diǎn)，其余結(jié)點(diǎn)可分為m個(gè)根結(jié)點(diǎn)的子樹(shù)。

2、樹(shù)的概念

結(jié)點(diǎn)的度:一個(gè)結(jié)點(diǎn)擁有子樹(shù)的個(gè)數(shù)稱(chēng)為度。比如A的度為3，C的度為2，H的度為0。度為0的結(jié)點(diǎn)稱(chēng)為葉子節(jié)點(diǎn)（D,F,G,H）。樹(shù)的度是樹(shù)中所有結(jié)點(diǎn)的度的最大值，此樹(shù)的度為3。
樹(shù)中結(jié)點(diǎn)的最大層次成為樹(shù)的深度或高度。此樹(shù)的深度為4。
父節(jié)點(diǎn)A的子結(jié)點(diǎn)B,C,D；B,C,D也是兄弟節(jié)點(diǎn)
樹(shù)的集合稱(chēng)為森林.樹(shù)和森林之間有著密切的關(guān)系.刪除一個(gè)樹(shù)的根結(jié)點(diǎn),其所有原來(lái)的子樹(shù)都是樹(shù),構(gòu)成森林.用一個(gè)結(jié)點(diǎn)連接到森林的所有樹(shù)的根結(jié)點(diǎn)就構(gòu)成樹(shù).

3、二叉樹(shù)

二叉樹(shù)是每個(gè)節(jié)點(diǎn)最多擁有兩個(gè)子節(jié)點(diǎn)，左子樹(shù)和右子樹(shù)是有順序的不能任意顛倒。

4、二叉樹(shù)遍歷

前序遍歷（前根遍歷）：根——>左——>右

中序遍歷（中根遍歷）：左——>根——>右

后序遍歷（后根遍歷）：左——>右——>根

已知前序和中序，求后序問(wèn)題，前序 ABDGCEFH 中序 DGBAECHF

解法：根據(jù)前序、中序綜合判斷畫(huà)出樹(shù)的節(jié)點(diǎn)圖，然后再寫(xiě)后序遍歷：DGBEHFCA

（前序和中序的子樹(shù)也滿(mǎn)足前序或中序的規(guī)則）

二叉樹(shù)的深度優(yōu)先遍歷（DFS）與廣度優(yōu)先遍歷（BFS）

DFS深度優(yōu)先遍歷：從根節(jié)點(diǎn)出發(fā)，沿著左子樹(shù)方向進(jìn)行縱向遍歷，直到找到葉子節(jié)點(diǎn)為止。然后回溯到前一個(gè)節(jié)點(diǎn)，進(jìn)行右子樹(shù)節(jié)點(diǎn)的遍歷，直到遍歷完所有可達(dá)節(jié)點(diǎn)為止。利用數(shù)據(jù)結(jié)構(gòu)“?！?，父節(jié)點(diǎn)入棧，父節(jié)點(diǎn)出棧，先右子節(jié)點(diǎn)入棧，后左子節(jié)點(diǎn)入棧。遞歸遍歷全部節(jié)點(diǎn)。

DFS:ABDGCEFH

BFS廣度優(yōu)先遍歷：從根節(jié)點(diǎn)出發(fā)，在橫向遍歷二叉樹(shù)層段節(jié)點(diǎn)的基礎(chǔ)上縱向遍歷二叉樹(shù)的層次。利用數(shù)據(jù)結(jié)構(gòu)“隊(duì)列”，父節(jié)點(diǎn)入隊(duì)，父節(jié)點(diǎn)出隊(duì)列，先左子節(jié)點(diǎn)入隊(duì)，后右子節(jié)點(diǎn)入隊(duì)。遞歸遍歷全部節(jié)點(diǎn)。

BFS：ABCDGEFH

5、滿(mǎn)二叉樹(shù)

高度為h，由2^h-1個(gè)節(jié)點(diǎn)構(gòu)成的二叉樹(shù)稱(chēng)為滿(mǎn)二叉樹(shù)。

6、完全二叉樹(shù)

完全二叉樹(shù)是由滿(mǎn)二叉樹(shù)而引出來(lái)的，若設(shè)二叉樹(shù)的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)(即1~h-1層為一個(gè)滿(mǎn)二叉樹(shù))，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹(shù)。

堆一般都是用完全二叉樹(shù)來(lái)實(shí)現(xiàn)的。