數(shù)據(jù)結(jié)構(gòu)-第四章-層次結(jié)構(gòu)-樹

第四章層次結(jié)構(gòu)——樹1.樹的描述有唯一的結(jié)點(diǎn)沒有前綴其余結(jié)點(diǎn)都有且只有一個(gè)前綴從根結(jié)點(diǎn)可以按后繼關(guān)系到達(dá)其余各結(jié)點(diǎn)

4.1、樹的概念4.1樹的概念4.2二叉樹4.3樹的應(yīng)用主要內(nèi)容2.樹的表示表(a(b(e(k,l),f),(c(g)),(d(h,i,j)))凸凹圖集合圖樹形圖4.1樹的概念樹的凹凸圖表示abekIfcgdhij樹的集合表示ghijaklbefcd樹的樹形表示3.樹的術(shù)語根、葉、分支結(jié)點(diǎn)父子、兄弟、祖孫關(guān)系高度度子樹、森林有序樹

4.1樹的概念結(jié)點(diǎn)的名稱根：樹中沒有前綴的結(jié)點(diǎn)成為根葉子：樹中沒有后繼的結(jié)點(diǎn)成為葉子分支節(jié)點(diǎn)：除根和葉子之外的結(jié)點(diǎn)結(jié)點(diǎn)的關(guān)系雙親和孩子：若結(jié)點(diǎn)a是結(jié)點(diǎn)b的前綴，則稱a是b的雙親，b是a的孩子兄弟：若結(jié)點(diǎn)a也是c的雙親，則c是b的兄弟，b也是c的兄弟祖先和子孫：若b又是e的前綴，則稱a是e的祖先，e是a的子孫結(jié)點(diǎn)的層次：即結(jié)點(diǎn)所在的層數(shù)，對(duì)于一棵樹，從根算起，根是第一層，根的孩子為第二層，依此類推高度：結(jié)點(diǎn)的層次，也叫做結(jié)點(diǎn)的高度。樹中結(jié)點(diǎn)高度最大者，為樹的高度。度：結(jié)點(diǎn)的度，指的是該節(jié)點(diǎn)孩子的個(gè)數(shù)，樹中所有結(jié)點(diǎn)中度最大者，為該樹的度。提問：葉子節(jié)點(diǎn)的度是多少？子樹：由樹的一部分結(jié)點(diǎn)組成，并保持原樹中的父子關(guān)系，其結(jié)構(gòu)也是一棵樹，成為原樹的子樹。森林：m棵互不相交的樹的集合有序樹：若樹中各結(jié)點(diǎn)的子樹從左到右是有次序地，不能交換則成該樹為有序樹4.樹的存儲(chǔ)結(jié)點(diǎn)結(jié)構(gòu)根指針:鏈頭指針空間利用率：4.1樹的概念返回樹中結(jié)點(diǎn)有多個(gè)后繼，所以不能使用順序結(jié)構(gòu)，采用鏈接結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)中有多個(gè)指針域，指向孩子、雙親、兄弟等datachild1child2……childn存儲(chǔ)空鏈域太多，空間利用率低ab∧c∧∧de∧f∧∧∧g∧∧∧h∧∧∧i∧∧∧j∧∧∧k∧∧∧l∧∧∧t4.2二叉樹二叉樹的概念性質(zhì)二叉樹的存儲(chǔ)二叉樹的運(yùn)算1、二叉樹的概念二叉樹是一種特殊的樹。其結(jié)點(diǎn)個(gè)數(shù)可以為0，這是稱其為空二叉樹。如果二叉樹不為空，則具有以下特征：每個(gè)結(jié)點(diǎn)最多只有兩棵子樹兩棵子樹有左右之分，其次序不能任意顛倒（即是有序樹）二叉樹的五種基本形態(tài)圖5.1二叉樹的五種基本形態(tài)

