




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、第六章第六章 樹和二叉樹樹和二叉樹本章主要內(nèi)容本章主要內(nèi)容一、樹的基本概念一、樹的基本概念二、二叉樹二、二叉樹三、二叉樹的遍歷三、二叉樹的遍歷三、線索二叉樹三、線索二叉樹四、樹和森林四、樹和森林六、哈夫曼樹六、哈夫曼樹七、本章主要要求七、本章主要要求6.1 樹的基本概念樹的基本概念 1.定義:是一種常非線性結(jié)構(gòu)樹是n(n0)個(gè)結(jié)點(diǎn)的有限集合。若n=0,則稱為空樹;否則,有且僅有一個(gè)特定的結(jié)點(diǎn)被稱為根,當(dāng)n1時(shí),其余結(jié)點(diǎn)被分成m(m0)個(gè)互不相交的子集T1,T2,.,Tm,每個(gè)子集又是一棵樹。遞歸定義的遞歸定義的樹的幾種形態(tài)2.樹的特點(diǎn)樹的特點(diǎn)(1)樹的根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn),除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)
2、有且只有一個(gè)前驅(qū)結(jié)點(diǎn)(2)樹中所有結(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼結(jié)點(diǎn)3.樹的相關(guān)概念樹的相關(guān)概念1) 結(jié)點(diǎn) 數(shù)據(jù)元素的內(nèi)容及其指向其子樹根的分支統(tǒng)稱為結(jié)點(diǎn)2) 結(jié)點(diǎn)的度 結(jié)點(diǎn)的分支數(shù)。3) 終端結(jié)點(diǎn)(葉子) 度為0的結(jié)點(diǎn)。4) 非終端結(jié)點(diǎn) 度不為0的結(jié)點(diǎn)。5) 結(jié)點(diǎn)的層次 樹中根結(jié)點(diǎn)的層次為1,根結(jié)點(diǎn)子樹的根為第2層,以此類推。6) 樹的度 樹中所有結(jié)點(diǎn)度的最大值。7) 樹的深度 樹中所有結(jié)點(diǎn)層次的最大值。8) 有序樹、無序樹 如果樹中每棵子樹從左向右的排列擁有一定的順序,不得互換,則稱為有序樹,否則稱為無序樹。9) 森林 是m(m0)棵互不相交的樹的集合。 在樹結(jié)構(gòu)中,結(jié)點(diǎn)之間的關(guān)系又可以用家族關(guān)
3、系描述,定義如下:10)孩子、雙親 結(jié)點(diǎn)子樹的根稱為這個(gè)結(jié)點(diǎn)的孩子,而這個(gè)結(jié)點(diǎn)又被稱為孩子的雙親。11)子孫 以某結(jié)點(diǎn)為根的子樹中的所有結(jié)點(diǎn)都被稱為是該結(jié)點(diǎn)的子孫。12)祖先 從根結(jié)點(diǎn)到該結(jié)點(diǎn)路徑上的所有結(jié)點(diǎn)。13)兄弟 同一個(gè)雙親的孩子之間互為兄弟。14)堂兄弟 雙親在同一層的結(jié)點(diǎn)互為堂兄弟。4.樹的表示法樹的表示法n直觀表示法n嵌套集合表示法n凹入表示法 /不清晰n廣義表表示法(1)(2)(3)(4)返回返回6.2 二叉樹二叉樹1.定義:定義:叉樹是n(n0)個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí),稱為空二叉樹;當(dāng)n0時(shí),有且僅有一個(gè)結(jié)點(diǎn)為二叉樹的根,其余結(jié)點(diǎn)被分成兩個(gè)互不相交的子集,一個(gè)稱為左子集
4、,另一個(gè)稱為右子集,每個(gè)子集又是一個(gè)二叉樹 遞歸定義的遞歸定義的2.二叉樹的五種形態(tài)二叉樹的五種形態(tài)例3.二叉樹的性質(zhì)二叉樹的性質(zhì) n 在二叉樹的第i層上最多有2i-1個(gè)結(jié)點(diǎn)(i1) n深度為K的二叉樹最多有2K-1個(gè)結(jié)點(diǎn)(K1) n對(duì)于任意一棵二叉樹BT,如果度為0的結(jié)點(diǎn)個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)個(gè)數(shù)為n2,則n0=n2+1 二叉樹的總度數(shù)二叉樹的總度數(shù)n1+2n2二叉樹的節(jié)點(diǎn)數(shù)二叉樹的節(jié)點(diǎn)數(shù)n0n1n2二叉樹的總度數(shù)二叉樹的節(jié)點(diǎn)數(shù)二叉樹的總度數(shù)二叉樹的節(jié)點(diǎn)數(shù)1 n1+2n2=n0n1n2-1 即:即: n0=n2+1n具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n+1 證明:假設(shè)具有n個(gè)結(jié)點(diǎn)的
5、完全二叉樹的深度為K,則根據(jù)性質(zhì)2可以得出: 2K-1-1n2K-1將不等式兩端加1得到: 2K-1n2K取以2為底的對(duì)數(shù),化簡: K-1log2nn,則結(jié)點(diǎn)i沒有左孩子;否則其左孩子結(jié)點(diǎn)的編號(hào)為2i。如果2i+1n,則結(jié)點(diǎn)i沒有右孩子;否則其右孩子結(jié)點(diǎn)的編號(hào)為2i+1。證明:采用數(shù)學(xué)歸納法,請(qǐng)大家自行閱讀教材證明:采用數(shù)學(xué)歸納法,請(qǐng)大家自行閱讀教材4.4.二叉樹的存儲(chǔ)二叉樹的存儲(chǔ)n順序存儲(chǔ)結(jié)構(gòu)n鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 通常二叉樹可以用下面兩種方式存儲(chǔ):下頁介紹(1) 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)適用完全二叉樹,用一組連續(xù)的存儲(chǔ)單元按照完全二叉樹的每個(gè)結(jié)點(diǎn)編號(hào)的順序存放結(jié)點(diǎn)內(nèi)容 如下圖所示: 下頁給出C實(shí)現(xiàn)
6、#define MaxTreeNodeNum 100typedef struct DataType dataMaxTreeNodeNum; /* 根存儲(chǔ)在下標(biāo)為1的數(shù)組單元中 */ int n; /* 當(dāng)前完全二叉樹的結(jié)點(diǎn)個(gè)數(shù) */QBTree;順序存儲(chǔ)特點(diǎn):順序存儲(chǔ)特點(diǎn):二叉樹是完全二叉樹時(shí),空間利用率高、尋找孩子和雙親比較容易。若二叉樹不是完全二叉樹,需要將空缺的位置用特定的符號(hào)填補(bǔ),造成空間利用率的下降 引出鏈?zhǔn)酱鎯?chǔ)(2)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)注:Lchild和Rchild是分別指向該結(jié)點(diǎn)左孩子和右孩子的指針 下頁C實(shí)現(xiàn)typedef char DataType/* 設(shè)結(jié)點(diǎn)內(nèi)容的數(shù)據(jù)類
7、型為字符型 */ typedef struct bnode DataType data; struct bnode *lchild, *rchild; Bnode, *BTree;二叉樹鏈接存儲(chǔ)的節(jié)點(diǎn)定義二叉樹鏈接存儲(chǔ)的節(jié)點(diǎn)定義返回返回6.3 6.3 二叉樹的遍歷二叉樹的遍歷定義:按照一定規(guī)則訪問二叉樹的所有節(jié)點(diǎn)一定義:按照一定規(guī)則訪問二叉樹的所有節(jié)點(diǎn)一次次先序遍歷先序遍歷TLR、中序遍歷中序遍歷LTR和和后序遍歷后序遍歷 LRT層次遍歷層次遍歷下頁分述TLR(1)先序遍歷TLR若二叉樹為空,則結(jié)束遍歷操作;否則訪問根結(jié)點(diǎn);先序遍歷根的左子樹;先序遍歷根的右子樹 遞歸算法,思考它所對(duì)應(yīng)的非遞歸
8、算法先看遍歷的結(jié)果下頁C實(shí)現(xiàn)void PreOrder ( BTree t ) if ( t ) visite (t-data); /* 訪問結(jié)點(diǎn)內(nèi)容訪問結(jié)點(diǎn)內(nèi)容 */ PreOrder ( t-lchild ); /* 遍歷左子樹遍歷左子樹 */ PreOrder ( t-rchild ); /* 遍歷右子樹遍歷右子樹 */ 思考:1. visite 函數(shù)能做什么? 2.visite (t-data)這條語句執(zhí)行次數(shù)? 3.如何計(jì)算結(jié)點(diǎn)個(gè)數(shù)、葉子個(gè)數(shù)? 4.改變visite (t-data)這條語句的位置會(huì)產(chǎn)生 什么效果?思考如何得到中序和后序遍歷的算法?(2)中序遍歷和后序遍歷算法中序遍歷
9、void InOrder ( BTree t ) if ( t ) InOrder ( t-lchild ); Visite (t-data); InOrder ( t-rchild ); 后序遍歷void PostOrder ( BTree t ) if ( t ) PostOrder ( t-lchild ); PostOrder ( t-rchild ); Visite(t-data); 三種訪問序列的結(jié)果三種訪問序列的結(jié)果(3)三種遍歷的非遞歸算法樹的定義是遞歸的,容易實(shí)現(xiàn)遍歷的遞歸算法思考遍歷算法的執(zhí)行過程找出它們所對(duì)應(yīng)的非遞歸算法?1) 先序遍歷的非遞歸算法void PreOrde
10、r (BTree t) PSeqStack S; BTree p = t; /*初始化 */ S=Init_SeqStack ( ); /* 棧初始化*/while ( p |!Empty_SeqStack ( S) if ( p) Visite (p-data) ; Push_SeqStack ( S, p); /* 預(yù)留p指針在棧中 */ p = p-lchild; else Pop_SeqStack (S,&p ); p = p-rchild; /* 左子樹為空, 進(jìn)右子樹 */end while/end preorder2) 中序遍歷的非遞歸算法n將上述算法稍微改動(dòng)就能寫出中序
11、遍歷的非遞歸算法,請(qǐng)讀者思考兩個(gè)算法的差異.void InOrder (BTree T) PSeqStack S; BTree p = t; S=Init_SeqStack ( ); /*初始化初始化 */while ( p |!Empty_SeqStack ( S) if ( p) Push_SeqStack ( S, p); /* 預(yù)留預(yù)留p指針在棧中指針在棧中 */ p = p-lchild; else Pop_SeqStack (S,&p ); Visite (p-data) ; p = p-rchild; /* 左子樹為空左子樹為空, 進(jìn)右子樹進(jìn)右子樹 */ 3) 后序遍歷的
12、非遞歸算法n先思考如下問題: *在先序中序遍歷中,每個(gè)結(jié)點(diǎn)(結(jié)點(diǎn)地址)進(jìn)棧幾次?出棧幾次? *在后序遍歷中,每個(gè)結(jié)點(diǎn)(結(jié)點(diǎn)地址)進(jìn)棧幾次?出棧幾次? *為什么后序遍歷特殊呢? *如何區(qū)別結(jié)點(diǎn)的第1次和第2次進(jìn)(出)棧? 3) 后序遍歷的非遞歸算法typedef struct Bnode *node; int flag;DataType;void PostOrder (BTree t ) PSeqStack S; DataType Sq;int tag;BTree p = t;S=Init_SeqStack();/* 棧初始化棧初始化*/while ( p |!Empty_SeqStack (S
13、 ) if ( p) Sq.flag=0; Sq.node=p;Push_SeqStack (S, Sq); /*將將p指針以及指針以及flag壓入棧中壓入棧中 */p = p-lchild;elsePop_SeqStack (S,&Sq); p = Sq.node; if (Sq.flag=0) Sq.flag=1; Push_SeqStack (S,Sq); /*二次壓棧二次壓棧 */ p= p-rchild; else Visite (p-data ); p=null; /思考為什么?思考為什么? /* 把把p賦空從棧中彈出下個(gè)結(jié)點(diǎn)賦空從棧中彈出下個(gè)結(jié)點(diǎn)*/ /endif /en
14、d if/endwhileend postorder (4)層次遍歷二叉樹)層次遍歷二叉樹定義:按照樹深度的次序從左到右依次訪問二定義:按照樹深度的次序從左到右依次訪問二叉樹的所有節(jié)點(diǎn)叉樹的所有節(jié)點(diǎn)下頁給出下頁給出C實(shí)現(xiàn)實(shí)現(xiàn)層次遍歷算法void LevelOrder(BTree T) BTree p=T; if (P) Init_SeqQueue(Q); /初始化隊(duì)列 Visite(p); In_SeqQueue(Q,p); /訪問根結(jié)點(diǎn),并將根結(jié)點(diǎn)入隊(duì) while (!Empty_SeqQueue(Q) /當(dāng)隊(duì)非空時(shí)重復(fù)執(zhí)行下列操作 Out_SeqQueue(Q,&p); /出隊(duì) i
15、f (p-Lchild) Visite(p-Lchild);In_SeqQueue(Q,p-Lchild); /處理左孩子 if (p-Rchild) Visite(p-Rchild);In_SeqQueue(Q,p-Rchild); /處理右孩子 (5) 二叉樹遍歷算法的應(yīng)用二叉樹遍歷算法的應(yīng)用 二叉樹是遞歸定義,可以寫出它的遞歸遍歷算法,同時(shí)借助遍歷算法可以實(shí)現(xiàn)一些基本的應(yīng)用,如: 節(jié)點(diǎn)計(jì)數(shù) 創(chuàng)建二叉樹 計(jì)算二叉樹的高度等例例1:創(chuàng)建二叉樹:創(chuàng)建二叉樹n有多種創(chuàng)建二叉樹的方法(按先序建,按層次建,按中序和先序遍歷結(jié)果建等),以下算法按先序建n在輸入先序序列時(shí),需要在空節(jié)點(diǎn)填補(bǔ)一個(gè)特殊的字符
16、,比如,#。如果讀入的字符是#,則在相應(yīng)的位置上構(gòu)造一棵空二叉樹;否則,創(chuàng)建一個(gè)新結(jié)點(diǎn)。n采用先序遍歷遞歸算法為基礎(chǔ),二叉樹中結(jié)點(diǎn)之間的指針連接是通過指針參數(shù)在遞歸調(diào)用返回時(shí)完成下頁給出下頁給出C實(shí)現(xiàn)實(shí)現(xiàn)創(chuàng)建二叉樹創(chuàng)建二叉樹BTree CreateBinTree()/* 以加入空結(jié)點(diǎn)的先序序列輸入,構(gòu)造二叉鏈表 */ char ch; BTree t; ch=getchar(); if (ch=) t=null; /*讀入時(shí),將相應(yīng)結(jié)點(diǎn)指針置空*/ else t=(BTree)malloc(sizeof(Bnode); /* 生成結(jié)點(diǎn)空間 */ t-data=ch; t-lchild =Cre
17、ateBinTree(); /*構(gòu)造二叉樹的左子樹 */ t-rchild =CreateBinTree(); /*構(gòu)造二叉樹的右子樹 */ return t;思考:思考: 1.如何輸入?如何輸入? 2.能否中序建樹和后序建樹?能否中序建樹和后序建樹?例例2:求二叉樹每層結(jié)點(diǎn)個(gè)數(shù):求二叉樹每層結(jié)點(diǎn)個(gè)數(shù) 思路:思路:二叉樹中每個(gè)結(jié)點(diǎn)都對(duì)應(yīng)一個(gè)層次,如果當(dāng)前結(jié)點(diǎn)T對(duì)應(yīng)的層次是L,則T-Lchild和T-Rchild所對(duì)應(yīng)的層次就是L+1,利用這個(gè)特性,我們很容易用遍歷算法求出結(jié)果 設(shè)置一個(gè)數(shù)組,數(shù)組的下標(biāo)表示樹的層數(shù),該下標(biāo)元素的值記錄該層元素的個(gè)數(shù);通過樹的遍歷算法來得到最終數(shù)組元素的值下頁給出
18、C實(shí)現(xiàn)void Levcoun (BTree t, int L, int num ) /* 求鏈?zhǔn)酱鎯?chǔ)的二叉樹t中每層結(jié)點(diǎn)個(gè)數(shù)L表示當(dāng)前t所指結(jié)點(diǎn)的層次,當(dāng)t初值為根時(shí),L初值為1,num數(shù)組元素初始化0 */ if ( t) Visite (t-data); /訪問當(dāng)前結(jié)點(diǎn) numL+; /當(dāng)前t所指結(jié)點(diǎn)的層次數(shù)增加1 Levcoun (t-lchild, L+1, num); /遞歸左子樹 Levcoun (t-rchild, L+1, num);/遞歸右子樹 例例3 3:計(jì)算二叉樹的高度:計(jì)算二叉樹的高度 樹的高度定義:樹中節(jié)點(diǎn)深度的最大值思路:二叉樹的高度是左右子樹的最大高度+1 ,所
19、以先計(jì)算出左右子樹高度的較大值,左右子樹高度的求法和原二叉樹高度的求法一樣,所以采用遞歸方法。下頁給出C實(shí)現(xiàn)int Height ( BTree t ) int h1,h2; if (t=null) return 0; else h1=Height ( t-lchild ); /*求左子樹的高度*/ h2=Height ( t-rchild ); /*求右子樹的高度*/ if (h1h2) return h1+1; else return h2+1; int Height ( BTree t ) int h1,h2; if (t=null) return 0; return(h1=Height
20、(t-lchild) h2=Height(t-rchild) ? h1+1: h2+1); 例例4 復(fù)制二叉樹復(fù)制二叉樹n已知一棵二叉樹用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),要求將此二叉樹復(fù)制成另外一棵二叉樹 思路:復(fù)制包括復(fù)制根節(jié)點(diǎn),左子樹,右子樹,并且把復(fù)制的左右子樹掛到復(fù)制的根節(jié)點(diǎn)上 采用遞歸的思想來實(shí)現(xiàn)復(fù)制樹下頁給出C實(shí)現(xiàn)BTree CopyTree (BTree t) BTree p,q,s; if (t=null) return (null); p=CopyTree(t-lchild); /*復(fù)制左子樹*/ q=CopyTree(t-rchild); /*復(fù)制左子樹*/ s=(Bnode *)mallo
21、c(sizeof(Bnode); /* 復(fù)制根結(jié)點(diǎn) */ s-data=t-data; s- lchild=p; s- rchild=q; return s;例5 交換二叉樹的左右子樹要求:將二叉樹中所有的左右子樹交換 void change_left_right(BTree t) if (t) change_left_right(t-lchild); change_left_right(t-rchild); t-lchildt-rchild; 交換的簡寫交換的簡寫返回返回6.4 線索二叉樹線索二叉樹問題的提出:二叉樹中有很多(思考:到底有多少?)閑置的指針,能否利用它們?yōu)樵L問二叉樹提供便利,
22、如下圖所示:如:求解某結(jié)點(diǎn)在某種遍歷次序下的前驅(qū)或后 繼結(jié)點(diǎn)求前驅(qū)和后繼的方法:求前驅(qū)和后繼的方法:遍歷通過指定次序的遍歷發(fā)現(xiàn)結(jié)點(diǎn)的前驅(qū)或后繼,費(fèi)時(shí)間,低效增設(shè)前驅(qū)和后繼指針在每個(gè)結(jié)點(diǎn)中增設(shè)兩個(gè)指針,分別指示該結(jié)點(diǎn)在指定次序下的前驅(qū)或后繼。增加空間開銷利用二叉鏈表中的空指針域(n個(gè)結(jié)點(diǎn)的二叉樹有n+1個(gè)空指針域),將二叉鏈表中的空的指針域改為指向其前驅(qū)和后繼:空的左孩子指針指向其前驅(qū),空的右孩子指針指向其后繼 比較好的比較好的方法方法線索化線索化為什么?為什么?一般采用加區(qū)分標(biāo)志的線索化一般采用加區(qū)分標(biāo)志的線索化ltag=0: lchild指示該結(jié)點(diǎn)的左孩子ltag=1: lchild指針該結(jié)
23、點(diǎn)的前趨。rtag=0: rchild指示該結(jié)點(diǎn)的右孩子rtag=1: rchild指針該結(jié)點(diǎn)的后繼。 有線索標(biāo)有線索標(biāo)志的二叉志的二叉樹樹ABCDE A B D C ET中序序列:BCAED0000111111v中序線索二叉樹1.線索二叉樹的實(shí)現(xiàn)(中序)線索二叉樹的實(shí)現(xiàn)(中序)線索二叉鏈表結(jié)構(gòu)描述如下:線索二叉鏈表結(jié)構(gòu)描述如下:typedef char DataType; /*不妨設(shè)數(shù)據(jù)類型為字符型 */ typedef struct Threadnode int ltag,rtag; DataType data; struct Threadnode *lchild, *rchild;Thr
24、eadnode,*ThreadTree;采用遞歸的思想中序線索化算法void InThread (ThreadTree t, ThreadTree pre) /* 遞歸中序線索化二叉樹 ; 函數(shù)調(diào)用前pre為空 ,pre為t的前驅(qū)*/ if (t) InThread(t-lchild,pre); /* 中序線索化左子樹 */ if (t-lchild=null) /* 建立前驅(qū)線索 */ t-ltag=1; t-lchild=pre; /* 左孩子域指向前驅(qū)*/ if(t-rchild=null) t-rtag=1;/*為下次后繼線索做準(zhǔn)備*/ if (pre)&(pre-rtag=1
25、) /* 建立后繼線索 */ pre-rchild=t; pre=t; InThread (t-rchild,pre); /*中序線索化右子樹 */ /endif如何寫出非遞如何寫出非遞歸的中序線索歸的中序線索程序?程序?2.中序線索二叉樹的遍歷算法中序線索二叉樹的遍歷算法 (不用棧)void InOrderTh ( ThreadTree t) /*對(duì)中序線索二叉樹進(jìn)行中序遍歷*/ ThreadTree p; if (t) p=t; while (p-ltag=0) p=p-lchild; /*找最左下的結(jié)點(diǎn),即中序遍歷的第一個(gè)結(jié)點(diǎn)*/ while (p) / * 訪問當(dāng)前結(jié)點(diǎn)并找出當(dāng)前結(jié)點(diǎn)的
26、中序后繼 */ visite(p-data); /*訪問當(dāng)前結(jié)點(diǎn)*/ p= InPostNode (p); /* 在中序線索二叉樹上尋找結(jié)點(diǎn)p的中序后 繼結(jié)點(diǎn) */ 如何實(shí)現(xiàn)如何實(shí)現(xiàn)Inpostnode?3. 中序線索下求前驅(qū)和后繼中序線索下求前驅(qū)和后繼結(jié)點(diǎn)的左標(biāo)志為1,那么其左指針域所指向的結(jié)點(diǎn)便是它的前驅(qū)結(jié)點(diǎn)如果該結(jié)點(diǎn)的左標(biāo)志為0,表明該結(jié)點(diǎn)有左孩子,它的前驅(qū)結(jié)點(diǎn)是以該結(jié)點(diǎn)的左孩子為根結(jié)點(diǎn)的子樹的最右結(jié)點(diǎn),即沿著其左子樹的右指針鏈向下查找,當(dāng)某結(jié)點(diǎn)的右標(biāo)志為1時(shí),就是所要找的前驅(qū)結(jié)點(diǎn)求求前前驅(qū)驅(qū)(1)若ltag=1, 則lchild域直接指向其前驅(qū)(2)若ltag=0, 則結(jié)點(diǎn)的前驅(qū)應(yīng)是其
27、左子樹的右鏈尾(rtag=1)的結(jié)點(diǎn)示例:示例:在中序線索二叉樹中找結(jié)點(diǎn)前驅(qū)ABCDEFGH C000111111 A B D FT E G01000 H11preA-ltag=0?例:求A結(jié)點(diǎn)的前驅(qū)pre-rtag=0?pre-rtag=0?pre-rtag=0?中序線索中找前驅(qū)算法ThreadTree InPreNode(ThreadTree p)/*在中序線索二叉樹上尋找結(jié)點(diǎn)p的中序前驅(qū)結(jié)點(diǎn) ,假設(shè)p非空*/ ThreadTree pre; pre =p-lchild; if (p-ltag=1) return pre; while (pre -rtag=0) pre = pre -rc
28、hild; return(pre); ?中序線索下的后繼中序線索下的后繼n如結(jié)點(diǎn)的右標(biāo)志為1,那么其右指針域所指向的結(jié)點(diǎn)便是它的后繼結(jié)點(diǎn)n如果該結(jié)點(diǎn)的右標(biāo)志為0,表明該結(jié)點(diǎn)有右孩子,它的后繼結(jié)點(diǎn)是以該結(jié)點(diǎn)的右孩子為根結(jié)點(diǎn)的子樹的最左結(jié)點(diǎn),即沿著其右子樹的左指針鏈到達(dá)某結(jié)點(diǎn)的左標(biāo)志為1時(shí),即是要找的后繼結(jié)點(diǎn)求求后后繼繼示例:在中序線索二叉樹中找結(jié)點(diǎn)后繼(1)若rtag=1, 則rchild域直接指向其后繼(2)若rtag=0, 則結(jié)點(diǎn)的后繼應(yīng)是其右子樹的左鏈尾(ltag=1)的結(jié)點(diǎn)ABCDEFGH C000111111 A B D FT E G01000 H11B-rtag=0?例:求B結(jié)點(diǎn)的后
29、繼postpost-rtag=0?post-rtag=0? 中序線索找后繼算法ThreadTree InPostNode(ThreadTree p)/* 在中序線索二叉樹上尋找結(jié)點(diǎn)p的中序后繼結(jié)點(diǎn),假設(shè)p非空*/ ThreadTree post; post=p-rchild; if (p-rtag=1) return post; while (post-ltag=0) post=post-lchild; return (post);?中序線索二叉樹上查找值為中序線索二叉樹上查找值為x的結(jié)點(diǎn)的結(jié)點(diǎn) 在中序線索二叉樹上查找值為x的結(jié)點(diǎn),實(shí)質(zhì)上就是在線索二叉樹上進(jìn)行遍歷,對(duì)訪問到的結(jié)點(diǎn)進(jìn)行判斷即可:
30、 ThreadTree Search (ThreadTree t,DataType x ) ThreadTree p; p=t; if (p) while (p-ltag=0) p=p-lchild; /*找最左下結(jié)點(diǎn)中序遍歷找最左下結(jié)點(diǎn)中序遍歷 的第一個(gè)結(jié)點(diǎn)的第一個(gè)結(jié)點(diǎn)*/ while (p&p-data!=x) p= InPostNode (p); /* 在中序線索二叉樹上尋找結(jié)點(diǎn)在中序線索二叉樹上尋找結(jié)點(diǎn)p的的 中序后繼結(jié)點(diǎn)中序后繼結(jié)點(diǎn) */ return p;返回返回6.5 6.5 樹和森林樹和森林1.樹的邏輯定義:樹的邏輯定義:是n(n0)個(gè)有限數(shù)據(jù)元素的集合。當(dāng)n0時(shí),稱這
31、棵樹為空樹。在一棵非空樹T中:(1)有一個(gè)特殊的數(shù)據(jù)元素稱為樹的根結(jié)點(diǎn),根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)。(2)若n1,除根結(jié)點(diǎn)之外的其余數(shù)據(jù)元素被分成m(m0)個(gè)互不相交的集合T1,T2,Tm,其中每一個(gè)集合Ti(1im)本身又是一棵樹。樹T1,T2,Tm稱為這個(gè)根結(jié)點(diǎn)的子樹。如何存儲(chǔ)樹?2.樹的存儲(chǔ)結(jié)構(gòu)(1)雙親表示法:存儲(chǔ)每個(gè)節(jié)點(diǎn)的信息,記起雙親節(jié)點(diǎn)的位置,一般用順序存儲(chǔ)結(jié)構(gòu)找雙親易,找子難C實(shí)現(xiàn)用用C類型定義如下:類型定義如下:#define MaxNodeNum 100typedef struct DataType data; int parent; Parentlist;typedef stru
32、ct Parentlist elemMaxNodeNum; int n; /* 樹中當(dāng)前的結(jié)點(diǎn)數(shù)目 */ParentTree;(2)孩子表示法)孩子表示法 類似于圖的鄰接表表示,把節(jié)點(diǎn)的所有孩子用指針串起來C實(shí)現(xiàn)特點(diǎn):找子易,找雙親難特點(diǎn):找子易,找雙親難#define MaxNodeNum 100typedef struct tnode /孩子結(jié)點(diǎn)描述 int elem; struct tnode * next; Tnode;typedef struct bnode /首結(jié)點(diǎn)描述 DataType data; Tnode *firstchild; /指向第一個(gè)孩子Bnode;typedef
33、struct Bnode Tree_AYMaxNodeNum; int n; /* 樹中當(dāng)前的結(jié)點(diǎn)數(shù)目 */ Tree,*PTree;改進(jìn):改進(jìn):或者在每個(gè)節(jié)點(diǎn)增加一個(gè)保存父節(jié)點(diǎn)位置的信息字段增加DataTypeParent_postion(3 3)孩子兄弟表示法)孩子兄弟表示法每個(gè)節(jié)點(diǎn)中存儲(chǔ)自己的第一個(gè)孩子和兄弟的地址(連接所有的兄弟),屬于鏈?zhǔn)酱鎯?chǔ),存儲(chǔ)結(jié)構(gòu)如下:typedef struct tnode DataType data; struct tnode *firstson,*nextbrother;Tnode;3.樹、森林和二叉樹的轉(zhuǎn)換樹、森林和二叉樹的轉(zhuǎn)換 樹和森林的存儲(chǔ)表示復(fù)雜,
34、實(shí)施具體的算法很困難,而二叉樹的算法的比較豐富,牽涉到樹和森林的問題,一般轉(zhuǎn)換成對(duì)應(yīng)的二叉樹,通過二叉樹來解決樹轉(zhuǎn)換成二叉樹樹轉(zhuǎn)換成二叉樹森林轉(zhuǎn)換成二叉樹森林轉(zhuǎn)換成二叉樹二叉樹轉(zhuǎn)換成樹二叉樹轉(zhuǎn)換成樹二叉樹轉(zhuǎn)換成森林二叉樹轉(zhuǎn)換成森林 樹轉(zhuǎn)換成二叉樹樹轉(zhuǎn)換成二叉樹將一棵樹轉(zhuǎn)換為二叉樹的方法是:n樹中所有相鄰兄弟之間加一條連線。n對(duì)樹中的每個(gè)結(jié)點(diǎn),只保留它與第一個(gè)孩子結(jié)點(diǎn)之間的連線,刪去它與其它孩子結(jié)點(diǎn)之間的連線。I.以樹的根結(jié)點(diǎn)為軸心,將整棵樹順時(shí)針轉(zhuǎn)動(dòng)一定的角度,使之結(jié)構(gòu)層次分明轉(zhuǎn)換過程示意圖:轉(zhuǎn)換過程示意圖:4.樹和森林的遍歷樹的遍歷:有先根遍歷和后根遍歷兩種思考:樹的遍歷有沒有中根遍歷?先根
35、遍歷:先根遍歷:訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn)按照從左到右的順序先根遍歷根結(jié)按照從左到右的順序先根遍歷根結(jié)點(diǎn)的每一棵子樹點(diǎn)的每一棵子樹后根遍歷:后根遍歷:按照從左到右的順序后根遍歷根結(jié)按照從左到右的順序后根遍歷根結(jié)點(diǎn)的每一棵子樹點(diǎn)的每一棵子樹訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn)遍歷的結(jié)果先根遍歷結(jié)果:A B E F I Gl先根遍歷:先訪問樹的根結(jié)點(diǎn),然后依次先根遍歷根 的每棵子樹DABDEFGIl后根遍歷:先依次后根遍歷每棵子樹,然后訪問根結(jié)點(diǎn)ABDEFGI后根遍歷:E I F GB D AABCDEFGHIJKLMNO先根遍歷:后根遍歷:ABE F I GCDHJ KL NOME I F G B C J K N O
36、 L M H D AABCDEFGHIJKLMNO例樹:對(duì)應(yīng)二叉樹:先序遍歷:ABE F I GCDHJ KL NOM中序遍歷:E I F G B C J K N O L M H D A樹的先根遍歷與對(duì)應(yīng)二叉樹的先序遍歷結(jié)果相同!樹的后根遍歷與對(duì)應(yīng)二叉樹的中序遍歷結(jié)果相同!6.6 哈夫曼樹1.問題的提出:在通信系統(tǒng)中,要發(fā)送由A,B,C,D四個(gè)字符組成的信息,A出現(xiàn)的概率為0.5,B出現(xiàn)的概率為0.25,C出現(xiàn)的概率為0.1,D出現(xiàn)的概率為0.15。如何對(duì)A、B、C、D 四個(gè)字符進(jìn)行編碼,能使總的編碼長度最短?思路另一種編碼方案另一種編碼方案類似38譯碼器第二種編碼方案優(yōu)于第一種編碼方案第二種
37、編碼方案優(yōu)于第一種編碼方案是否有規(guī)律可循?2.與哈夫曼樹相關(guān)的一些概念1) 路徑 從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支之間的分支構(gòu)成兩個(gè)結(jié)點(diǎn)之間的路徑。 2) 路徑長度 路徑上的分支數(shù)目分支數(shù)目。3) 樹的路徑長度 根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)的路徑長度之和。4) 樹的帶權(quán)路徑長度 樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和。記作記作: 其中,wi是第i個(gè)葉子結(jié)點(diǎn)的權(quán)值,li為從根到第i個(gè)葉子結(jié)點(diǎn)的路徑長度,m為樹的葉子結(jié)點(diǎn)的個(gè)數(shù) 1W P Lmiiiw l3.3.哈夫曼樹的定義哈夫曼樹的定義 最優(yōu)二叉樹 設(shè)有m個(gè)權(quán)值w1,w2,wm,構(gòu)造一棵有m個(gè)葉子結(jié)點(diǎn)的二叉樹,第i個(gè)葉子結(jié)點(diǎn)的權(quán)值為wi,則帶權(quán)路徑長度
38、WPL最小的二叉樹被稱作最最優(yōu)二叉樹優(yōu)二叉樹,這種最優(yōu)二叉樹也稱之為哈夫曼樹哈夫曼樹哈夫曼樹舉例權(quán)值的計(jì)算:b是哈夫曼樹4.4.建立哈夫曼樹的算法建立哈夫曼樹的算法(1) 根據(jù)給定的m個(gè)權(quán)值w1,w2,,wm,構(gòu)成m棵二叉樹的集合T=T1,T2,Tm,其中每個(gè)Ti只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn),其左右子樹均空。 (2) 從T中選兩棵根結(jié)點(diǎn)的權(quán)值最小的二叉樹,不妨設(shè)為Ti、Tj并作為左右子樹構(gòu)成一棵新的二叉樹Tk,并且置新二叉樹的根值為其左右子樹的根結(jié)點(diǎn)的權(quán)值之和。(3) 將新二叉樹Tk并入到T中,同時(shí)從T中刪除Ti、Tj。(4) 重復(fù)(2)、(3),直到T中只有一棵樹為止。這棵樹便是哈夫曼樹。 構(gòu)
39、造過程:假設(shè)有一組權(quán)值5,29,7,8,14,23,3,11,下面我們將利用這組權(quán)值演示構(gòu)造哈夫曼樹的過程。 第一步:以這8個(gè)權(quán)值作為根結(jié)點(diǎn)的權(quán)值構(gòu)造具有8棵樹的森林5 29 7 8 14 23 3 11第二步:從中選擇兩個(gè)根的權(quán)值最小的樹第二步:從中選擇兩個(gè)根的權(quán)值最小的樹3,5作為左右子樹構(gòu)造一棵新樹,并將這兩棵樹從作為左右子樹構(gòu)造一棵新樹,并將這兩棵樹從森林中刪除,并將新樹添加進(jìn)去森林中刪除,并將新樹添加進(jìn)去3 529 7 8 14 23 118第三步:重復(fù)第二步過程,直到森林中只有一棵樹為止選擇7,829 14 23 117 8153 5829 14 23 7 81583 51911選
40、擇8,11 選擇14,15 選擇19,2329 157 829143 5 842231911選擇29,297 815582929143 5842231911選擇42,581007 815582929143 5842231911這就是以上述8個(gè)權(quán)值為葉子結(jié)點(diǎn)權(quán)值構(gòu)成的哈夫曼樹,它的帶權(quán)的路徑長度為:WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=2715.哈夫曼樹的特點(diǎn)特點(diǎn)特點(diǎn)1:若一棵二叉樹是哈夫曼樹,則該二叉樹不存在度為1的結(jié)點(diǎn)。特點(diǎn)特點(diǎn)2:若給定權(quán)值的葉子結(jié)點(diǎn)個(gè)數(shù)為n,則所構(gòu)造的哈夫曼樹中的結(jié)點(diǎn)數(shù)是2n-1。 說明:由特點(diǎn)1和二叉樹的性質(zhì)3可得特點(diǎn)特點(diǎn)3:任一棵哈夫曼樹的帶權(quán)路徑長度等于所有分支結(jié)點(diǎn)值的累加和。思考為什么?思考為什么?可以證明么,可以證明么,如何證明?如何證明?樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和6. 哈夫曼編碼 前綴編碼(何為前綴編碼?)方式,能實(shí)現(xiàn)一組指定出現(xiàn)頻率字符編碼長度之和最小A:0T:10C:110S:111前綴編碼得前綴編碼得到的字符編到的字符編碼碼返回返回 #define N 20 /* 葉子結(jié)點(diǎn)數(shù)葉子結(jié)點(diǎn)數(shù) */ typedef int DataType ; typedef struct char ch; DataType weight; /*假設(shè)葉子
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- Module 1 Unit 2 He's cool(教學(xué)設(shè)計(jì))-2023-2024學(xué)年外研版(三起)英語四年級(jí)下冊(cè)
- 設(shè)備供貨裝合同范本
- 1秋天 第一課時(shí) 教學(xué)設(shè)計(jì)-2024-2025學(xué)年語文一年級(jí)上冊(cè)統(tǒng)編版(五四制)
- 綠化栽植勞務(wù)合同范本
- 10《我們所了解的環(huán)境污染》(教學(xué)設(shè)計(jì))-部編版道德與法治四年級(jí)上冊(cè)
- Unit 1 My Classroom Part B. Lets talk. Lets play (教學(xué)設(shè)計(jì))-2024-2025學(xué)年人教PEP版英語四年級(jí)上冊(cè)
- 3《學(xué)會(huì)反思》教學(xué)設(shè)計(jì)-2023-2024學(xué)年道德與法治六年級(jí)下冊(cè)統(tǒng)編版
- 外裝合同范本
- 個(gè)人購買瓷磚合同范本
- 2023-2024學(xué)年高二上學(xué)期體育與健康人教版必修第一冊(cè)教學(xué)設(shè)計(jì)
- 科雷氏骨折史密斯氏骨折培訓(xùn)課件
- 衛(wèi)生院基本藥物采購供應(yīng)管理制度
- 抽水蓄能輔助洞室施工方案
- 數(shù)據(jù)結(jié)構(gòu)英文教學(xué)課件:chapter7 Searching
- 護(hù)理核心制度及重點(diǎn)環(huán)節(jié)-PPT課件
- 夾套管現(xiàn)場(chǎng)施工方法
- 部編版語文五年級(jí)下冊(cè)形近字組詞參考
- 第三章走向混沌的道路
- 化探野外工作方法及要求
- 2006年事業(yè)單位工資改革工資標(biāo)準(zhǔn)表及套改表2
- 江蘇省特種設(shè)備安全條例2021
評(píng)論
0/150
提交評(píng)論