各種實現和應用以后放鏈接
一、二叉樹的基本概念
二叉樹:二叉樹是每個節點最多有兩個子樹的樹結構。
根節點:一棵樹最上面的節點稱為根節點。
父節點、子節點:如果一個節點下面連接多個節點,那么該節點稱為父節點,它下面的節點稱為子 節點。
葉子節點:沒有任何子節點的節點稱為葉子節點。
兄弟節點:具有相同父節點的節點互稱為兄弟節點。
節點度:節點擁有的子樹數。上圖中,13的度為2,46的度為1,28的度為0。
樹的深度:從根節點開始(其深度為0)自頂向下逐層累加的。上圖中,13的深度是1,30的深度是2,28的深度是3。
樹的高度:從葉子節點開始(其高度為0)自底向上逐層累加的。54的高度是2,根節點23的高度是3。
對于樹中相同深度的每個節點來說,它們的高度不一定相同,這取決于每個節點下面的葉子節點的深度。上圖中,13和54的深度都是1,但是13的高度是1,54的高度是2。
二、二叉樹的類型
類型 | 定義 | 圖示 |
滿二叉樹 Full Binary Tree | 除最后一層無任何子節點外,每一層上的所有節點都有兩個子節點,最后一層都是葉子節點。滿足下列性質: 1)一顆樹深度為h,最大層數為k,深度與最大層數相同,k=h; 2)葉子節點數(最后一層)為2k?1; 3)第 i 層的節點數是:2i?1; 4)總節點數是:2k?1,且總節點數一定是奇數。 | |
完全二叉樹 Complete Binary Tree | 若設二叉樹的深度為h,除第 h 層外,其它各層 (1~h-1) 的結點數都達到最大個數,第 h 層所有的結點都連續集中在最左邊,這就是完全二叉樹。滿足下列性質: 1)只允許最后一層有空缺結點且空缺在右邊,即葉子節點只能在層次最大的兩層上出現; 2)對任一節點,如果其右子樹的深度為j,則其左子樹的深度必為j或j+1。 即度為1的點只有1個或0個; 3)除最后一層,第 i 層的節點數是:2i?1; 4)有n個節點的完全二叉樹,其深度為:log2n+1或為log2n+1; 5)滿二叉樹一定是完全二叉樹,完全二叉樹不一定是滿二叉樹。 | |
平衡二叉樹 Balanced Binary Tree | 又被稱為AVL樹,它是一顆空樹或左右兩個子樹的高度差的絕對值不超過 1,并且左右兩個子樹都是一棵平衡二叉樹。 | |
二叉搜索樹 Binary Search Tree | 又稱二叉查找樹、二叉排序樹(Binary Sort Tree)。它是一顆空樹或是滿足下列性質的二叉樹: 1)若左子樹不空,則左子樹上所有節點的值均小于或等于它的根節點的值; 2)若右子樹不空,則右子樹上所有節點的值均大于或等于它的根節點的值; 3)左、右子樹也分別為二叉排序樹。 | |
紅黑樹 Red Black Tree | 是每個節點都帶有顏色屬性(顏色為紅色或黑色)的自平衡二叉查找樹,滿足下列性質: 1)節點是紅色或黑色; 2)根節點是黑色; 3)所有葉子節點都是黑色; 4)每個紅色節點必須有兩個黑色的子節點。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點。) 5)從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點。 |
?
?
?
?
?
?
?
?
?