主頁(yè)：114514的代碼大冒險(xiǎn)

qq:2188956112（歡迎小伙伴呀hi?(。???。)??）

Gitee：莊嘉豪 (zhuang-jiahaoxxx) - Gitee.com

引入

我們之前已經(jīng)學(xué)過線性數(shù)據(jù)結(jié)構(gòu)，今天我們將介紹非線性數(shù)據(jù)結(jié)構(gòu)----樹

望文生義，這個(gè)數(shù)據(jù)結(jié)構(gòu)肯定與現(xiàn)實(shí)中的樹，?有著一定的聯(lián)系，如圖：

?數(shù)據(jù)結(jié)構(gòu)中的樹它看起來(lái)像樹枝，也想樹的根部

樹的概念

樹的相關(guān)概念

?

節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度；如上圖：A的為6

葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為0的節(jié)點(diǎn)稱為葉節(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)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)；如上圖：A是B的父節(jié)點(diǎn)

孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)；如上圖：B是A的孩子節(jié)點(diǎn)

兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)；如上圖：B、C是兄弟節(jié)點(diǎn)

樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度；如上圖：樹的度為6

節(jié)點(diǎn)的層次：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推；

樹的高度或深度：樹中節(jié)點(diǎn)的最大層次；如上圖：樹的高度為4

堂兄弟節(jié)點(diǎn)：雙親在同一層的節(jié)點(diǎn)互為堂兄弟；如上圖：H、I互為兄弟節(jié)點(diǎn)

節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；如上圖：A是所有節(jié)點(diǎn)的祖先

子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。如上圖：所有節(jié)點(diǎn)都是A的子孫

森林：由m（m>0）棵互不相交的樹的集合稱為森林；

樹的表示

概念圖：

?

?樹在實(shí)際中的運(yùn)用（表示文件系統(tǒng)的目錄樹結(jié)構(gòu)）

文件目錄：

?公司內(nèi)部功能安排

?

二叉樹（特殊的樹）

?

?

這些都不重要

你只需要知道二叉樹的每個(gè)節(jié)點(diǎn)最多兩個(gè)孩子

可以沒有孩子，也可以只有一個(gè)孩子

另外在二叉樹中

左孩子和右孩子是有差異的

現(xiàn)實(shí)中的二叉樹

?

1. 滿二叉樹：一個(gè)二叉樹，如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹就是滿二叉樹。也就是說(shuō)，如果一個(gè)二叉樹的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是2^k-1,則它就是滿二叉樹。

2. 完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來(lái)的。對(duì)于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱之為完全二叉樹。要注意的是滿二叉樹是一種特殊的完全二叉樹。

說(shuō)人話：

就是說(shuō)如果除了最底下那一排（所謂的葉子節(jié)點(diǎn)）其他的節(jié)點(diǎn)都有兩個(gè)孩子

我們就稱之為滿二叉樹

?那么什么是完全二叉樹呢

就是除了樹的倒數(shù)第二排之外，其他節(jié)點(diǎn)都有兩個(gè)孩子

如圖:

?

二叉樹的性質(zhì)

說(shuō)了一大堆，能看懂多少算多少

我來(lái)說(shuō)幾個(gè)比較可能用到的點(diǎn)

只要是樹，有兩個(gè)孩子的節(jié)點(diǎn)始終比沒有孩子的節(jié)點(diǎn)的數(shù)量少一

?完全二叉樹的坐標(biāo)規(guī)律如右圖所示

（完全二叉樹中） 我們假使某節(jié)點(diǎn)這個(gè)下標(biāo)為i，那么它的父親就是

（i-1）/2 ，左孩子（如果有的話）為2*i+1，右孩子為左孩子坐標(biāo)加1

另外還有就是這個(gè)完全二叉樹的層數(shù)問題

除開最后一層外，第一層節(jié)點(diǎn)的數(shù)量為2^0,第二次為2^1第三次為2^2

第n層為2^(n-1),

如此滿二叉樹的節(jié)點(diǎn)數(shù)量為2^n - 1個(gè)

hhh,非滿二叉樹的節(jié)點(diǎn)數(shù)量則為前n-1層的節(jié)點(diǎn)數(shù)量+最后一層的節(jié)點(diǎn)數(shù)

我想，這個(gè)時(shí)候，在知道二叉樹的節(jié)點(diǎn)的數(shù)量前提下

求出二叉樹的深度，也就是層數(shù)不是什么困難的事情了

---

總結(jié)

這就是今天的樹的概念講解

這部分內(nèi)容不需要太過焦慮

這些概念現(xiàn)在只是稍微有個(gè)大概就可以

我們?cè)诮酉聛?lái)的學(xué)習(xí)中會(huì)反復(fù)提到