朋友們、伙計(jì)們，我們又見(jiàn)面了，本期來(lái)給大家解讀一下二叉樹(shù)方面的相關(guān)知識(shí)點(diǎn)，如果看完之后對(duì)你有一定的啟發(fā)，那么請(qǐng)留下你的三連，祝大家心想事成！
?
C 語(yǔ) 言 專(zhuān) 欄：C語(yǔ)言：從入門(mén)到精通
數(shù)據(jù)結(jié)構(gòu)專(zhuān)欄：數(shù)據(jù)結(jié)構(gòu)
個(gè)? 人? 主? 頁(yè)?：stackY、
?
目錄
??編輯
前言：
1.樹(shù)的概念及結(jié)構(gòu)
1.1樹(shù)的概念
1.2 樹(shù)的相關(guān)概念
1.3樹(shù)的表示
1.4樹(shù)在實(shí)際中的運(yùn)用
2.二叉樹(shù)概念及結(jié)構(gòu)?
2.1概念
2.2特殊的二叉樹(shù)
2.3二叉樹(shù)的性質(zhì)
2.4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)
3.二叉樹(shù)的順序結(jié)構(gòu)實(shí)現(xiàn)
3.1堆的應(yīng)用?
1. 堆排序
2. Top-K問(wèn)題
4.二叉樹(shù)的鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)
5.二叉樹(shù)基礎(chǔ)OJ練習(xí)
前言：
在之前的數(shù)據(jù)結(jié)構(gòu)中我們學(xué)習(xí)的是有關(guān)線(xiàn)性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)，那么在本期我們將會(huì)帶來(lái)樹(shù)形的數(shù)據(jù)結(jié)構(gòu)，樹(shù)形結(jié)構(gòu)通過(guò)名字來(lái)觀察顯而易見(jiàn)它的邏輯結(jié)構(gòu)示意圖是一種類(lèi)似現(xiàn)實(shí)生活中樹(shù)的形狀和特點(diǎn)，那么一棵樹(shù)就就會(huì)有樹(shù)根、樹(shù)枝、樹(shù)葉，那么二叉樹(shù)也不例外，在理解二叉樹(shù)之前呢我們先來(lái)了解一下有關(guān)樹(shù)的結(jié)構(gòu)以及概念，話(huà)不多說(shuō)，直接開(kāi)始：
1.樹(shù)的概念及結(jié)構(gòu)
1.1樹(shù)的概念
樹(shù)是一種非線(xiàn)性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做樹(shù)是因 為它看起來(lái)像一棵倒掛的樹(shù)，也就是說(shuō)它是根朝上，而葉朝下的。????????有一個(gè)特殊的結(jié)點(diǎn)，稱(chēng)為根結(jié)點(diǎn)，根節(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)。????????除根節(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成M(M>0)個(gè)互不相交的集合T1、T2、……、Tm，其中每? ? ? ? ? ? 一個(gè)集合Ti(1<= i <= m)又是一棵結(jié)構(gòu)與樹(shù)類(lèi)似的子樹(shù)。每棵子樹(shù)的根結(jié)點(diǎn)有且只有一? ? ? ? ? ? 個(gè)前驅(qū)，可以有0個(gè)或多個(gè)后繼。????????因此，樹(shù)是遞歸定義的。
注意：樹(shù)形結(jié)構(gòu)中，子樹(shù)之間不能有交集，否則就不是樹(shù)形結(jié)構(gòu)
1.2 樹(shù)的相關(guān)概念
節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹(shù)的個(gè)數(shù)稱(chēng)為該節(jié)點(diǎn)的度； 如上圖：A的為6、D的為1，B的為0，E的為2。葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為0的節(jié)點(diǎn)稱(chēng)為葉節(jié)點(diǎn)； 如上圖：B、C、H、I...等節(jié)點(diǎn)為葉節(jié)點(diǎn)。非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)； 如上圖：D、E、F、G...等節(jié)點(diǎn)為分支節(jié)點(diǎn)。雙親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱(chēng)為其子節(jié)點(diǎn)的父節(jié)點(diǎn)； 如上圖：A是B的父節(jié)點(diǎn)，E是I和J的父節(jié)點(diǎn)。孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹(shù)的根節(jié)點(diǎn)稱(chēng)為該節(jié)點(diǎn)的子節(jié)點(diǎn)； 如上圖：B是A的孩子節(jié)點(diǎn)，H是D的孩子結(jié)點(diǎn)。兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱(chēng)為兄弟節(jié)點(diǎn)； 如上圖：B、C是兄弟節(jié)點(diǎn)，K、L、M是兄弟結(jié)點(diǎn)。樹(shù)的度：一棵樹(shù)中，最大的節(jié)點(diǎn)的度稱(chēng)為樹(shù)的度； 如上圖：樹(shù)的度為6。節(jié)點(diǎn)的層次：從根開(kāi)始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類(lèi)推。樹(shù)的高度或深度：樹(shù)中節(jié)點(diǎn)的最大層次； 如上圖：樹(shù)的高度為4。堂兄弟節(jié)點(diǎn)：雙親在同一層的節(jié)點(diǎn)互為堂兄弟；如上圖：H、I互為堂兄弟節(jié)點(diǎn)，M、N互為堂兄弟結(jié)點(diǎn)。節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；如上圖：A是所有節(jié)點(diǎn)的祖先，F(xiàn)是K、L、M的祖先。子孫：以某節(jié)點(diǎn)為根的子樹(shù)中任一節(jié)點(diǎn)都稱(chēng)為該節(jié)點(diǎn)的子孫。如上圖：所有節(jié)點(diǎn)都是A的子孫。森林：由m（m>0）棵互不相交的樹(shù)的集合稱(chēng)為森林。
1.3樹(shù)的表示
樹(shù)結(jié)構(gòu)相對(duì)線(xiàn)性表就比較復(fù)雜了，要存儲(chǔ)表示起來(lái)就比較麻煩了，既然保存值域，也要保存結(jié)點(diǎn)和結(jié)點(diǎn)之間 的關(guān)系，實(shí)際中樹(shù)有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法 等。我們這里就簡(jiǎn)單的了解其中最常用的孩子兄弟表示法。//樹(shù)的表示方法 //左孩子右兄弟 typedef int DataType; struct Node { struct Node* _firstChild1; // 第一個(gè)孩子結(jié)點(diǎn) struct Node* _pNextBrother; // 指向其下一個(gè)兄弟結(jié)點(diǎn) DataType _data; // 結(jié)點(diǎn)中的數(shù)據(jù)域 };
1.4樹(shù)在實(shí)際中的運(yùn)用
2.二叉樹(shù)概念及結(jié)構(gòu)?
2.1概念
一棵二叉樹(shù)是結(jié)點(diǎn)的一個(gè)有限集合，該集合:1. 或者為空。2. 由一個(gè)根節(jié)點(diǎn)加上兩棵別稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。圖示：
從上圖可以看出：1. 二叉樹(shù)不存在度大于2的結(jié)點(diǎn)。2. 二叉樹(shù)的子樹(shù)有左右之分，次序不能顛倒，因此二叉樹(shù)是有序樹(shù)。注意：對(duì)于任意的二叉樹(shù)都是由以下幾種情況復(fù)合而成的：?
2.2特殊的二叉樹(shù)
1. 滿(mǎn)二叉樹(shù)：一個(gè)二叉樹(shù)，如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹(shù)就是滿(mǎn)二叉樹(shù)。也就是 說(shuō)，如果一個(gè)二叉樹(shù)的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是2^k - 1，則它就是滿(mǎn)二叉樹(shù)（每一層都是滿(mǎn)的）。2. 完全二叉樹(shù)：完全二叉樹(shù)是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹(shù)是由滿(mǎn)二叉樹(shù)而引出來(lái)的。對(duì)于深度為K 的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿(mǎn)二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì) 應(yīng)時(shí)稱(chēng)之為完全二叉樹(shù)。 要注意的是滿(mǎn)二叉樹(shù)是一種特殊的完全二叉樹(shù)（前K-1層必須是滿(mǎn)的，最后一層可以不滿(mǎn)，但是從左到右必須連續(xù) ）。
2.3二叉樹(shù)的性質(zhì)
1. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹(shù)的第i層上最多有2^(i-1)個(gè)結(jié)點(diǎn)。
2. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)是2^h-1。
?3.完全二叉樹(shù)的節(jié)點(diǎn)的范圍是[ 2^(h-1) , 2^h -1]
完全二叉樹(shù)的最少的節(jié)點(diǎn)個(gè)數(shù)可以看作是一個(gè)高度為h-1的滿(mǎn)二叉樹(shù)再加上一個(gè)節(jié)點(diǎn)
4. 對(duì)任何一棵二叉樹(shù), 如果度為0其葉結(jié)點(diǎn)個(gè)數(shù)為N，?度為2的分支結(jié)點(diǎn)個(gè)數(shù)為M，則有N = M+1。5. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個(gè)結(jié)點(diǎn)的滿(mǎn)二叉樹(shù)的深度h，h= log(n+1)。（log以2為底n+1的對(duì)數(shù)）。（ 滿(mǎn)二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)為n = 2^h-1，所以滿(mǎn)二叉樹(shù)的高度（深度）為h = log（n+1））
2.4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)
二叉樹(shù)一般可以使用兩種結(jié)構(gòu)存儲(chǔ)，一種順序結(jié)構(gòu)，一種鏈?zhǔn)浇Y(jié)構(gòu)。1. 順序存儲(chǔ)順序結(jié)構(gòu)存儲(chǔ)就是使用數(shù)組來(lái)存儲(chǔ)，一般使用數(shù)組只適合表示完全二叉樹(shù)，因?yàn)椴皇峭耆鏄?shù)會(huì)有空 間的浪費(fèi)。而現(xiàn)實(shí)中使用中只有堆才會(huì)使用數(shù)組來(lái)存儲(chǔ)，二叉樹(shù)順 序存儲(chǔ)在物理上是一個(gè)數(shù)組，在邏輯上是一顆二叉樹(shù)。
2. 鏈?zhǔn)酱鎯?chǔ)二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指，用鏈表來(lái)表示一棵二叉樹(shù)，即用鏈來(lái)指示元素的邏輯關(guān)系。 通常的方法是鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，數(shù)據(jù)域和左右指針域，左右指針?lè)謩e用來(lái)給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址 。鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈，難度也是逐次遞增，我們會(huì)先從最簡(jiǎn)單的來(lái)學(xué)習(xí)。
3.二叉樹(shù)的順序結(jié)構(gòu)實(shí)現(xiàn)
?關(guān)于二叉樹(shù)的順序結(jié)構(gòu)實(shí)現(xiàn)以及堆的概念都在這篇博客中：二叉樹(shù)的順序結(jié)構(gòu)--堆
3.1堆的應(yīng)用?
堆的應(yīng)用主要有兩個(gè)方面：
1. 堆排序
2. Top-K問(wèn)題
大家感興趣可以去我的這兩篇博客看一下，里面都有非常詳細(xì)的解答：
1.?排序算法：堆排序
2.?堆的應(yīng)用：Top-K問(wèn)題
4.二叉樹(shù)的鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)
二叉樹(shù)的鏈?zhǔn)浇Y(jié)構(gòu)是使用鏈表的方式來(lái)實(shí)現(xiàn)，每一個(gè)節(jié)點(diǎn)都有一個(gè)左子樹(shù)和一個(gè)右子樹(shù)，在鏈?zhǔn)蕉鏄?shù)中我們會(huì)學(xué)習(xí)到鏈?zhǔn)蕉鏄?shù)的創(chuàng)建方式、求節(jié)點(diǎn)個(gè)數(shù)、樹(shù)的高度......，具體的實(shí)現(xiàn)過(guò)程在這篇博客中：數(shù)據(jù)結(jié)構(gòu)：鏈?zhǔn)蕉鏄?shù)，感興趣的老鐵可以跳轉(zhuǎn)過(guò)去看一看。
5.二叉樹(shù)基礎(chǔ)OJ練習(xí)
單值二叉樹(shù)：https://leetcode.cn/problems/univalued-binary-tree/
檢查兩個(gè)樹(shù)是否相同：https://leetcode.cn/problems/same-tree/
對(duì)稱(chēng)二叉樹(shù)：https://leetcode.cn/problems/symmetric-tree/文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-471514.html
今天的博客就分享到這里，喜歡的老鐵留下你的三連，感謝感謝！我們下期再見(jiàn)??！?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-471514.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：二叉樹(shù)（初階）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
