1、樹的定義

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

2、樹的概念 

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

 3、二叉樹 

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

  4、二叉樹遍歷

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

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

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

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

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

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

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

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

DFS:ABDGCEFH

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

BFS：ABCDGEFH 

5、滿二叉樹 

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

6、完全二叉樹 

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

堆一般都是用完全二叉樹來實現的。

總結

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

最新評論