二叉樹(shù)簡(jiǎn)介

關(guān)于樹(shù)的介紹，請(qǐng)參考：https://www.jb51.net/article/222488.htm

一、二叉樹(shù)簡(jiǎn)介

二叉樹(shù)是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)，是一種特殊的樹(shù)，如下圖，就是一棵二叉樹(shù)。

二叉樹(shù)是由n(n>=0)個(gè)節(jié)點(diǎn)組成的數(shù)據(jù)集合。當(dāng) n=0 時(shí)，二叉樹(shù)中沒(méi)有節(jié)點(diǎn)，稱(chēng)為空二叉樹(shù)。當(dāng) n=1 時(shí)，二叉樹(shù)只有根節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)。當(dāng) n>1 時(shí)，二叉樹(shù)的每個(gè)節(jié)點(diǎn)都最多只能有兩個(gè)子樹(shù)，遞歸地構(gòu)建成一棵完整的二叉樹(shù)。

二叉樹(shù)的兩個(gè)子樹(shù)被稱(chēng)為左子樹(shù)(left subtree)和右子樹(shù)(right subtree)。在二叉樹(shù)中，如果節(jié)點(diǎn)沒(méi)有子樹(shù)，則左子樹(shù)和右子樹(shù)都為空，如果節(jié)點(diǎn)只有一個(gè)子樹(shù)，要根據(jù)子樹(shù)的左右來(lái)區(qū)分子樹(shù)是左子樹(shù)還是右子樹(shù)，如果節(jié)點(diǎn)有兩個(gè)子樹(shù)，則左子樹(shù)和右子樹(shù)都有。

如果，樹(shù)中存在一個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)的子樹(shù)超過(guò)兩個(gè)，則該樹(shù)不是二叉樹(shù)，如下圖中，節(jié)點(diǎn)C有三個(gè)子樹(shù)，所以這不是一棵二叉樹(shù)。

二、幾種特殊的二叉樹(shù)

只要樹(shù)中所有節(jié)點(diǎn)的子樹(shù)都不超過(guò)兩個(gè)(0個(gè)，1個(gè)，2個(gè))，這就是一棵普通的二叉樹(shù)。在二叉樹(shù)中，有一些比較特殊，除了滿(mǎn)足二叉樹(shù)的結(jié)構(gòu)外，還滿(mǎn)足一些特殊的規(guī)則，主要有如下幾種。

1. 完全二叉樹(shù)：假設(shè)一棵二叉樹(shù)的深度為d(d>1)，除了第d層外，其它各層的節(jié)點(diǎn)數(shù)目均已達(dá)最大值，且第d層所有節(jié)點(diǎn)從左向右連續(xù)地緊密排列，這樣的二叉樹(shù)被稱(chēng)為完全二叉樹(shù)。

完全二叉樹(shù)的葉節(jié)點(diǎn)只能出現(xiàn)在最下層和次下層，最下層的葉節(jié)點(diǎn)靠左緊密地排列，次下層如果存在葉節(jié)點(diǎn)，葉節(jié)點(diǎn)緊密地靠右排列。

如下圖，樹(shù)的深度為4，除了第4層，節(jié)點(diǎn)數(shù)達(dá)到了最大(“掛滿(mǎn)了”)，第4層的節(jié)點(diǎn)都是緊密地靠左排列(中間沒(méi)有空位)，所以這是一棵完全二叉樹(shù)。

如下圖，樹(shù)的深度也為4，除了第4層，節(jié)點(diǎn)數(shù)也達(dá)到了最大，但是第4層的節(jié)點(diǎn)不是緊靠左側(cè)排列的(節(jié)點(diǎn)E沒(méi)有子節(jié)點(diǎn)，空了兩個(gè)位置)，所以這不是一棵完全二叉樹(shù)，只是一棵普通的二叉樹(shù)。