二叉樹中關(guān)系的一些定義左子結(jié)點(diǎn):左子樹的根結(jié)點(diǎn)，稱為左孩子右子結(jié)點(diǎn)：右子樹的根節(jié)點(diǎn)，稱為右孩子兄弟結(jié)點(diǎn)：具有同一個(gè)父結(jié)點(diǎn)的，相互之間稱為兄弟結(jié)點(diǎn)葉結(jié)點(diǎn)：沒有孩子結(jié)點(diǎn)的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)一般的樹用二叉樹表示左手抱孩子，右手抱兄弟滿二叉樹和完全二叉樹如果一棵二叉樹每層的結(jié)點(diǎn)數(shù)目都達(dá)到最大，則這棵二叉樹稱作滿二叉樹(fullbinarytree)。如果一棵二叉樹最多只有最下面的兩層結(jié)點(diǎn)度數(shù)可以小于2，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的連續(xù)位置上，則此二叉樹稱作完全二叉樹(completebinarytree)。1523456789114131211102345678911110完全二叉樹完全二叉樹的特點(diǎn)是：其葉結(jié)點(diǎn)只可能在層次最大的兩層出現(xiàn)完全二叉樹中由根結(jié)點(diǎn)到各個(gè)結(jié)點(diǎn)的路徑長度總和在具有同樣結(jié)點(diǎn)個(gè)數(shù)的二叉樹中達(dá)到了最小，即任意一棵二叉樹中根結(jié)點(diǎn)到各結(jié)點(diǎn)的最長路徑一定不短于結(jié)點(diǎn)數(shù)目相同的完全二叉樹中的路徑長度目錄

2、二叉樹的主要性質(zhì)性質(zhì)1.在二叉樹中，第i層上最多有2i-1個(gè)結(jié)點(diǎn)（i≥1）

證明：利用數(shù)學(xué)歸納法當(dāng)i=1時(shí)，2i-1=1，只有一個(gè)根結(jié)點(diǎn)，正確?，F(xiàn)在假設(shè)對(duì)所有的j，1≤j＜

i，命題成立，即第j層上之多有2j-1個(gè)結(jié)點(diǎn)。下面證明當(dāng)就j=i時(shí)結(jié)論也成立。由歸納假設(shè)，第i-1層上最多有2i-2個(gè)結(jié)點(diǎn)。由于二叉樹每個(gè)結(jié)點(diǎn)的度數(shù)最大為2，所以第i層上的最大結(jié)點(diǎn)數(shù)為第i-1層上的最大結(jié)點(diǎn)數(shù)的2倍，即2i-1個(gè)。二叉樹的主要性質(zhì)性質(zhì)2.高度為k的二叉樹至多有

2k-1個(gè)結(jié)點(diǎn)（k≥0）。其中高度(depth)定義為二叉樹中層數(shù)最大的葉結(jié)點(diǎn)的層數(shù)。證明：由性質(zhì)1可知，第i層的最大結(jié)點(diǎn)數(shù)為2i-1，所以二叉樹的主要性質(zhì)性質(zhì)3.任何一棵二叉樹，若其終端結(jié)點(diǎn)數(shù)為n0

，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1

。

證明：設(shè)n1為二叉樹中度為1的結(jié)點(diǎn)數(shù)。該二叉樹的結(jié)點(diǎn)總數(shù)n為度分別為0，1，2的結(jié)點(diǎn)數(shù)之和，即n=n0+n1+n2（5.1）

除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有一條邊進(jìn)入，設(shè)邊數(shù)為e，有n=e+1。由于這些邊是由度為1或2的的結(jié)點(diǎn)射出的，所以又有e=n1+2n2，于是得

n=e+1=n1+2n2+1 （5.2）由公式5.1和5.2得n0+n1+n2=n1+2n2+1，即n0=n2+1

二叉樹的主要性質(zhì)性質(zhì)4.滿二叉樹定理：非空滿二叉樹樹葉數(shù)目等于其分支結(jié)點(diǎn)數(shù)加1。

證明：滿二叉樹定理由性質(zhì)3可直接推出。

性質(zhì)5.滿二叉樹定理推論：一個(gè)非空二叉樹的空子樹數(shù)目等于其結(jié)點(diǎn)數(shù)加1。

證明：設(shè)二叉樹為T，度為1的結(jié)點(diǎn)下空子樹數(shù)目為1，度為0的節(jié)點(diǎn)空子樹數(shù)目為2，所以空子樹的數(shù)目為n1+2n0 根據(jù)性質(zhì)3，n=n1+n2+n0=n1+2n0-1 我們有：n1+2n0=n+1

