本文屬于數(shù)據(jù)結構專欄文章，適合數(shù)據(jù)結構入門者學習，涵蓋數(shù)據(jù)結構基礎的知識和內容體系，文章在介紹數(shù)據(jù)結構時會配合上
動圖演示，方便初學者在學習數(shù)據(jù)結構時理解和學習，了解數(shù)據(jù)結構系列專欄點擊下方鏈接。
- 博客主頁：Duck Bro 博客主頁
- 系列專欄：數(shù)據(jù)結構專欄
- 關注博主，后期持續(xù)更新系列文章
- 如果有錯誤感謝請大家批評指出，及時修改
- 感謝大家點贊??收藏?評論?
數(shù)據(jù)結構入門 — 二叉樹的概念、性質及結構
本文關鍵字：二叉樹、概念、存儲結構、性質
一、二叉樹的概念
二叉樹是一種數(shù)據(jù)結構，由一組節(jié)點組成，每個節(jié)點最多有兩個子節(jié)點，稱為左子節(jié)點和右子節(jié)點。二叉樹可以為空樹，也可以是一個只有根節(jié)點而沒有子節(jié)點的單節(jié)點樹，或者是一個有多個節(jié)點的樹，每個節(jié)點都有且僅有一個父節(jié)點。
對于任意的二叉樹都是由以下幾種情況復合而成的：
一個二叉樹要么為空樹，要么由一個根節(jié)點和兩棵分別稱為左子樹和右子樹的二叉樹組成。
注意：
- 二叉樹不存在度大于2的結點
- 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹
二、特殊的二叉樹
特殊的二叉樹有很多種，幾種特殊的二叉樹都有其獨特的特點，在不同的場景下有不同的應用
| 名稱 | 說明 |
|---|---|
| 完全二叉樹 | 除了最后一層節(jié)點不滿以外，其它每層節(jié)點數(shù)都達到最大值。在最后一層上只缺少右側連續(xù)若干節(jié)點。 |
| 滿二叉樹 | 每個節(jié)點都有零或兩個子節(jié)點，且所有葉子節(jié)點都在同一層上。 |
| 平衡二叉樹 | 一棵空樹或者左右兩個子樹高度差的絕對值不超過 1，且左右兩個子樹都是平衡二叉樹。 |
| 二叉搜索樹（BST） | 一棵空樹或者滿足以下特點的二叉樹：對于任意節(jié)點，左子樹中的所有節(jié)點小于該節(jié)點的值，右子樹中的所有節(jié)點大于該節(jié)點的值。 |
| 紅黑樹 | 一棵自平衡二叉搜索樹，具有以下特點：每個節(jié)點要么是紅色，要么是黑色，根節(jié)點是黑色，葉子節(jié)點是黑色的空節(jié)點，紅色節(jié)點的子節(jié)點只能是黑色的節(jié)點，從任一節(jié)點到其每個葉子節(jié)點的所有路徑都包含相同數(shù)目的黑色節(jié)點。 |
| B 樹 | 一種自平衡的多路搜索樹，能夠支持對數(shù)據(jù)的高效操作，主要應用于文件系統(tǒng)和數(shù)據(jù)庫管理系統(tǒng)等領域。 |
三、二叉樹的性質
- 若規(guī)定根節(jié)點的層數(shù)為1，則一棵非空二叉樹的第i層上最多有 2 ( n ? 1 ) 2^{(n-1)} 2(n?1)個結點.
- 若規(guī)定根節(jié)點的層數(shù)為1，則深度為h的二叉樹的最大結點數(shù)是 2 h ? 1 2^h -1 2h?1 .
- 對任何一棵二叉樹, 如果度為0其葉結點個數(shù)為 n 0 n_{0} n0? , 度為2的分支結點個數(shù)為 ,則有 n 0 = n 2 + 1 n_{0}=n_{2}+1 n0?=n2?+1
- 若規(guī)定根節(jié)點的層數(shù)為1，具有n個結點的滿二叉樹的深度，
h
=
l
o
g
2
(
n
+
1
)
h= log_{2}(n+1)
h=log2?(n+1). (ps：
l
o
g
2
(
n
+
1
)
log_{2}(n+1)
log2?(n+1)是log以2
為底，n+1為對數(shù)) - 對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序對所有節(jié)點從0開始編號，則對于序號為 i 的結點有：
- 若i>0，i位置節(jié)點的雙親序號：(i-1)/2；i=0，i為根節(jié)點編號，無雙親節(jié)點
- 若2i+1<n，左孩子序號：2i+1，2i+1>=n否則無左孩子
- 若2i+2<n，右孩子序號：2i+2，2i+2>=n否則無右孩子
四、二叉樹的結構
二叉樹有兩種基本的存儲結構：順序存儲和鏈式存儲。
1. 順序存儲法
順序結構存儲就是使用數(shù)組來存儲，一般使用數(shù)組只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費。而現(xiàn)實中使用中只有堆才會使用數(shù)組來存儲，關于堆后面的文章會專門講解。二叉樹順序存儲在物理上是一個數(shù)組，在邏輯上是一顆二叉樹。
2. 鏈式存儲法
二叉樹的鏈式存儲結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。 通常的方法是鏈表中每個結點由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結點左孩子和右孩子所在的鏈結點的存儲地址 。文章來源：http://www.zghlxwxcb.cn/news/detail-724089.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-724089.html
到了這里，關于數(shù)據(jù)結構入門 — 二叉樹的概念、性質及結構的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
