二叉樹（Binary Tree）類型特點(diǎn)

在上一篇《樹（Tree）的基本概念》 中我們了解了樹中常用的一些概念名詞。這一篇呢注重說一下二叉樹的特點(diǎn)和一些概念。

二叉樹的類型

附圖1

binary_tree.jpg

真二叉樹

真二叉樹的每個(gè)節(jié)點(diǎn)的度要么是0，要么是2 。

以 「附圖1」 為例：圖中第一行的：空樹、只有一個(gè)節(jié)點(diǎn)的樹、最右側(cè)的二叉樹；第三行的二叉樹都是真二叉樹

滿二叉樹

滿二叉樹的每個(gè)節(jié)點(diǎn)的度要么是0，要么是2 ，并且所有的葉子節(jié)點(diǎn)都在最后一層。

以 「附圖1」 為例：圖中 第三行的二叉樹即是真二叉樹 ，又是滿二叉樹

完全二叉樹

所有的葉子節(jié)點(diǎn)都在最后兩層，并且葉子節(jié)點(diǎn)都靠左對齊。（如下：「附圖A」）

附圖A

tree_four.jpg

二叉樹的特點(diǎn)

  • 每個(gè)節(jié)點(diǎn)的度只有三中情況：0、1、2
  • 每個(gè)節(jié)點(diǎn)的度最大為2（即最多有2顆子樹）
  • 每個(gè)節(jié)點(diǎn)的左子樹和右子樹是有順序的
  • 即使某一個(gè)節(jié)點(diǎn)只有一棵樹，也要區(qū)分左子樹和右子樹的
  • 二叉樹是有序樹
  • 同樣高度的二叉樹中滿二叉樹的總節(jié)點(diǎn)數(shù)量是最多的，葉子節(jié)點(diǎn)數(shù)量是最多的
  • 滿二叉樹一定是真二叉樹 ，真二叉樹不一定是滿二叉樹
  • 完全二叉樹從根節(jié)點(diǎn)到倒數(shù)第二層是一顆滿二叉樹
  • 滿二叉樹一定是完全二叉樹 ，完全二叉樹不一定是滿二叉樹

附圖2

tree_two.jpg
非空二叉樹的第n層(n ≥ 1)，最多有\color{red}{2^n}\color{red}{^-}\color{red}{^1} 個(gè)節(jié)點(diǎn)

以 「附圖2」 中右側(cè)的 滿二叉樹為例, 推導(dǎo)非空二叉樹的第n層最多有多少個(gè)節(jié)點(diǎn)：
規(guī)律為：
第一層（ n = 1 ）：\color{red}{2^1}\color{red}{^-}\color{red}{^1} = 1 個(gè)節(jié)點(diǎn) ；
第二層（ n = 2 ）：\color{red}{2^2}\color{red}{^-}\color{red}{^1} = 2 個(gè)節(jié)點(diǎn) ；
第三層（ n = 3 ）：\color{red}{2^3}\color{red}{^-}\color{red}{^1} = 4 個(gè)節(jié)點(diǎn) ；
第四層（ n = 4 ）：\color{red}{2^4}\color{red}{^-}\color{red}{^1} = 8 個(gè)節(jié)點(diǎn) ；
…………

高度為h的非空二叉樹，最多有\color{red}{2^h}\color{red}{-}\color{red}{1} 個(gè)節(jié)點(diǎn)(h ≥ 1)

推導(dǎo)： 當(dāng) h= 4, 即非空二叉樹有4層，這時(shí)的二叉樹就是 「附圖2」 中右側(cè)的 滿二叉樹；
這時(shí)二叉樹的總節(jié)點(diǎn)數(shù)為：
第一層1個(gè) + 第二層2個(gè) + 第三層4個(gè) + 第四層8個(gè) = 15個(gè)；
即：1+ 2 + 4 + 8 = \color{red}{2^0} + \color{red}{2^1} + \color{red}{2^2}+ \color{red}{2^3} = \color{red}{2^4}\color{red}{-}\color{red}{1} = 15

附圖3