二叉樹的主要性質(zhì)性質(zhì)6.有n個(gè)結(jié)點(diǎn)（n>0）的完全二叉樹的高度為[log2(n+1)]。其中二叉樹的高度(height)定義為二叉樹中層數(shù)最大的葉結(jié)點(diǎn)的層數(shù)。證明：假設(shè)高度為h，則根據(jù)性質(zhì)2和完全二叉樹的定義，有或不等式中各項(xiàng)取對(duì)數(shù)，于是得到。因?yàn)閔為整數(shù)，所以h＝[log2(n+1)]。

二叉樹的主要性質(zhì)性質(zhì)7.對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，結(jié)點(diǎn)按層次由左到右編號(hào)，則對(duì)任一結(jié)點(diǎn)i（1≤i≤n）有

（1）如果i=1，則結(jié)點(diǎn)i是二叉樹的根結(jié)點(diǎn)；若i＞1，則其父結(jié)點(diǎn)編號(hào)是[i/2]。（2）當(dāng)2i≤n時(shí)，結(jié)點(diǎn)i的左子結(jié)點(diǎn)是2i，否則結(jié)點(diǎn)i沒有左子結(jié)點(diǎn)。當(dāng)2i+1≤n時(shí)，結(jié)點(diǎn)i的右子結(jié)點(diǎn)是2i+1，否則結(jié)點(diǎn)i沒有右子結(jié)點(diǎn)。

二叉樹的主要性質(zhì)證明：對(duì)于i=1，由完全二叉樹的定義，其左孩子的編號(hào)是2，如果2>n，即不存在編號(hào)為1的結(jié)點(diǎn)，此時(shí)結(jié)點(diǎn)i沒有左孩子。其右孩子的編號(hào)只能是3，如果3>n，此時(shí)結(jié)點(diǎn)i沒有右孩子。對(duì)于i>1分兩種情況討論：(1)設(shè)第j層的第一個(gè)結(jié)點(diǎn)編號(hào)為i(此時(shí)有i=2j-1)，則其左孩子必為第j+1層的第一個(gè)結(jié)點(diǎn)，其編號(hào)為2j=2i，如果2i>n，那么i沒有左孩子；其右孩子必為第j+1層第二個(gè)結(jié)點(diǎn)，其編號(hào)為2i+1。(2)假設(shè)第j層的某個(gè)結(jié)點(diǎn)編號(hào)為i，若它有左孩子，那么它的左孩子必然是第j+1層中的第2[i-2j-1]個(gè)，那么其左孩子的編號(hào)就是2j+2[i-2j-1]=2i；如果結(jié)點(diǎn)i有右孩子，那么其右孩子的編號(hào)必是2i+2。目錄

3、二叉樹的存儲(chǔ)通常采用鏈接的形式lchild指向左孩子，rchild指向右孩子lchilddatarchildlchildparentdatarchild5.3.1二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)圖5.8

圖5.5中二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)

容易看出，在含有n個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)空鏈域?？梢岳眠@些空鏈域存儲(chǔ)其它的有用信息，形成其它的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。圖5.5二叉樹示例結(jié)點(diǎn)類型typedef

struct

BiTreeNode

{

BiTreeNode*lchild;

BiTreeNode*rchild;

ElemTypedata;}BiTree;