2. 滿(mǎn)二叉樹(shù)：所有葉節(jié)點(diǎn)都在最底層的完全二叉樹(shù)稱(chēng)為滿(mǎn)二叉樹(shù)。滿(mǎn)二叉樹(shù)是完全二叉樹(shù)中的特殊情況，除了滿(mǎn)足完全二叉樹(shù)的特征，還滿(mǎn)足所有葉節(jié)點(diǎn)都在最底層。滿(mǎn)二叉樹(shù)是相同深度的二叉樹(shù)中葉節(jié)點(diǎn)最多的樹(shù)。

如下圖，這首先是一棵完全二叉樹(shù)，其次，所有的葉節(jié)點(diǎn)都在最底層，所以這是一棵滿(mǎn)二叉樹(shù)。其實(shí)，滿(mǎn)二叉樹(shù)也可以這么定義，二叉樹(shù)有節(jié)點(diǎn)的所有層，節(jié)點(diǎn)數(shù)目均已達(dá)最大值，則這是一棵滿(mǎn)二叉樹(shù)。

3. 平衡二叉樹(shù)(AVL樹(shù))：如果二叉樹(shù)的所有節(jié)點(diǎn)的兩棵子樹(shù)的高度差不大于1，則二叉樹(shù)被稱(chēng)為平衡二叉樹(shù)。

如上圖中的滿(mǎn)二叉樹(shù)，任何節(jié)點(diǎn)的兩棵子樹(shù)高度差都是0(高度都相等，高度差不大于1)，所以這是一棵平衡二叉樹(shù)。

如下圖中的二叉樹(shù)，對(duì)于根節(jié)點(diǎn)A，左子樹(shù)是以節(jié)點(diǎn)B為根的子樹(shù)，高度為4，右子樹(shù)是以節(jié)點(diǎn)C為根的子樹(shù)，高為2，A的左子樹(shù)與右子樹(shù)的高度差為2(高度差大于1)，所以這不是一棵平衡二叉樹(shù)。

AVL樹(shù)得名于它的發(fā)明者G. M. Adelson-Velsky和E. M. Landis，是兩人姓的縮寫(xiě)。AVL樹(shù)中任何節(jié)點(diǎn)的兩個(gè)子樹(shù)的高度差不大于1，通過(guò)高度來(lái)判斷是否平衡，所以也被稱(chēng)為高度平衡樹(shù)。

4. 排序二叉樹(shù)(二叉查找樹(shù)，Binary Search Tree)：又稱(chēng)為二叉搜索樹(shù)、有序二叉樹(shù)。

排序二叉樹(shù)需要具有如下的性質(zhì)：

4.1 如果二叉樹(shù)的左子樹(shù)不為空，則左子樹(shù)上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值。

4.2 如果二叉樹(shù)的右子樹(shù)不為空，則右子樹(shù)上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值。

4.3 如果獨(dú)立地看，左子樹(shù)、右子樹(shù)也分別為排序二叉樹(shù)，用遞歸的思想，直到樹(shù)的葉節(jié)點(diǎn)。

如下圖，根節(jié)點(diǎn)8的左子樹(shù)中，所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)，右子樹(shù)中，所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)，并且左子樹(shù)和右子樹(shù)都是排序二叉樹(shù)，所以這是一棵排序二叉樹(shù)。

5. 斜樹(shù)：除了葉節(jié)點(diǎn)，所有節(jié)點(diǎn)都只有左子樹(shù)的二叉樹(shù)稱(chēng)為左斜樹(shù)。除了葉節(jié)點(diǎn)，所有節(jié)點(diǎn)都只有右子樹(shù)的二叉樹(shù)稱(chēng)為右斜樹(shù)。他們統(tǒng)稱(chēng)為斜樹(shù)，判斷二叉樹(shù)是否為斜樹(shù)，主要是看樹(shù)的結(jié)構(gòu)，對(duì)節(jié)點(diǎn)的值沒(méi)有要求。

如下圖，左邊的樹(shù)中，除了葉節(jié)點(diǎn)D，所有節(jié)點(diǎn)都只有左子樹(shù)，這是一棵左斜樹(shù)，同理，右邊的樹(shù)是一棵右斜樹(shù)。

