樹

• 樹的定義：樹是以分支關(guān)系定義的層次結(jié)構(gòu)。

• D; 樹(Tree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集。

• R 數(shù)據(jù)關(guān)系

  ?有且僅有一個(gè)特定的稱為根(Root) 的結(jié)點(diǎn)

  ?當(dāng)n>1時(shí)，除根以外的其余結(jié)點(diǎn) 可分為m(m>0)個(gè)互不相交的有限 集T1, T2 ,… ,Tm ，其中每一個(gè)集 合本身又是一棵樹，并且稱為根 的子樹(SubTree)。

• ? 只有一個(gè)結(jié)點(diǎn)——只有一個(gè)根結(jié)點(diǎn)的樹；

• ? 有0個(gè)結(jié)點(diǎn)的樹——空樹

• 分支結(jié)點(diǎn)： 非終端結(jié)點(diǎn)

• 結(jié)點(diǎn)層次指的是結(jié)點(diǎn)在樹中所處的層次；

• 堂兄弟指的是具有相同父親的兄弟結(jié)點(diǎn)；

• 樹的深度指的是樹中所有結(jié)點(diǎn)中最大層數(shù)；

• 有序樹指的是樹中每個(gè)結(jié)點(diǎn)的子節(jié)點(diǎn)之間具有順序關(guān)系；無序樹則相反，子節(jié)點(diǎn)之間沒有順序關(guān)系；

• 森林則指由若干棵互不相交的樹組成。

• 孩子指的是一個(gè)結(jié)點(diǎn)的直接后代；

• 雙親指的是一個(gè)結(jié)點(diǎn)的直接前驅(qū)；

• 兄弟指的是具有相同雙親的結(jié)點(diǎn)；

• 祖先指的是從根到某一結(jié)點(diǎn)路徑上所有結(jié)點(diǎn)；

• 子孫則指某一結(jié)點(diǎn)為根的子樹中所有結(jié)點(diǎn)。

• 葉子結(jié)點(diǎn)指的是度為0的結(jié)點(diǎn)；

• 分支結(jié)點(diǎn)指的是度不為0的結(jié)點(diǎn)；

• 內(nèi)部結(jié)點(diǎn)指的是除根節(jié)點(diǎn)和葉子節(jié)點(diǎn)以外的所有節(jié)點(diǎn)；

• 樹的度指的是樹中所有結(jié)點(diǎn)中最大度數(shù)。

二叉樹

二叉樹(Binary Tree) 是另一種樹形結(jié)構(gòu) 特點(diǎn)是每個(gè)結(jié)點(diǎn)最多只有兩棵子樹(即二 叉樹中不存在度＞2的結(jié)點(diǎn)) 二叉樹的子樹有左右之分，其次序不能 任意顛倒

二叉樹的性質(zhì)

• 性質(zhì)1 在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i≥1)

• 性質(zhì)2 深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)(k≥1)

• 性質(zhì)3 對(duì)任一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的 結(jié)點(diǎn)數(shù)為n2，則n0=n2+1

完全二叉樹

• 滿二叉樹 一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹

• 深度為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í)
  某一結(jié)點(diǎn) 有右子樹， 則其必有 左子樹
• 葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)
• 對(duì)任一結(jié)點(diǎn)，若其右分支的子孫最大層次為l，則其 左下分支的子孫的最大層次必為l或l+1

• 性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2 n + 1

• 

二叉樹的存儲(chǔ)

• 順序存儲(chǔ)結(jié)構(gòu)

• 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

• 知識(shí)點(diǎn) 在含有n個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)空鏈域

遍歷二叉樹和線索二叉樹

• ? 對(duì)線性結(jié)構(gòu)而言，順序遍歷；
• ? 二叉樹是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如 何遍歷，即按什么樣的搜索路徑遍歷的問題。

• 看ppt 有代碼實(shí)現(xiàn)

二叉樹遍歷的時(shí)間效率和空間效率

基本操作：訪問結(jié)點(diǎn)Visit()

• 時(shí)間效率:O(n) //每個(gè)結(jié)點(diǎn)只訪問一次
• 空間效率:O(n) //棧占用的最大輔助空 間

6.4 樹和森林

• 樹的存儲(chǔ)結(jié)構(gòu)——雙親表示法

• 利用每個(gè)結(jié)點(diǎn)只有一個(gè) 雙親的性質(zhì)

• 采用多重鏈表，即每個(gè)結(jié)點(diǎn)設(shè)置多個(gè)指針域，每個(gè)指針域指 向一棵子樹的根結(jié)點(diǎn)

• 樹林遍歷順序 和 樹一樣 ( 順序即為第幾棵樹的Root結(jié)點(diǎn))

• 樹的存儲(chǔ)結(jié)構(gòu)——孩子兄弟表示法 / 二叉樹表示法 / 二叉鏈 表表示法

哈夫曼樹

應(yīng)用

1）二進(jìn)制編碼 : 通信中，可以采用0、1的不同排列來表示不同的字符， 稱為二進(jìn)制編碼。 發(fā)送端需要將電文中的字符序列轉(zhuǎn)換成二進(jìn)制的0、1 序列，即編碼； 接受端需要把接受的0、1序列轉(zhuǎn)換成對(duì)應(yīng)的字符序列， 即譯碼。 (左0 右 1)

2} 前綴編碼 : 若對(duì)某一字符集進(jìn)行不等長編碼，則要求字符集中任一字符的編碼都不能是其他字符編碼的前綴。符合此要求的編碼叫 做前綴編碼