4、運(yùn)算遍歷（也叫周游）插入、刪除（1）遍歷遍歷廣度優(yōu)先遍歷——水平遍歷深度優(yōu)先遍歷——前序遍歷、中序遍歷、后序遍歷①水平遍歷概念：按照層次從小到大，從左到右訪問二叉樹的所有結(jié)點(diǎn)水平遍歷結(jié)果：ABCDEFGHI①水平遍歷思路：訪問結(jié)點(diǎn)的過程中應(yīng)該將其孩子結(jié)點(diǎn)存儲(chǔ)起來，等處理下一層時(shí)再取出來處理。從左到右遍歷，處理下一層時(shí)，結(jié)點(diǎn)遍歷的順序和存儲(chǔ)的順序一致所以采用隊(duì)列①水平遍歷算法初始化；當(dāng)隊(duì)不空時(shí)，重復(fù)做：出隊(duì)；處理；如果有左子，左子進(jìn)隊(duì)；如果有右子，右子進(jìn)隊(duì)；voidLevelOrder(BiTree*r){

if(r==NULL) return;

linkQue

aQue;

CreatlnkQueue(aQue);

BiTree*p=r;

enQueue(aQue,p);//根入隊(duì)

while(!QueisEmpty(aQue)) {

deQueue(aQue,p);//隊(duì)頭出隊(duì)

visit(p);//訪問

if(p->lchild!=NULL)

enQueue(aQue,p->lchild);//左孩子入隊(duì)

if(p->rchild!=NULL)

enQueue(aQue,p->rchild);//右孩子入隊(duì) }

DellnkQueue(aQue);}②前序遍歷概念：先處理根，然后遍歷左子樹，最后遍歷右子樹前序遍歷結(jié)果：ABDEGCFHI思路為了保證遍歷的持續(xù)，

需使用表臨時(shí)存儲(chǔ)

一些結(jié)點(diǎn)的地址。保存和取出的次序?yàn)橄冗M(jìn)后出。故應(yīng)使用棧。算法初始化當(dāng)未遍歷完，重復(fù)做：如果當(dāng)前結(jié)點(diǎn)非空，處理，進(jìn)棧，取左子；否則，出棧，取右子。voidPreOrder(BiTree*r){

if(r==NULL) return;

lnkStack*s=NULL;

BiTree*p;

p=r;

while(!StackIsEmpty(s)||p) {

if(p) {

visit(p);

push(s,p); p=p->lchild; } else {

pop(s,p); p=p->rchild; } }}③中序遍歷概念：先遍歷左子樹，然后處理根，最后遍歷右子樹中序遍歷結(jié)果：DBGEACHFI思路在前序遍歷的基礎(chǔ)上，將處理結(jié)點(diǎn)的語句后移。voidInOrder(BiTree*r){

if(r==NULL) return;

lnkStack*s=NULL;

BiTree*p=r;

while(!StackIsEmpty(s)||p) {

if(p) {

push(s,p); p=p->lchild; } else {

pop(s,p);

visit(p); p=p->rchild; } }}④后序遍歷概念：先遍歷左子樹，然后遍歷右子樹，最后處理根后序遍歷結(jié)果：DGEBHIFCA思路需要兩次訪問棧頂結(jié)點(diǎn)。前者是為了處理其右子樹，后者是為了處理該結(jié)點(diǎn)。算法取棧頂結(jié)點(diǎn)；如果是第一次訪問，設(shè)標(biāo)記，取右子；否則，出棧，處理。voidPostOrder(BiTree*r){

if(!r) return;

lnkStack*s=NULL;

BiTree*p=r;

PostOrderNodetag;

while(!StackIsEmpty(s)||p) {

while(p!=NULL) {

tag.p=p;

tag.isLeft=1;

push(s,tag); p=p->lchild; }

pop(s,tag);

if(tag.isLeft) {

tag.isLeft=0; p=tag.p;

push(s,tag); p=p->rchild; } else {

visit(tag.p); p=NULL; } }}深度優(yōu)先遞歸算法【算法1】