tree_three.jpg
對于任何一個(gè)非空二叉樹，如果葉子節(jié)點(diǎn)數(shù)量為\color{red}{N_0} , 度為 2 的節(jié)點(diǎn)數(shù)量為 \color{red}{N_2} ，則有：\color{red}{N_0} = \color{red}{N_2} + \color{red}{1}
假設(shè)度為1 的節(jié)點(diǎn)數(shù)量為\color{red}{N_1} ，二叉樹的節(jié)點(diǎn)總數(shù)為：\color{red}{N} = \color{red}{N_0} + \color{red}{N_1} + \color{red}{N_2}
二叉樹的邊數(shù) T = （度為1 的節(jié)點(diǎn)數(shù)量 \color{red}{N_1}+ 度為 2 的節(jié)點(diǎn)數(shù)量\color{red}{N_2}的 2 倍） = （二叉樹的節(jié)點(diǎn)總數(shù)\color{red}{N} - 1） = （葉子節(jié)點(diǎn)數(shù)量\color{red}{N_0} + 度為1 的節(jié)點(diǎn)數(shù)量 \color{red}{N_1} +度為2的節(jié)點(diǎn)數(shù)量 \color{red}{N_2}）即：T = （ \color{red}{N_1} + \color{red}{N_2} * 2 ） = （ \color{red}{N} - 1） = （ \color{red}{N_0} + \color{red}{N_1} + \color{red}{N_2}）

以「附圖3」 中的二叉樹為例推導(dǎo)：
A二叉樹：度為1的節(jié)點(diǎn)數(shù)量\color{red}{N_1}= 0， 度為2的節(jié)點(diǎn)數(shù)量\color{red}{N_2}= 0，葉子節(jié)點(diǎn)數(shù)量\color{red}{N_0} = 1 = 0 + 1 ；二叉樹的節(jié)點(diǎn)總數(shù)為 1 = 1 + 0 + 0
B二叉樹：度為1的節(jié)點(diǎn)數(shù)量\color{red}{N_1}= 0，度為2的節(jié)點(diǎn)數(shù)量\color{red}{N_2}= 1，葉子節(jié)點(diǎn)數(shù)量\color{red}{N_0} = 2 = 1 + 1 ；二叉樹的節(jié)點(diǎn)總數(shù)為 3 = 2 + 0 + 1
C二叉樹：度為1的節(jié)點(diǎn)數(shù)量\color{red}{N_1}= 0，度為2的節(jié)點(diǎn)數(shù)量\color{red}{N_2}= 3 ，葉子節(jié)點(diǎn)數(shù)量\color{red}{N_0} = 4 = 3 + 1 ；二叉樹的節(jié)點(diǎn)總數(shù)為 7 = 4 + 0 + 3
D二叉樹：度為1的節(jié)點(diǎn)數(shù)量\color{red}{N_1}= 2，度為2的節(jié)點(diǎn)數(shù)量\color{red}{N_2}= 5 ，葉子節(jié)點(diǎn)數(shù)量\color{red}{N_0} = 6 = 7 + 1；二叉樹的節(jié)點(diǎn)總數(shù)為 13 = 6 + 2 + 5
E二叉樹：度為1的節(jié)點(diǎn)數(shù)量\color{red}{N_1}= 0，度為2的節(jié)點(diǎn)數(shù)量\color{red}{N_2}= 7 ，葉子節(jié)點(diǎn)數(shù)量\color{red}{N_0} = 8 = 7 + 1 ；二叉樹的節(jié)點(diǎn)總數(shù)為 15 = 8 + 0 + 7
……

假設(shè)一個(gè)滿二叉樹的高度為h (h ≥1 ) , 那么第n層的節(jié)點(diǎn)數(shù)量為\color{red}{2^n}\color{red}{^-}\color{red}{^1} ； 葉子節(jié)點(diǎn)數(shù)量為 \color{red}{2^h}\color{red}{^-}\color{red}{^1} ；總節(jié)點(diǎn)數(shù)量為 n = \color{red}{2^h}\color{red}{-}\color{red}{1} = \color{red}{2^0} + \color{red}{2^1} + \color{red}{2^2} + ..... + \color{red}{2^h}\color{red}{^-}\color{red}{^1} ;高度 h = \color{red}\log_\color{red}{2}\color{red}{(n+1)}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容