三、二叉樹(shù)的特點(diǎn)和性質(zhì)

通過(guò)對(duì)二叉樹(shù)的介紹和對(duì)幾種特殊二叉樹(shù)的了解，可知二叉樹(shù)有以下特點(diǎn)：

1. 每個(gè)節(jié)點(diǎn)最多有兩顆子樹(shù)，所以二叉樹(shù)中節(jié)點(diǎn)的度不大于2，二叉樹(shù)的度也不會(huì)大于2。

2. 左子樹(shù)和右子樹(shù)的次序不能顛倒。

3. 即使某節(jié)點(diǎn)只有一棵子樹(shù)，也要根據(jù)左右來(lái)區(qū)分它是左子樹(shù)還是右子樹(shù)。

此外，二叉樹(shù)還具有如下性質(zhì)：

1. 在二叉樹(shù)的第i層，至多有 2^(i-1) 個(gè)節(jié)點(diǎn)(i>0) 。

這里說(shuō)的是至多的情況，滿(mǎn)二叉樹(shù)的每一層節(jié)點(diǎn)都“掛滿(mǎn)”了，所以可以用下圖中的滿(mǎn)二叉樹(shù)來(lái)驗(yàn)證，第1層的節(jié)點(diǎn)數(shù)為2^(1-1)=1個(gè)，... 第4層的節(jié)點(diǎn)個(gè)數(shù)最多為 2^(4-1)=8個(gè)。

2. 深度為i的二叉樹(shù)至多有 2^i - 1 個(gè)節(jié)點(diǎn)(k>0) 。

這里也是說(shuō)至多的情況，所以也用滿(mǎn)二叉樹(shù)來(lái)驗(yàn)證，深度為4時(shí)，二叉樹(shù)的節(jié)點(diǎn)數(shù)最多為 2^4 - 1=16-1=15個(gè)。

3. 對(duì)于任意一棵二叉樹(shù)，如果其葉節(jié)點(diǎn)數(shù)為M，度為2的節(jié)點(diǎn)總數(shù)為N，則 M=N+1 。

為了不失一般性，下圖中的樹(shù)是一棵普通的二叉樹(shù)，葉節(jié)點(diǎn)為 F,H,I,J,K,L ，共6個(gè)，度為2的節(jié)點(diǎn)為 A,B,C,D,G ，共5個(gè)。

4. 具有n個(gè)節(jié)點(diǎn)的滿(mǎn)二叉樹(shù)的深度必為 log2(n+1) 。這個(gè)性質(zhì)是上面第2點(diǎn)的逆運(yùn)算。

5. 對(duì)于一棵完全二叉樹(shù)，若從上至下、從左至右編號(hào)，則編號(hào)為 i 的節(jié)點(diǎn)，(葉節(jié)點(diǎn)除外)其左子節(jié)點(diǎn)的編號(hào)必為2i，(葉節(jié)點(diǎn)除外)其右子節(jié)點(diǎn)的編號(hào)必為 2i+1，(根節(jié)點(diǎn)除外)其父節(jié)點(diǎn)的編號(hào)必為i/2(取整除)。

如下圖，這是一棵完全二叉樹(shù)，已經(jīng)按規(guī)則編好號(hào)了，可以任意取一個(gè)節(jié)點(diǎn)進(jìn)行驗(yàn)證，都是符合此性質(zhì)的。

到此這篇關(guān)于二叉樹(shù)的概念案例詳解的文章就介紹到這了,更多相關(guān)二叉樹(shù)的概念內(nèi)容請(qǐng)搜索本站以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持本站！

版權(quán)聲明：本站文章來(lái)源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請(qǐng)保持原文完整并注明來(lái)源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來(lái)源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來(lái)，僅供學(xué)習(xí)參考，不代表本站立場(chǎng)，如有內(nèi)容涉嫌侵權(quán)，請(qǐng)聯(lián)系alex-e#qq.com處理。