樹,二叉樹(完全二叉樹,滿二叉樹)概念圖解

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

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

1、樹的定義

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

2、樹的概念

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

3、二叉樹

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

4、二叉樹遍歷

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

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

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

已知前序和中序，求后序問題，前序 ABDGCEFH 中序 DGBAECHF

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

（前序和中序的子樹也滿足前序或中序的規(guī)則）

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

DFS深度優(yōu)先遍歷：從根節(jié)點(diǎn)出發(fā)，沿著左子樹方向進(jìn)行縱向遍歷，直到找到葉子節(jié)點(diǎn)為止。然后回溯到前一個(gè)節(jié)點(diǎn)，進(jìn)行右子樹節(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ā)，在橫向遍歷二叉樹層段節(jié)點(diǎn)的基礎(chǔ)上縱向遍歷二叉樹的層次。利用數(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、滿二叉樹

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

6、完全二叉樹

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

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