深度優(yōu)先前序遍歷voidPreOrder(BiTree*root){ //前序周游二叉樹或其子樹

if(r!=NULL){

Visit(r); //訪問當(dāng)前結(jié)點(diǎn)

PreOrder(r->lchild); //前序周游左子樹

PreOrder(r->rchild); //前序周游右子樹 }}深度優(yōu)先遞歸算法【算法2】

中序遍歷voidInOrder(BiTree*r){ if(r!=NULL){

InOrder(r->lchild); //中序周游左子樹

Visit(r); //訪問當(dāng)前結(jié)點(diǎn)

InOrder(r->rchild);//中序周游右子樹 }}深度優(yōu)先遞歸算法【算法3】后序遍歷voidPostOrder(BiTree*r){ //后序周游二叉樹或其子樹

if(r!=NULL){

PostOrder(r->lchild()); //后序周游左子樹

PostOrder(r->rchild()); //后序周游右子樹

Visit(r); //訪問當(dāng)前結(jié)點(diǎn) }}深度優(yōu)先遍歷二叉樹對(duì)于有n個(gè)結(jié)點(diǎn)的二叉樹，遍歷完樹的每一個(gè)元素都需要O(n)時(shí)間只要對(duì)每個(gè)結(jié)點(diǎn)的處理（函數(shù)Visit的執(zhí)行）時(shí)間是一個(gè)常數(shù)，那么遍歷二叉樹就可以在線性時(shí)間內(nèi)完成所需要的輔助空間為周游過程中棧的最大容量，即樹的高度最壞情況下具有n個(gè)結(jié)點(diǎn)的二叉樹高度為n，則所需要的空間復(fù)雜度為O(n)目錄

5、二叉樹的運(yùn)算例1：求二叉樹結(jié)點(diǎn)個(gè)數(shù)思路：將原有遍歷算法中訪問結(jié)點(diǎn)的函數(shù)從打印結(jié)點(diǎn)內(nèi)容改為計(jì)數(shù)即可例2求二叉樹中值為v的結(jié)點(diǎn)的父結(jié)點(diǎn)值思路一：在遍歷算法中，訪問結(jié)點(diǎn)變?yōu)楸容^結(jié)點(diǎn)的孩子值是否為V。思路二：采用后序遍歷。棧頂元素即為父結(jié)點(diǎn)例4.3已知二叉樹root，要求按層輸出各結(jié)點(diǎn)值思路：按層處理，采用水平遍歷，用計(jì)數(shù)器記錄每層入隊(duì)時(shí)結(jié)點(diǎn)的個(gè)數(shù)，出隊(duì)時(shí)計(jì)數(shù)器值為0時(shí)，該層結(jié)束，換行voidLevelOrderInLine(BiTree*r)//例4.3{

if(r==NULL) return;

linkQue

aQue;

CreatlnkQueue(aQue);

BiTree*p=r;

enQueue(aQue,p);

intcount=1;

int

dcount=0;

while(!QueisEmpty(aQue)) {

if(dcount==0) {

dcount=count; count=0; }

deQueue(aQue,p);

dcount--;

visit(p);

if(dcount==0)

cout<<endl;

if(p->lchild!=NULL) {

enQueue(aQue,p->lchild); count++; }

if(p->rchild!=NULL) {

enQueue(aQue,p->rchild); count++; } }

DellnkQueue(aQue);}4.2.6二叉樹的其他存儲(chǔ)及運(yùn)算①數(shù)組存儲(chǔ)②帶逆存儲(chǔ)③穿線存儲(chǔ)①數(shù)組存儲(chǔ)Struct

arrTree{ElemTypedata;int

lchildint

rchild}arrTree

a[n];0A121B342C-153D-1-14E6-15F786G-1-17H-1-18I-1-1②帶逆存儲(chǔ)對(duì)于經(jīng)常求父結(jié)點(diǎn)的問題，結(jié)點(diǎn)在存儲(chǔ)時(shí)，可以存儲(chǔ)父結(jié)點(diǎn)lchildparentdatarchild③穿線存儲(chǔ)穿線存儲(chǔ)的二叉樹，也叫穿線樹、或線索二叉樹。利用結(jié)點(diǎn)中空閑的左右子鏈域：若作子鏈域空，則存儲(chǔ)制定遍歷下的前綴結(jié)點(diǎn)的地址；若右子鏈域空，則存儲(chǔ)指定遍歷下后繼結(jié)點(diǎn)的地址構(gòu)造方法

寫出遍歷序列畫出穿線鏈修改相應(yīng)鏈域:為了區(qū)別是否是穿線鏈，加標(biāo)記前序遍歷穿線樹ABDEGCFHI中序穿線樹DBGEACHFI后序遍歷：DGEBHIFCA4.3樹的應(yīng)用1.二叉排序樹2.堆排序3.哈夫曼樹4.決策樹5.博弈樹1、二叉排序樹二叉搜索樹中的每個(gè)非空結(jié)點(diǎn)表示一個(gè)記錄某結(jié)點(diǎn)左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于該結(jié)點(diǎn)的關(guān)鍵碼值若其右子樹不為空，則右子樹上所有結(jié)點(diǎn)的值均大于該結(jié)點(diǎn)的關(guān)鍵碼值樹中各結(jié)點(diǎn)的關(guān)鍵碼必須是唯一的二叉搜索樹可以是一棵空樹，任何結(jié)點(diǎn)的左右子樹都是二叉搜索樹,按照中序周游整個(gè)二叉樹得到一個(gè)由小到大有序排列1、二叉排序樹對(duì)于關(guān)鍵碼集合K={50，19，35，55，20，5，100，52，88，53，92}，二叉排序樹的生成過程如圖所示：5051955355220100539288查找插入刪除二叉排序樹的查找二叉排序樹的高效率在于繼續(xù)檢索時(shí)只需要查找兩棵子樹之一：將給定值key與根結(jié)點(diǎn)的關(guān)鍵碼比較，如果key小于根結(jié)點(diǎn)的值，則只需要檢索左子樹如果key大于根結(jié)點(diǎn)的值，就只檢索右子樹這個(gè)過程一直持續(xù)到key被匹配成功或者遇到葉結(jié)點(diǎn)為止如果遇到葉結(jié)點(diǎn)仍沒有發(fā)現(xiàn)key，那么key就不在這棵二叉搜索樹中查找運(yùn)算

無需遍歷算法效率與樹的高度相關(guān)二叉排序樹的插入算法：插入運(yùn)算

要點(diǎn)：保持二叉排序樹的特性插入位置的選擇二叉排序樹的插入算法：需要運(yùn)用檢索方法，查找待插入關(guān)鍵碼是否在樹中如果存在則不允許插入重復(fù)關(guān)鍵碼如果直到找到空結(jié)點(diǎn)還沒有發(fā)現(xiàn)重復(fù)關(guān)鍵碼，那么就把新結(jié)點(diǎn)插入到待插入方向作為新的葉結(jié)點(diǎn)對(duì)于給定的關(guān)鍵碼集合，可以從一個(gè)空的二叉搜索樹開始，按照檢索路徑搜索這棵二叉樹，將關(guān)鍵碼一個(gè)個(gè)插入到相應(yīng)的葉結(jié)點(diǎn)位置，從而動(dòng)態(tài)生成二叉搜索樹二叉排序樹插入操作：將待插入結(jié)點(diǎn)的關(guān)鍵碼與根結(jié)點(diǎn)的關(guān)鍵碼相比較，若待插入的關(guān)鍵碼小于根結(jié)點(diǎn)的關(guān)鍵碼，則進(jìn)入左子樹，否則進(jìn)入右子樹。按照同樣的方式沿檢索路徑直到葉結(jié)點(diǎn)，確定插入位置，把待插入結(jié)點(diǎn)作為一個(gè)新葉結(jié)點(diǎn)插入到二叉搜索樹中。二叉排序樹的刪除設(shè)pointer，temppointer是指針變量，其中pointer表示要?jiǎng)h除的結(jié)點(diǎn)。首先找到待刪除的結(jié)點(diǎn)pointer，刪除該結(jié)點(diǎn)的過程如下：若結(jié)點(diǎn)pointer沒有左子樹，則用pointer右子樹的根代替被刪除的結(jié)點(diǎn)pointer；若結(jié)點(diǎn)pointer有左子樹，則在左子樹里找到按中序周游的最后一個(gè)結(jié)點(diǎn)temppointer，把temppointer的右指針置成指向pointer的右子樹的根，然后用結(jié)點(diǎn)pointer左子樹的根代替被刪除的結(jié)點(diǎn)pointer。

二叉排序樹的刪除圖5.12二叉搜索樹的刪除示例圖5.11二叉搜索樹二叉排序樹的刪除改進(jìn)的二叉搜索樹結(jié)點(diǎn)刪除算法的思想為：若結(jié)點(diǎn)pointer沒有左子樹，則用pointer右子樹的根代替被刪除的結(jié)點(diǎn)pointer若結(jié)點(diǎn)pointer有左子樹，則在左子樹里找到按中序周游的最后一個(gè)結(jié)點(diǎn)temppointer（即左子樹中的最大結(jié)點(diǎn)）由于temppointer沒有右子樹，刪除該結(jié)點(diǎn)只需用temppointer的左子樹代替temppointer，然后用temppointer結(jié)點(diǎn)代替待刪除的結(jié)點(diǎn)pointer二叉搜索樹的刪除圖5.13改進(jìn)的二叉搜索樹的刪除圖5.11二叉搜索樹52.552.5堆排序相關(guān)概念滿二叉樹完全二叉樹堆排序堆：是這樣的二叉樹，他的每個(gè)結(jié)點(diǎn)的值都大于它的兩個(gè)孩子（如果存在）的值，這就是堆最大堆：如果結(jié)點(diǎn)的值都大于孩子的值最小堆：如果結(jié)點(diǎn)的值都小于孩子的值302510201755421355941746堆的性質(zhì)從邏輯的角度來講，堆是一種樹形結(jié)構(gòu)，而且是一種特殊的完全二叉樹。此完全二叉樹的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于序列中的一個(gè)關(guān)鍵碼，根結(jié)點(diǎn)對(duì)應(yīng)于關(guān)鍵碼K0，按層次從左至右依次類推。說其特殊，主要是因?yàn)槎研蛑皇蔷植坑行?，即最小堆?duì)應(yīng)的完全二叉樹中所有內(nèi)部結(jié)點(diǎn)的值均不大于其左右孩子的關(guān)鍵碼值，而一個(gè)結(jié)點(diǎn)與其兄弟之間沒有必然的聯(lián)系。最小堆不像二叉搜索樹那樣實(shí)現(xiàn)了關(guān)鍵碼的完全排序。相比較而言，只有當(dāng)結(jié)點(diǎn)之間是父子關(guān)系的時(shí)候，才可以確定這兩個(gè)結(jié)點(diǎn)關(guān)鍵碼的大小關(guān)系。堆排序思路：將一個(gè)順序表看作是順序存儲(chǔ)的完全二叉樹將其調(diào)整為堆，則得到最大結(jié)點(diǎn)最大結(jié)點(diǎn)離堆，剩下結(jié)點(diǎn)調(diào)整成堆，次大結(jié)點(diǎn)離堆重復(fù)上述過程，直到只剩下一個(gè)結(jié)點(diǎn)（46，94，13，42，55，17，10，70）4694131017554270建堆算法從最后一個(gè)非葉結(jié)點(diǎn)開始逐個(gè)篩for(p=n/2;p>=1;p--)

