1、樹的定義

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

2、樹的概念 

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

 3、二叉樹 

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

  4、二叉樹遍歷

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

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

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

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

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

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

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

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

DFS:ABDGCEFH

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

BFS：ABCDGEFH 

5、滿二叉樹 

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

6、完全二叉樹 

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

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

總結(jié)

本篇文章就到這里了，希望可以給你帶來一些幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！

最新評論