數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)樹和二叉樹

數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)樹和二叉樹一、二叉樹或空，或由根和由互不相交的左子樹、右子樹構(gòu)成。1、二叉鏈第六章樹和二叉樹abcdfgeabcedfg性質(zhì)1：在二叉樹的第i(i>0)層上至多有2i-1個(gè)結(jié)點(diǎn)。性質(zhì)2：深度為k的二叉樹中至多有2k-1個(gè)結(jié)點(diǎn)(k>0)。性質(zhì)3：對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。性質(zhì)4：有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為+1。2、二叉樹的性質(zhì)性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹按層序從1開始編號(hào)，則對(duì)任一結(jié)點(diǎn)(i<=i<=n),有：(1)如果i=1，則結(jié)點(diǎn)i是二叉樹的根結(jié)點(diǎn)；如果

i>1,

則其雙親結(jié)點(diǎn)是[i/2]。(2)如果2i<=n,則結(jié)點(diǎn)i的左孩

子是結(jié)點(diǎn)2i；否則結(jié)點(diǎn)i無(wú)

左孩子。(3)如果2i+1<=n,則結(jié)點(diǎn)i的右

孩子是結(jié)點(diǎn)2i+1；否則結(jié)

點(diǎn)i無(wú)右孩子。例６.１32個(gè)結(jié)點(diǎn)的完全二叉樹，從根開始，按層次從左到右用1-32編號(hào)。請(qǐng)回答：（1）它共有多少層？（2）各層最左邊的結(jié)點(diǎn)的編號(hào)是多少？（3）編號(hào)為6的結(jié)點(diǎn)的左孩子的編號(hào)是多少？它的右孩子呢？（4）編號(hào)為16的結(jié)點(diǎn)的左孩子的編號(hào)是多少？它的右孩子呢？（5）對(duì)于編號(hào)為8的結(jié)點(diǎn)，它的父結(jié)點(diǎn)的編號(hào)是多少？編號(hào)為13的結(jié)點(diǎn)呢？編號(hào)為1的結(jié)點(diǎn)呢？

二叉樹的遍歷：按某條搜索路徑訪問(wèn)二叉樹中每一個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次。

遍歷方法有4種：先序遍歷，中序遍歷，后序遍歷，層次遍歷。3、二叉樹的遍歷先序遍歷二叉樹：（1）訪問(wèn)根結(jié)點(diǎn)

（2）先序遍歷左子樹（3）先序遍歷右子樹先序遍歷序列：

abcdfge1234567abcdfge中序遍歷二叉樹：（1）中序遍歷左子樹

（2）訪問(wèn)根結(jié)點(diǎn)（3）中序遍歷右子樹中序遍歷序列：

bafgdceabcdfge1234567后序遍歷二叉樹：（1）后序遍歷左子樹

（2）后序遍歷右子樹（3）訪問(wèn)根結(jié)點(diǎn)后序遍歷序列：

bgfdecaabcdfge1234567abcdfge1234567層次遍歷二叉樹：按層次（1-k層)，每層從左到右依次訪問(wèn)二叉樹中的每一個(gè)結(jié)點(diǎn)。

層次遍歷序列：

abcdefg

例6.1已知二叉樹先序遍歷序列是:abcdefg;

中序遍歷序列是:cbdaefg;

（1）畫出該二叉樹;

（2）寫出后序遍歷序列.(cdbgfea)

（1）（2）寫出后序遍歷序列：cdbgfeaabcdefg1234567二、樹1、樹的定義

樹（Tree)是n(n>=0)個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹中：(1)有且僅有一個(gè)根結(jié)點(diǎn)；(2)除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)可分為

m(m>=0)個(gè)互不相交的子樹。3、樹與二叉樹的轉(zhuǎn)換

樹轉(zhuǎn)換成二叉樹：

(左孩子-右兄弟)OacgbdefOacgbdef2、樹的存儲(chǔ)結(jié)構(gòu)——二叉鏈Oacgbdef(左孩子-右兄弟)4、樹的遍歷Oacgbdef

先序遍歷樹：

（1）訪問(wèn)根結(jié)點(diǎn)

（2）先序遍歷每一個(gè)子樹

先序遍歷序列：

oabcdfeg

Oacgbdef

后序遍歷樹：

（1）后序遍歷每一個(gè)子樹（2）訪問(wèn)根結(jié)點(diǎn)

后序遍歷序列：

bafdecg03、哈夫曼碼：是一種前綴編碼（即任一字符的編碼都不是另一編碼的前綴）。左支用0表示，右支用1表示。1、二叉樹的帶權(quán)路徑長(zhǎng)度

WPL=wklkk=1其中，n:葉子結(jié)點(diǎn)個(gè)數(shù)，wk:第k個(gè)葉子的權(quán)，

lk:第k個(gè)葉子到根的路徑長(zhǎng)度。

2、Huffman樹的構(gòu)造方法

（1）將{w1,w2,…….,wn}看成n個(gè)二叉樹；

（2）選擇2個(gè)根結(jié)點(diǎn)的值最小的二叉樹，構(gòu)造1個(gè)新的二叉樹；…….；直至剩1個(gè)樹止。

n

三、Huffman樹(1)構(gòu)造huffman樹——以小值為左孩子

(2)在哈夫曼樹的所有左分支上編上號(hào)碼“0”,右分支上編上號(hào)碼“1”；(3)將根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)的路徑編碼串起來(lái),得到字符集的哈夫曼編碼。(4)ＷＰＬ=(25+36+50)*2+(8+10+14)*4+(2+5)*5=385例6.8設(shè)通信用8個(gè)字符abcdefgh