- 樹(shù)的理解性定義
- 樹(shù)的用處
- 樹(shù)的實(shí)現(xiàn)和二叉樹(shù)
- 樹(shù)的遍歷
1概作、樹(shù)的理解性定義
樹(shù)是分組、層次結(jié)構(gòu)：
-
分組
樹(shù)由樹(shù)根和其余節(jié)點(diǎn)組成，而其余節(jié)點(diǎn)分為m（m>0)個(gè)互不相交的有限集，所以把這些有限集合稱為原樹(shù)的子樹(shù)善延。
可以把每個(gè)子樹(shù)理解為一組，而子樹(shù)內(nèi)部又遞歸的分組下去
與分組有關(guān)的術(shù)語(yǔ)：
森林（Forest） 城侧，Tree＝（root易遣，F(xiàn)） ，其中F為森林
-
層次
樹(shù)狀圖本身是有層次的嫌佑，這樣利于高效查找
與層次相關(guān)的術(shù)語(yǔ)：
結(jié)點(diǎn)的層次（Level）豆茫、樹(shù)的深度（Depth）
遍歷：層次遍歷
2、樹(shù)的用處
基本上有序列（廣義）的地方就可以應(yīng)用樹(shù)歧强，因?yàn)?strong>樹(shù)結(jié)構(gòu)即是一種序列索引結(jié)構(gòu)
序列的核心接口就是三個(gè)cha：插澜薄、查为肮、X（增查刪）
對(duì)于這個(gè)三個(gè)接口摊册，我們要解決的核心問(wèn)題是：
①效率：怎么查得快
②穩(wěn)定：如果不支持增刪，那么序列就是靜態(tài)結(jié)構(gòu)颊艳，用處不大茅特。而支持增刪之后忘分，需要考慮如何保證序列內(nèi)部結(jié)構(gòu)不會(huì)被增刪操作破壞，導(dǎo)致查詢效率受到影響白修。
樹(shù)通過(guò)其結(jié)構(gòu)來(lái)表達(dá)了一種劃分查找方法妒峦，這一方法相比于遍歷搜索的復(fù)雜度O(n)，一般情況下復(fù)雜度僅有O(logn)兵睛。
樹(shù)則可以動(dòng)態(tài)改變存儲(chǔ)空間肯骇，且運(yùn)用一些手段來(lái)保護(hù)自身索引結(jié)構(gòu)。
3祖很、樹(shù)的實(shí)現(xiàn)和二叉樹(shù)
樹(shù)轉(zhuǎn)換為二叉樹(shù)
由于二叉樹(shù)是有序的笛丙，為了避免混淆，對(duì)于無(wú)序樹(shù)假颇，我們約定樹(shù)中的每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)按從左到右的順序進(jìn)行編號(hào)胚鸯。
將樹(shù)轉(zhuǎn)換成二叉樹(shù)的步驟是：
（1）加線。就是在所有兄弟結(jié)點(diǎn)之間加一條連線笨鸡；
（2）抹線姜钳。就是對(duì)樹(shù)中的每個(gè)結(jié)點(diǎn)，只保留他與第一個(gè)孩子結(jié)點(diǎn)之間的連線形耗，刪除它與其它孩子結(jié)點(diǎn)之間的連線哥桥；
（3）旋轉(zhuǎn)。就是以樹(shù)的根結(jié)點(diǎn)為軸心激涤，將整棵樹(shù)順時(shí)針旋轉(zhuǎn)一定角度泰讽，使之結(jié)構(gòu)層次分明。
樹(shù)的表示
由于樹(shù)中的每個(gè)結(jié)點(diǎn)的度不統(tǒng)一昔期，所以顯然已卸，首先我們想到的是結(jié)構(gòu)體加鏈表的形式對(duì)其進(jìn)行表示，如下圖所示：
note: 但這種是不正確的實(shí)現(xiàn)方式
我們知道硼一，當(dāng)一棵樹(shù)具有n個(gè)節(jié)點(diǎn)時(shí)累澡，它具有n-1條邊，而上述的表示方式則需要3n（因?yàn)闃?shù)的度為3）個(gè)存儲(chǔ)單元來(lái)存放樹(shù)的邊般贼。這樣一樣愧哟，2n＋1個(gè)存儲(chǔ)單元就被浪費(fèi)了。因此為了減少上述浪費(fèi)哼蛆，實(shí)際編碼時(shí)我們一般采用兒子-兄弟的表示方法：
-
樹(shù)的結(jié)構(gòu)體中包含：一個(gè)存放結(jié)點(diǎn)元素的單元蕊梧，一個(gè)指向第一個(gè)兒子的指針和一個(gè)指向第一個(gè)兄弟的指針。
-
這樣一來(lái)腮介，我們表示一顆樹(shù)肥矢，則只需要2n個(gè)存儲(chǔ)單元來(lái)存儲(chǔ)樹(shù)的邊，僅僅浪費(fèi)n+1個(gè)存儲(chǔ)單元叠洗。
當(dāng)我們把上述樹(shù)進(jìn)行旋轉(zhuǎn)45度時(shí)甘改，發(fā)現(xiàn)這就是一顆二叉樹(shù)了旅东，因此大部分的樹(shù)都可以轉(zhuǎn)化為二叉樹(shù)的形式進(jìn)行表示。綜上所述十艾，樹(shù)的算法大多圍繞二叉樹(shù)進(jìn)行抵代。
未完待續(xù)
