八、樹(shù)和二叉樹(shù)

一、樹(shù)的定義

樹(shù)的定義
樹(shù)是一種非線(xiàn)性的數(shù)據(jù)結(jié)構(gòu)
樹(shù)是由 n (n≥0) 個(gè)結(jié)點(diǎn)組成的有限集合
?如果 n = 0，稱(chēng)為空樹(shù) ；
?如果 n > 0，則 ：
??有一個(gè)特定的稱(chēng)之為根 (root) 的結(jié)點(diǎn)，它只有直接后繼，但沒(méi)有直接前驅(qū)
??除根以外的其它結(jié)點(diǎn)劃分為 m (m≥0) 個(gè)互不相交的有限集合T0, T1, …,Tm-1， 每個(gè)集合又是一棵樹(shù)， 并且稱(chēng)之為根的子樹(shù)(subTree)

樹(shù)家族中的概念
樹(shù)的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)及若干指向子樹(shù)的分支
結(jié)點(diǎn)擁有的子樹(shù)數(shù)稱(chēng)為結(jié)點(diǎn)的度
?度為0的結(jié)點(diǎn)稱(chēng)為葉結(jié)點(diǎn)
?度不為0的結(jié)點(diǎn)稱(chēng)為分支結(jié)點(diǎn)
樹(shù)的度定義為所有結(jié)點(diǎn)中的度的最大值

結(jié)點(diǎn)的直接后繼稱(chēng)為該結(jié)點(diǎn)的孩子
?相應(yīng)的，該結(jié)點(diǎn)稱(chēng)為孩子的雙親
結(jié)點(diǎn)的孩子的孩子的…… 稱(chēng)為該結(jié)點(diǎn)的子孫
?相應(yīng)的，該結(jié)點(diǎn)稱(chēng)為子孫的祖先
同一個(gè)雙親的孩子之間互稱(chēng)兄弟

結(jié)點(diǎn)的層次
?根為第1層
?根的孩子為第2層
?……
樹(shù)中結(jié)點(diǎn)的最大層次稱(chēng)為樹(shù)的深度或高度

如果樹(shù)中結(jié)點(diǎn)的各子樹(shù)從左向右是有次序的，子樹(shù)間不能互換位置 ，則稱(chēng)該樹(shù)為有序樹(shù) ，否則為無(wú)序樹(shù)。

森林是由 n ( n≥0) 棵互不相交的樹(shù)組成的集合

樹(shù)的一些常用操作

創(chuàng)新互聯(lián)公司專(zhuān)注于資溪網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠(chéng)為您提供資溪營(yíng)銷(xiāo)型網(wǎng)站建設(shè)，資溪網(wǎng)站制作、資溪網(wǎng)頁(yè)設(shè)計(jì)、資溪網(wǎng)站官網(wǎng)定制、微信平臺(tái)小程序開(kāi)發(fā)服務(wù)，打造資溪網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供資溪網(wǎng)站排名全網(wǎng)營(yíng)銷(xiāo)落地服務(wù)。

創(chuàng)建樹(shù)
銷(xiāo)毀樹(shù)
清空樹(shù)
插入結(jié)點(diǎn)
刪除結(jié)點(diǎn)
獲取結(jié)點(diǎn)
獲取根結(jié)點(diǎn)
獲取樹(shù)的結(jié)點(diǎn)數(shù)
獲取樹(shù)的高度
獲取樹(shù)的度

二、樹(shù)的存儲(chǔ)結(jié)構(gòu)

樹(shù)的存儲(chǔ)結(jié)構(gòu)
無(wú)法直接用數(shù)組表示樹(shù)的邏輯結(jié)構(gòu)
但可以設(shè)計(jì)結(jié)構(gòu)體數(shù)組對(duì)結(jié)點(diǎn)間的關(guān)系進(jìn)行表述

利用鏈表組織樹(shù)中的各個(gè)結(jié)點(diǎn)
鏈表中的前后關(guān)系不代表結(jié)點(diǎn)間的邏輯關(guān)系
結(jié)點(diǎn)的邏輯關(guān)系由 child 數(shù)據(jù)域描述
child 數(shù)據(jù)域保存其他結(jié)點(diǎn)的存儲(chǔ)地址

三、二叉樹(shù)的定義

另一種樹(shù)結(jié)構(gòu)模型
孩子兄弟表示法模型
每個(gè)結(jié)點(diǎn)都有一個(gè)指向其第一個(gè)孩子的指針
每個(gè)結(jié)點(diǎn)都有一個(gè)指向其第一個(gè)右兄弟的指針

每個(gè)結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)指針和兩個(gè)結(jié)點(diǎn)指針
數(shù)據(jù)指針 ： 指向保存于樹(shù)中的數(shù)據(jù)
孩子結(jié)點(diǎn)指針 ： 指向第一個(gè)孩子
兄弟結(jié)點(diǎn)指針 ： 指向第一個(gè)右兄弟

孩子兄弟表示法的特點(diǎn)
能夠表示任意的樹(shù)形結(jié)構(gòu)
每個(gè)結(jié)點(diǎn)中有且僅有三個(gè)指針域
?數(shù)據(jù)指針，孩子結(jié)點(diǎn)指針，兄弟結(jié)點(diǎn)指針
每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)簡(jiǎn)單
?只有孩子結(jié)點(diǎn)指針和兄弟結(jié)點(diǎn)指針構(gòu)成了“樹(shù)杈"
二叉樹(shù)的定義
二叉樹(shù)是由n ( n ≥0) 個(gè)結(jié)點(diǎn)組成的有限集合， 該集合或者為空， 或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱(chēng)為左子樹(shù)和 右子樹(shù)的 、 互不相交的二叉樹(shù)組成。

特殊的二叉樹(shù)

滿(mǎn)二叉樹(shù)(Full Binary Tree)
如果 二叉樹(shù)中所有分支結(jié)點(diǎn)的度數(shù)都為2， 且葉子結(jié)點(diǎn)都在同一層次上 ， 則稱(chēng)這類(lèi)二叉樹(shù)為滿(mǎn)二叉樹(shù) 。

完全二叉樹(shù) (Complete Binary Tree)
如果一棵具有n個(gè)結(jié)點(diǎn)的高度為k的二叉樹(shù)， 它的每一個(gè)結(jié)點(diǎn)都與高度為k 的滿(mǎn)二叉樹(shù)中編號(hào)為1—n 的結(jié)點(diǎn)一一對(duì)應(yīng)， 則稱(chēng)這棵二叉樹(shù)為完全二叉樹(shù)。（從上到下從左到右編號(hào))
完全二叉樹(shù)的葉結(jié)點(diǎn)僅出現(xiàn)在最下面兩層
?最下層的葉結(jié)點(diǎn)一定出現(xiàn)在左邊
?倒數(shù)第二層的葉結(jié)點(diǎn)一定出現(xiàn)在右邊
完全二叉樹(shù)中度為1的結(jié)點(diǎn)只有左孩子
同樣結(jié)點(diǎn)數(shù)的二叉樹(shù) ， 完全二叉樹(shù)的高度最小

通用樹(shù)實(shí)現(xiàn)源碼

本文題目：八、樹(shù)和二叉樹(shù)
網(wǎng)頁(yè)地址：http://muchs.cn/article46/gppehg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供搜索引擎優(yōu)化、ChatGPT、品牌網(wǎng)站建設(shè)、品牌網(wǎng)站設(shè)計(jì)、企業(yè)網(wǎng)站制作、面包屑導(dǎo)航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀(guān)點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)