sift(p,n);n/2篩一個(gè)結(jié)點(diǎn)的算法當(dāng)p有孩子時(shí)將p較大的孩子=>k如果s[p]<s[k]則交換s[p],s[k]

否則結(jié)束（46，94，13，42，55，17，10，70）4694131017554270堆排序算法

set_heap(s,n)for(i=n;i>=2;i--)swap(s[1],s[i])sift(1,i-1)時(shí)間效率建堆算法：篩n/2個(gè)結(jié)點(diǎn)，log2n次比較選擇排序：n-1遍，log2n次比較

O(nlog2n) 3、哈夫曼樹

Huffman樹

Huffman編碼Huffman樹假設(shè)有n個(gè)權(quán)值分別為w1，w2，…，wn(n≥2)的結(jié)點(diǎn)，求帶權(quán)路徑長度就是要構(gòu)造一棵二叉樹，每一個(gè)葉子結(jié)點(diǎn)ki取wi作為它的權(quán)，li表示該葉子結(jié)點(diǎn)的路徑長度，則帶權(quán)路徑長度可記作WPL(T)WPL(T)=,其中帶權(quán)路徑長度最小的二叉樹稱為Huffman樹。

Huffman樹例如，圖中表示了三棵具有4個(gè)葉結(jié)點(diǎn)的二叉樹，各葉結(jié)點(diǎn)的權(quán)值分別為6，2，3，4。它們的帶權(quán)路徑長度分別為：(a)6×2+2×2+3×2+4×2=30(b)6×2+2×3+3×3+4×1=31(c)6×1+2×3+3×3+4×2=29其中，5.18(c)中所示的二叉樹帶權(quán)路徑長度最小?？梢则?yàn)證，它就是一棵Huffman樹，也就是說，這棵樹在所有的具有6，2，3，4權(quán)值的葉結(jié)點(diǎn)的二叉樹中帶權(quán)路徑長度最小。圖5.18具有不同帶權(quán)外部路徑長度的二叉樹3、Huffman樹建立Huffman編碼樹：(1)對(duì)于給定的n個(gè)權(quán)值w1，w2，…，wn(n≥2)，構(gòu)成n棵二叉樹的集合T={T1，T2，…，Tn}，使得每一棵二叉樹只具有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)。(2)構(gòu)造一棵新的二叉樹，在集合T中找出兩個(gè)權(quán)值最小的樹作為新樹根結(jié)點(diǎn)的左右子樹，把新樹根結(jié)點(diǎn)的權(quán)值賦為其左右子樹根結(jié)點(diǎn)的和。(3)在集合T中刪除這兩棵樹，并把得到的新二叉樹加入到集合中。(4)重復(fù)步驟(2)、(3)的操作，直到集合T中只含有一棵樹為止。5.6.1Huffman樹Huffman樹的構(gòu)造過程236495152364（1）HT是權(quán)值越大的越靠近根結(jié)點(diǎn)；（2）HT不唯一，但WPL一定相等。5915typedef

