一、樹的定義

樹是一個(gè)有n個(gè)（n>=0）結(jié)點(diǎn)的有限集合。

如果n=0，稱為空樹；

如果n>0，稱為非空樹，有且僅有一個(gè)特定的稱為根Root的結(jié)點(diǎn)（無直接前驅(qū)）

如果n>1,除了根節(jié)點(diǎn)外，其他結(jié)點(diǎn)劃分為m個(gè)互不相交的有限集合（記為T1、T2...TM），每個(gè)集合本身又是一棵樹，稱為根的子樹（Sub-tree）。

每個(gè)結(jié)點(diǎn)肯定有唯一的前驅(qū)（除根節(jié)點(diǎn)外），但是可能有多個(gè)后繼。

二、樹的術(shù)語

結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支

結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹個(gè)數(shù)，也即結(jié)點(diǎn)包含的分支個(gè)數(shù)

葉子結(jié)點(diǎn)（終端結(jié)點(diǎn)）

度為0的結(jié)點(diǎn) {K,L,F,G,M,I,J}

分支結(jié)點(diǎn)（）非終端結(jié)點(diǎn)

度不為0的結(jié)點(diǎn) {A,B,C,D,E,H}

包含根結(jié)點(diǎn)

內(nèi)部結(jié)點(diǎn)：除根之外的分支結(jié)點(diǎn) {B,C,D,E,H}

孩子：結(jié)點(diǎn)的子樹的根

雙親：孩子的直接前驅(qū)

兄弟：同一個(gè)雙親的其他孩子

子孫：以某結(jié)點(diǎn)為根的樹中所有的結(jié)點(diǎn)

祖先：從該結(jié)點(diǎn)到根結(jié)點(diǎn)，經(jīng)過所有分支結(jié)點(diǎn)

樹的層次

根結(jié)點(diǎn)為第一層，根的孩子為第二層，依次類推。

深度：樹中最大的層次

森林：互不相交的樹的集合。對(duì)于樹中每個(gè)結(jié)點(diǎn)而已，其子樹的集合就是森林

二叉樹? Binary Tree

每個(gè)結(jié)點(diǎn)最多只有兩棵子樹 最多兩個(gè)孩子

二叉樹的子樹可以分成左右兩個(gè)部分 稱為左子樹和右子樹? ??

?二叉樹的性質(zhì)1

在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)??

深度為k的二叉樹至多有2^k-1個(gè)結(jié)點(diǎn)

如果二叉樹終端結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2，則no=n2+1

證明思路：總結(jié)點(diǎn)數(shù)n=no+n1+n2

考察分支數(shù)B：除了根之外，所有的結(jié)點(diǎn)都有且只有一個(gè)分支指向它不同度的結(jié)點(diǎn)產(chǎn)生不同個(gè)數(shù)的分支 n=B+1

不同度的結(jié)點(diǎn)產(chǎn)生不同個(gè)數(shù)的分支B=n1+2n2

no=n2+1

五、滿二叉樹

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

每層上的結(jié)點(diǎn)數(shù)都是最大數(shù)? 可以自上而下、自左至右連續(xù)編號(hào)

完全二叉樹? 當(dāng)且僅當(dāng)每一個(gè)結(jié)點(diǎn)都與深度相同的滿二叉樹中編號(hào)從1到n的結(jié)點(diǎn)一一一對(duì)應(yīng)的二叉樹

葉子結(jié)點(diǎn)只在最大兩層上出現(xiàn)

以任何一個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)，其左子樹深度與右子樹深度相等或大于1

具有n個(gè)結(jié)點(diǎn)的完全二叉樹 其深度為log2n取整+1

七、二叉樹的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)

用一組連續(xù)的存儲(chǔ)單元依次自上而下，自左至右存儲(chǔ)結(jié)點(diǎn)

對(duì)于一般二叉樹，空結(jié)點(diǎn)的位置也要按照完全二叉樹編號(hào)

八、二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

1、二叉鏈表

采用數(shù)據(jù)域加上左右孩子的指針

2、二叉鏈表的定義

二叉鏈表的一個(gè)結(jié)點(diǎn)的可以用一個(gè)結(jié)構(gòu)體表示，里面包含的成員有一個(gè)數(shù)據(jù)域，兩個(gè)指針域

struct BiNode? ? binode：?雙節(jié)點(diǎn)? ? ? ? ? ?node:節(jié)點(diǎn)

{

char data;

BiNode? *Ichild,*rchild;

}

3、二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

只能雙親找孩子，孩子難以找到雙親

4、二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

三叉鏈表

?遍歷二茶樹

根據(jù)訪問根結(jié)點(diǎn)的次序

DLR

LDR

LRD

先序：

boid PreOrderTraverse(BinTree T)

{

if(T)

{

cout<<T->data;

PreOrderTraverse(T->IChild);

PreOrderTraverse()T->rChild):

先序中序、中序后序

都可以求出二叉樹

而先序和后序不可以

因?yàn)椴痪邆浯_定左右子樹的能力。

樹的存儲(chǔ)結(jié)構(gòu)

雙親表示法? ?找雙親容易找孩子難? ?

孩子表示法：最大的缺點(diǎn)就是空指針鏈域太多? ? 有些結(jié)點(diǎn)有很多孩子 有些結(jié)點(diǎn)的孩子很少：結(jié)構(gòu)不均衡? ? ? ? ??

n結(jié)點(diǎn)的樹? ?度為d? ? ? 多鏈表表示法中 空指針必有[（d-1）n+1]

?

?

?

樹的路徑：

路徑：從樹的一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成了兩個(gè)結(jié)點(diǎn)之間的路徑

路徑長(zhǎng)度：路徑上的分支的數(shù)目

樹的路徑長(zhǎng)度：從根結(jié)點(diǎn)到每個(gè)結(jié)點(diǎn)之間路徑長(zhǎng)度的和

如果結(jié)點(diǎn)權(quán)重不一樣，我們可以計(jì)算帶權(quán)路徑長(zhǎng)度

從結(jié)點(diǎn)到根結(jié)點(diǎn)之間的路徑長(zhǎng)度乘以該結(jié)點(diǎn)的權(quán)重

樹的帶權(quán)路徑長(zhǎng)度WPL? ? Weighted? path length

樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和（）度為0

相同的葉子結(jié)點(diǎn)數(shù)，葉子結(jié)點(diǎn)也具有相同的權(quán)重，但是不同的二叉樹會(huì)產(chǎn)生不同的WOL

引出概念

樹的帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹被稱為最優(yōu)二叉樹

Huffman? 哈夫曼樹

有什么special的place

權(quán)值最大的結(jié)點(diǎn)離根最近

權(quán)值最小的結(jié)點(diǎn)離根最遠(yuǎn)

?

?

有了編碼

怎么解碼

要能唯一解碼對(duì)編碼有什么要求

要求前綴編碼

即任何一個(gè)字符編碼都不是其他字符的前綴

Huffman是一種前綴編碼

?