一、樹的定義

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

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

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

結(jié)點的層次
根為第1層
根的孩子為第2層
?……
樹中結(jié)點的大層次稱為樹的深度或高度

如果樹中結(jié)點的各子樹從左向右是有次序的，子樹間不能互換位置 ，則稱該樹為有序樹 ，否則為無序樹。

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

樹的一些常用操作

彭水苗族土家族ssl適用于網(wǎng)站、小程序/APP、API接口等需要進行數(shù)據(jù)傳輸應(yīng)用場景，ssl證書未來市場廣闊！成為創(chuàng)新互聯(lián)公司的ssl證書銷售渠道，可以享受市場價格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：13518219792（備注：SSL證書合作）期待與您的合作！

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

二、樹的存儲結(jié)構(gòu)

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

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

三、二叉樹的定義

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

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

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

特殊的二叉樹

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

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

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

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

標題名稱：八、樹和二叉樹-創(chuàng)新互聯(lián)
轉(zhuǎn)載注明：http://weahome.cn/article/ddodss.html