在上一篇《樹(Tree)的基本概念》 中我們了解了樹中常用的一些概念名詞踢星。這一篇呢注重說一下二叉樹
的特點和一些概念灭翔。
二叉樹的類型
附圖1
真二叉樹
真二叉樹的每個節(jié)點的度要么是0蝠检,要么是2 。
以 「附圖1」 為例:圖中第一行的:空樹涎显、只有一個節(jié)點的樹坤检、最右側的二叉樹;第三行的二叉樹都是真二叉樹
滿二叉樹
滿二叉樹的每個節(jié)點的度要么是0期吓,要么是2 早歇,并且所有的葉子節(jié)點都在最后一層。
以 「附圖1」 為例:圖中 第三行的二叉樹即是真二叉樹 讨勤,又是滿二叉樹
完全二叉樹
所有的葉子節(jié)點都在最后兩層箭跳,并且葉子節(jié)點都靠左對齊。(如下:「附圖A」)
附圖A
二叉樹的特點
- 每個節(jié)點的度只有三中情況:0潭千、1衅码、2
- 每個節(jié)點的度最大為2(即最多有2顆子樹)
- 每個節(jié)點的左子樹和右子樹是有順序的
- 即使某一個節(jié)點只有一棵樹,也要區(qū)分左子樹和右子樹的
- 二叉樹是有序樹
- 同樣高度的二叉樹中滿二叉樹的總節(jié)點數(shù)量是最多的脊岳,葉子節(jié)點數(shù)量是最多的
- 滿二叉樹一定是真二叉樹 ,真二叉樹不一定是滿二叉樹
- 完全二叉樹從根節(jié)點到倒數(shù)第二層是一顆滿二叉樹
- 滿二叉樹一定是完全二叉樹 ,完全二叉樹不一定是滿二叉樹
附圖2
非空二叉樹的第n
層(n ≥ 1
)割捅,最多有
個節(jié)點
以 「附圖2」 中右側的 滿二叉樹為例, 推導
非空二叉樹
的第n
層最多有多少個節(jié)點:
規(guī)律為:
第一層( n = 1 ):= 1 個節(jié)點 奶躯;
第二層( n = 2 ):= 2 個節(jié)點 ;
第三層( n = 3 ):= 4 個節(jié)點 亿驾;
第四層( n = 4 ):= 8 個節(jié)點 嘹黔;
…………
高度為h
的非空二叉樹,最多有
個節(jié)點(h ≥ 1
)
推導: 當
h= 4
, 即非空二叉樹有4層莫瞬,這時的二叉樹就是 「附圖2」 中右側的 滿二叉樹儡蔓;
這時二叉樹的總節(jié)點數(shù)為:
第一層1個 + 第二層2個 + 第三層4個 + 第四層8個 = 15個;
即:1+ 2 + 4 + 8 =+
+
+
=
= 15
附圖3
對于任何一個非空二叉樹疼邀,如果葉子節(jié)點數(shù)量為
, 度為 2 的節(jié)點數(shù)量為
,則有:
=
+
假設度為1 的節(jié)點數(shù)量為
,二叉樹的節(jié)點總數(shù)為:
=
+
+
二叉樹的邊數(shù) T = (度為1 的節(jié)點數(shù)量
+ 度為 2 的節(jié)點數(shù)量
的 2 倍) = (二叉樹的節(jié)點總數(shù)
- 1) = (葉子節(jié)點數(shù)量
+ 度為1 的節(jié)點數(shù)量
+度為2的節(jié)點數(shù)量
)即:T = (
+
* 2 ) = (
- 1) = (
+
+
)
以「附圖3」 中的二叉樹為例推導:
A二叉樹:度為1的節(jié)點數(shù)量= 0携悯, 度為2的節(jié)點數(shù)量
= 0雳灾,葉子節(jié)點數(shù)量
= 1 = 0 + 1 ;二叉樹的節(jié)點總數(shù)為 1 = 1 + 0 + 0
B二叉樹:度為1的節(jié)點數(shù)量= 0拐袜,度為2的節(jié)點數(shù)量
= 1吉嚣,葉子節(jié)點數(shù)量
= 2 = 1 + 1 ;二叉樹的節(jié)點總數(shù)為 3 = 2 + 0 + 1
C二叉樹:度為1的節(jié)點數(shù)量= 0蹬铺,度為2的節(jié)點數(shù)量
= 3 尝哆,葉子節(jié)點數(shù)量
= 4 = 3 + 1 ;二叉樹的節(jié)點總數(shù)為 7 = 4 + 0 + 3
D二叉樹:度為1的節(jié)點數(shù)量= 2甜攀,度為2的節(jié)點數(shù)量
= 5 秋泄,葉子節(jié)點數(shù)量
= 6 = 7 + 1;二叉樹的節(jié)點總數(shù)為 13 = 6 + 2 + 5
E二叉樹:度為1的節(jié)點數(shù)量= 0赴邻,度為2的節(jié)點數(shù)量
= 7 印衔,葉子節(jié)點數(shù)量
= 8 = 7 + 1 ;二叉樹的節(jié)點總數(shù)為 15 = 8 + 0 + 7
……