struct

HuffmanNode{

intweight;//權(quán)值

intparent;//雙親下標(biāo)

int

lchild,rchild;//左右孩子下標(biāo)}HTree;HTree*intHTree(int*Element,int

n,int&cursize,int&size){//初始化，將權(quán)值Element賦給哈夫曼樹為葉結(jié)點(diǎn)

inti;

HTree*list; size=2*n-1;//樹中結(jié)點(diǎn)的個(gè)數(shù)

list=newHTree[size];

for(i=0;i<n;i++) {

list[i].weight=Element[i]; }

for(i=0;i<size;i++) {

list[i].parent=-1;

list[i].lchild=list[i].rchild=0; }

cursize=n; returnlist;}bool

FindMinTwo(HTree*list,int

cursize,int&f,int&s){

inti;

for(i=0;i<cursize;i++) {

if(list[i].parent==-1) { f=i; break; } }

if(i>=cursize) returnfalse;

for(++i;i<cursize;i++) {

if(list[i].parent==-1) { s=i; break; } }

if(i>=cursize) returnfalse;

if(list[f].weight>list[s].weight) {

int

tmp;

tmp=f; f=s; s=tmp; }

for(++i;i<cursize;i++) {

if(list[i].parent==-1&&list[i].weight<list[f].weight) { s=f; f=i; } elseif(list[i].parent==-1&&list[i].weight<list[s].weight) { s=i; } } returntrue;

}voidCreatHuffmanTree(HTree*&list,int

size,int&cursize){

int

f,s;

while(FindMinTwo(list,cursize,f,s)) {

list[cursize].weight=list[f].weight+list[s].weight;

list[cursize].lchild=f;

list[cursize].rchild=s;

list[f].parent=cursize;

list[s].parent=cursize;

list[cursize].parent=-1;

cursize++; }}5.6.2Huffman編碼Huffman編碼過程如下：用d1，d2，…，dn作為外部結(jié)點(diǎn)構(gòu)造具有最小路徑長度的二叉樹把從每個(gè)結(jié)點(diǎn)引向其左子結(jié)點(diǎn)的邊標(biāo)上號(hào)碼0，從每個(gè)結(jié)點(diǎn)引向其右子結(jié)點(diǎn)的邊標(biāo)上號(hào)碼1從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)路徑上的編號(hào)連接起來就是這個(gè)外部結(jié)點(diǎn)所代表字符的編碼。得到的二進(jìn)制前綴碼就稱作Huffman編碼圖5.20

