樹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 雙親指的是一個結(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)是每個結(jié)點(diǎn)最多只有兩棵子樹(即二 叉樹中不存在度＞2的結(jié)點(diǎn)) 二叉樹的子樹有左右之分，其次序不能 任意顛倒

二叉樹的性質(zhì)

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

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

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

完全二叉樹

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

• 深度為k，有n個結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個 結(jié)點(diǎn)都與深度為k的滿二叉樹中編號從1至n的結(jié)點(diǎn) 一一對應(yīng)時
  某一結(jié)點(diǎn) 有右子樹， 則其必有 左子樹
• 葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)
• 對任一結(jié)點(diǎn)，若其右分支的子孫最大層次為l，則其 左下分支的子孫的最大層次必為l或l+1

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

• 

二叉樹的存儲

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

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

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

遍歷二叉樹和線索二叉樹

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

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

二叉樹遍歷的時間效率和空間效率

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

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

6.4 樹和森林

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

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

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

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

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

哈夫曼樹

應(yīng)用

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

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