Huffman編碼示例5.6.2Huffman編碼用Huffman算法構(gòu)造出的二叉樹給出了各字符的編碼，同時(shí)也用來譯碼從二叉樹的根開始，把二進(jìn)制編碼每一位的值與Huffman樹邊上標(biāo)記的0，1相匹配，確定選擇左分支還是右分支，直至確定一條到達(dá)樹葉的路徑。一旦到達(dá)樹葉，就譯出了一個(gè)字符。然后繼續(xù)用這棵二叉樹繼續(xù)譯出其它二進(jìn)制編碼AACBACBAABAABCDCACADAACCA定長編碼：A:00;B:01;C:10;D:11編碼長度：50

哈夫曼編碼AACBACBAABAABCDCACADAACCA不定長編碼：A:12;B:4;C:7;D:2A:0;B:01;C:1;D:11編碼長度：31001010101...AACBACBAABAABCDCACADAACCA不定長編碼：A:12;B:4;C:7;D:2A:0;B:101;C:11;D:100編碼長度：440011101011101…返回voidCode(HTree*list,char**Hc,intn){

int

start,pi,j,i=0; char*s=newchar[n];

while(i<n){ s[n-1]='\0'; start=n-1; pi=list[i].parent; j=i;

while(pi!=-1){

if(list[pi].lchild==j) s[--start]='0'; elses[--start]='1'; j=pi; pi=list[pi].parent; }

strcpy(Hc[i],&s[start]); i++; } delete[]s;}5.6.2Huffman編碼

例如，在一個(gè)數(shù)據(jù)通信系統(tǒng)中使用的字符是a，b，c，d，e，f，g，對(duì)應(yīng)的頻率分別為15，2，6，5，20，10，18。各字符的二進(jìn)制編碼為：a：00b：11110c：1110d：11111e：10f：110g