數(shù)據(jù)結(jié)構(gòu)789樹課件

1、數(shù)據(jù)結(jié)構(gòu)Data Structure彭宏京南京工業(yè)大學(xué)計(jì)算機(jī)科學(xué)系2019年9月學(xué)時(shí)數(shù)：48(32+16） 學(xué) 分： 3 教 材：嚴(yán)蔚敏等，數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學(xué)出版社，2019年4月 （配題集） 參考書：1 殷人昆等，數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC+描述），清華大學(xué)出版社，2019年7月。￥26 2 殷人昆等，數(shù)據(jù)結(jié)構(gòu)習(xí)題解析，清華大學(xué)出版社，2019年4月。￥263 李春葆，數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析（C語言篇），清華大學(xué)出版社，2019年1月。￥284 丁寶康等，數(shù)據(jù)結(jié)構(gòu)自學(xué)考試指導(dǎo)，清華大學(xué)出版社， 2019年5月。￥23內(nèi) 容 安 排章內(nèi) 容 學(xué)時(shí) 章 內(nèi) 容 學(xué)時(shí) 1緒 論27圖62

2、線性表48動(dòng)態(tài)存儲(chǔ)管理略3棧和隊(duì)列69查找44串（自學(xué)）210內(nèi)部排序45數(shù)組和廣義表（自學(xué)） 411外部排序略6樹和二叉樹 612文件略實(shí)驗(yàn)：課內(nèi)上機(jī)（16規(guī)定內(nèi)容）+課外上機(jī)（24平時(shí)作業(yè)中編程題驗(yàn)證）數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容各種數(shù)據(jù)結(jié)構(gòu)的應(yīng)用1、樹的定義和基本術(shù)語2、二叉樹3、遍歷二叉樹和線索二叉樹4、樹和森林5、樹和等價(jià)問題6、赫夫曼樹及其與樹的應(yīng)用7、回溯法與樹的遍歷8、樹的計(jì)數(shù)目錄第六章 樹和二叉樹 特點(diǎn)：非線性結(jié)構(gòu)，一個(gè)直接前驅(qū)，但可能有多個(gè)直接后繼。 （一對(duì)多或1:n） 1、樹的定義和基本術(shù)語（1）. 樹的定義注：樹的定義具有遞歸性，即“樹中還有樹”。由一個(gè)或多個(gè)(n0)結(jié)點(diǎn)組成的有

3、限集合T，有且僅有一個(gè)結(jié)點(diǎn)稱為根（root），當(dāng)n1時(shí)，其余的結(jié)點(diǎn)分為m(m0)個(gè)互不相交的有限集合T1,T2，Tm。每個(gè)集合本身又是棵樹，被稱作這個(gè)根的子樹 。（1）. 樹的定義（2）.若干術(shù)語（3）.邏輯結(jié)構(gòu)（4）.存儲(chǔ)結(jié)構(gòu)（5）.樹的運(yùn)算樹的表示法主要有5種：圖形表示法嵌套集合表示法廣義表表示法凹入表示法左孩子右兄弟表示法1、樹的定義和基本術(shù)語自學(xué)圖形表示法：教師學(xué)生其他人員2019級(jí)2019級(jí)2019級(jí)2019級(jí)南工大信息學(xué)院計(jì)算機(jī)系電子系通信系葉子根子樹左孩子右兄弟表示法ABCDEFGHIJKLM數(shù)據(jù)左孩子 右兄弟（2）. 若干術(shù)語即上層的那個(gè)結(jié)點(diǎn)(直接前驅(qū))即下層結(jié)點(diǎn)的子樹的根(直

4、接后繼)同一雙親下的同層結(jié)點(diǎn)（孩子之間互稱兄弟）即雙親位于同一層的結(jié)點(diǎn)（但并非同一雙親）即從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)即以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)ABCGEIDHFJMLK 根 葉子 森林有序樹無序樹即根結(jié)點(diǎn)(沒有前驅(qū))即終端結(jié)點(diǎn)(沒有后繼)指m棵不相交的樹的集合(例如刪除A后的子樹個(gè)數(shù))雙親孩子兄弟堂兄弟祖先子孫結(jié)點(diǎn)各子樹從左至右有序，不能互換（左為第一）結(jié)點(diǎn)各子樹可互換位置。（2）. 若干術(shù)語（續(xù)）即樹的數(shù)據(jù)元素結(jié)點(diǎn)掛接的子樹數(shù)結(jié)點(diǎn)結(jié)點(diǎn)的度結(jié)點(diǎn)的層次終端結(jié)點(diǎn)分支結(jié)點(diǎn)樹的度樹的深度(或高度)ABCGEIDHFJMLK從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）即度為0的結(jié)點(diǎn)，即葉子即度不為0的

5、結(jié)點(diǎn)（也稱為內(nèi)部結(jié)點(diǎn)）所有結(jié)點(diǎn)度中的最大值（Max各結(jié)點(diǎn)的度）指所有結(jié)點(diǎn)中最大的層數(shù)（Max各結(jié)點(diǎn)的層次）問：右上圖中的結(jié)點(diǎn)數(shù) ；樹的度 ；樹的深度1334（有幾個(gè)直接后繼就是幾度，亦稱“次數(shù)”）ABCDEFGHIJKLM結(jié)點(diǎn)A的度：3結(jié)點(diǎn)B的度：2結(jié)點(diǎn)M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點(diǎn)A的孩子：B，C，D結(jié)點(diǎn)B的孩子：E，F(xiàn)結(jié)點(diǎn)I的雙親：D結(jié)點(diǎn)L的雙親：E結(jié)點(diǎn)B，C，D為兄弟結(jié)點(diǎn)K，L為兄弟樹的度：3結(jié)點(diǎn)A的層次：1結(jié)點(diǎn)M的層次：4樹的深度：4結(jié)點(diǎn)F，G為堂兄弟結(jié)點(diǎn)M的祖先是A、D、H（3）. 樹的邏輯結(jié)構(gòu) 一對(duì)多（1:n），有多個(gè)直接后繼（如家譜樹、目錄樹等等），但只有一個(gè)根結(jié)

6、點(diǎn)，且子樹之間互不相交。 （4）. 樹的存儲(chǔ)結(jié)構(gòu) 討論1：樹是非線性結(jié)構(gòu)，該怎樣存儲(chǔ)？特點(diǎn)：仍然有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)等方式。 理論上，你愛怎樣存儲(chǔ)就怎樣存儲(chǔ)（比如隨手扔進(jìn)存儲(chǔ)器，就像有些不愛收拾的同學(xué)對(duì)待自己的物品一樣）！但如果這樣的話，你要取出來就很要命了（相信大家均有過找東西的煩惱）。學(xué)數(shù)據(jù)結(jié)構(gòu)就是讓你/計(jì)算機(jī)變得更有秩序和高效！原則是：物理存儲(chǔ)要反映邏輯結(jié)構(gòu)（邏輯關(guān)系必須在存儲(chǔ)實(shí)現(xiàn)時(shí)得到反映）!注：這兩種存儲(chǔ)方式對(duì)于線性結(jié)構(gòu)來說很直觀也很自然。那么，這兩種存儲(chǔ)方式如何反映1:n的樹型關(guān)系呢？（想一想？）二叉樹討論3：樹的鏈?zhǔn)酱鎯?chǔ)方案應(yīng)該怎樣制定？復(fù)原困難討論2：樹的順序存儲(chǔ)方案應(yīng)該怎樣制

7、定？可用多重鏈表：一個(gè)前趨指針，n個(gè)后繼指針。 細(xì)節(jié)問題： 樹中結(jié)點(diǎn)的結(jié)構(gòu)類型樣式該如何設(shè)計(jì)？ 即應(yīng)該設(shè)計(jì)成“等長(zhǎng)”還是“不等長(zhǎng)”？ 缺點(diǎn)： 等長(zhǎng)結(jié)構(gòu)太浪費(fèi)（每個(gè)結(jié)點(diǎn)的度不一定相同）； 不等長(zhǎng)結(jié)構(gòu)太復(fù)雜（要定義好多種結(jié)構(gòu)類型）。先研究最簡(jiǎn)單、最有規(guī)律的樹，然后設(shè)法把一般的樹轉(zhuǎn)化為簡(jiǎn)單樹?？梢?guī)定為：從上至下、從左至右將樹的結(jié)點(diǎn)依次存入內(nèi)存。重大缺陷：解決思路：不能唯一復(fù)原就沒有實(shí)用價(jià)值！其實(shí)你也可以來一個(gè)規(guī)定，但你的規(guī)定有用嗎？如果有，那么恭喜你，呵呵?。?）. 樹的運(yùn)算 要明確：1. 普通樹（即多叉樹）若不轉(zhuǎn)化為二叉樹，則運(yùn)算很難實(shí)現(xiàn)。2. 二叉樹的運(yùn)算仍然是插入、刪除、修改、查找、排序等，但

8、這些操作必須建立在對(duì)樹結(jié)點(diǎn)能夠“遍歷”的基礎(chǔ)上！本章重點(diǎn)：二叉樹的表示和實(shí)現(xiàn)遍歷指每個(gè)結(jié)點(diǎn)都被訪問且僅訪問一次，不遺漏不重復(fù)“遍歷”實(shí)現(xiàn)了一種重要思想：非線性結(jié)構(gòu)線性化2、二叉樹為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè) “叉” 的樹？二叉樹的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)；所有樹都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹（可以預(yù)習(xí)6.4節(jié)）。（1）. 二叉樹的定義（2）. 二叉樹的性質(zhì)（3）. 二叉樹的存儲(chǔ)結(jié)構(gòu)例：結(jié)點(diǎn)總數(shù)為 3 時(shí)的所有二叉樹的樹的形狀 2、二叉樹（1）、二叉樹的定義是n（n0）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的分別稱為左子樹和右子樹的二叉樹組成。(即:空或有一個(gè)根，根有左子樹、右子樹；而左右子

9、樹本身又是二叉樹。）邏輯結(jié)構(gòu)： 一對(duì)二（1:2） 基本特征: 每個(gè)結(jié)點(diǎn)最多只有兩棵子樹 （不存在度大于2的結(jié)點(diǎn)）； 左子樹和右子樹次序不能顛倒。BCDEFL 例：二叉樹 2、二叉樹（2）、二叉樹的性質(zhì)：證：k = 1 時(shí)成立，設(shè) k = i-1 時(shí)成立 則當(dāng) k = i 時(shí)在二叉樹的第 i 層上至多有 2 i-1-1 * 2 = 2 i-1 個(gè)結(jié)點(diǎn)BCDEFLA1層：結(jié)點(diǎn)個(gè)數(shù) 21-1=20 個(gè)2層：結(jié)點(diǎn)個(gè)數(shù) 22-1=21 個(gè)3層：結(jié)點(diǎn)個(gè)數(shù) 23-1=22 個(gè)性質(zhì)1：在二叉樹的第 i 層上至多有 2 i-1個(gè)結(jié)點(diǎn)討論1：第i層的結(jié)點(diǎn)數(shù)最多是多少？ 2i-1個(gè)性質(zhì)2：深度為 K 的二叉樹至多有

10、2 k- 1 個(gè)結(jié)點(diǎn)證：利用性質(zhì) 1 ，將第 1 層至第 k 層的最多的結(jié)點(diǎn)數(shù)進(jìn)行相加：1 + 2 + 22 + + 2k-2 + 2k-1 = 2k - 1性質(zhì)3：二叉樹的葉子結(jié)點(diǎn)數(shù) n0 等于度為 2 的結(jié)點(diǎn)數(shù)n2 + 1 （即n0=n2+1） 證： 二叉樹中全部結(jié)點(diǎn)數(shù)nn0+n1+n2(葉子數(shù)1度結(jié)點(diǎn)數(shù)2度結(jié)點(diǎn)數(shù))又二叉樹中全部結(jié)點(diǎn)數(shù)nB+1 ( 總分支數(shù)根結(jié)點(diǎn) ) （除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)必有一個(gè)直接前趨，即一個(gè)分支）而 總分支數(shù)B= n1+2n2 (1度結(jié)點(diǎn)必有1個(gè)直接后繼，2度結(jié)點(diǎn)必有2個(gè))三式聯(lián)立可得： n0+n1+n2= n1+2n2 +1, 即n0=n2+1討論2：深度為k的二

11、叉樹，最多有多少個(gè)結(jié)點(diǎn)？ 2k-1個(gè)討論3：二叉樹的葉子數(shù)和度為2的結(jié)點(diǎn)數(shù)之間有關(guān)系嗎？2. 深度為的二叉樹的結(jié)點(diǎn)總數(shù)，最多為 個(gè)。 )k-1 ) log2k ) k )k1. 樹中各結(jié)點(diǎn)的度的最大值稱為樹的 。 ) 高度 ) 層次 ) 深度 ) 度DCC3. 深度為9的二叉樹中至少有 個(gè)結(jié)點(diǎn)。 )9 )8 ) )91課堂練習(xí)：2、二叉樹BCDEFLAPSQRUBCDEFLAPSQRXUWV滿二叉樹:一棵深度為k 且有2k -1個(gè)結(jié)點(diǎn)的二叉樹。 特點(diǎn)：每層都“充滿”了結(jié)點(diǎn)完全二叉樹:深度為k 的、有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k 的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。性質(zhì)

12、4：具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n1 證：根據(jù)性質(zhì)2，深度為k的二叉樹最多只有2k-1個(gè)結(jié)點(diǎn)，且完全二叉樹的定義是與同深度的滿二叉樹前面編號(hào)相同，即它的總結(jié)點(diǎn)數(shù)n位于k層和k-1層滿二叉樹容量之間，即 2k-1-1n2k-1 或2k-1n2k 三邊同時(shí)取對(duì)數(shù)，于是有：k-1log2n1，則其雙親是i/2 如果2in，則結(jié)點(diǎn)i無左孩子；如果2in，則其左孩子是2i (3) 如果2i+1n，則結(jié)點(diǎn)i無右孩子；如果2i+1n，則其右孩子是2i+1121110987654321為何要研究這兩種特殊形式？因?yàn)橹挥羞@兩種形式可以實(shí)現(xiàn)二叉樹的順序存儲(chǔ)。問題: 設(shè)一棵完全二叉樹具有1000個(gè)

13、結(jié)點(diǎn)，則它有 個(gè)葉子結(jié)點(diǎn)，有 個(gè)度為2的結(jié)點(diǎn)，有 個(gè)結(jié)點(diǎn)只有非空左子樹，有 個(gè)結(jié)點(diǎn)只有非空右子樹。48948810由于最后一層葉子數(shù)為489個(gè)，是奇數(shù)，說明有1個(gè)結(jié)點(diǎn)只有非空左子樹；而完全二叉樹中不可能出現(xiàn)非空右子樹(0個(gè))。解：易求出總層數(shù)和末層葉子數(shù)?？倢訑?shù)k=log2n1 =10;且前9層總結(jié)點(diǎn)數(shù)為29-1=511 (完全二叉樹的前k-1層肯定是滿的)所以末層葉子數(shù)為1000-511=489個(gè)。請(qǐng)注意葉子結(jié)點(diǎn)總數(shù)末層葉子數(shù)！還應(yīng)當(dāng)加上第k-1層（靠右邊）的0度結(jié)點(diǎn)個(gè)數(shù)。分析：末層的489個(gè)葉子只占據(jù)了上層的245個(gè)結(jié)點(diǎn)（489/2 )上層（k=9)右邊的0度結(jié)點(diǎn)數(shù)還有29-1-245=1

14、1個(gè)！ 第i層上的滿結(jié)點(diǎn)數(shù)為2i-1所以，全部葉子數(shù)489(末層)11(k-1層)=500個(gè)。 度為2的結(jié)點(diǎn)葉子總數(shù)1=499個(gè)。2、二叉樹（3）、二叉樹的存儲(chǔ)結(jié)構(gòu)： 一、順序存儲(chǔ)結(jié)構(gòu)按二叉樹的結(jié)點(diǎn)“自上而下、從左至右”編號(hào)，用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)。ABCDEFGHI123456789ABCGEIDHF問：順序存儲(chǔ)后能否復(fù)原成唯一對(duì)應(yīng)的二叉樹形狀？答：若是完全/滿二叉樹則可以做到唯一復(fù)原。 而且有規(guī)律：下標(biāo)值為i的雙親，其左孩子的下標(biāo)值必為2i，其右孩子的下標(biāo)值必為2i1（即性質(zhì)5） 例如，對(duì)應(yīng)2的兩個(gè)孩子必為4和5,即B的左孩子必是D,右孩子必為E。T0一般不用討論：不是完全二叉樹怎么辦？

15、答：一律補(bǔ)全為完全二叉樹！方法很簡(jiǎn)單，將各層空缺處統(tǒng)統(tǒng)補(bǔ)上“虛結(jié)點(diǎn)”，其內(nèi)容為空。ABCDE123456789.16ABECD缺點(diǎn)：浪費(fèi)空間；插入、刪除不便 2、二叉樹(3)、二叉樹的存儲(chǔ)結(jié)構(gòu)：二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 僅定義結(jié)點(diǎn)的類型即可。ABCDEFGHILtypedef struct BiTNode TELemType data; struct BiTNode * lchild; struct BiTNode * rchild; BitTNode, * BiTree;BiTree p; data lchild rchild標(biāo)準(zhǔn)形式：（二叉鏈表）data lchild rchild parentt

16、ypedef struct BiTNode TELemType data; struct BiTNode * lchild; struct BiTNode * rchild; struct BiTNode * parent; BitTNode, * BiTree;BiTree p; 廣義標(biāo)準(zhǔn)形式：（三叉鏈表）如果需要倒查某結(jié)點(diǎn)的雙親，可以再增加一個(gè)雙親域（直接前趨）指針，將二叉鏈表變成三叉鏈表。用二叉鏈表即可方便表示。一般從根結(jié)點(diǎn)開始存儲(chǔ)。（相應(yīng)地，訪問樹中結(jié)點(diǎn)時(shí)也只能從根開始）例： ABECDABDCEdatalchildrchilddatalchildrchildADEBCFrootlch

17、ild data rchild結(jié)點(diǎn)結(jié)構(gòu): 二叉鏈表3、遍歷二叉樹和線索二叉樹一、遍歷二叉樹遍歷定義遍歷用途遍歷方法指按某條搜索路線遍訪每個(gè)結(jié)點(diǎn)且不重復(fù)（又稱周游）。它是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運(yùn)算的前提，是二叉樹一切運(yùn)算的基礎(chǔ)和核心。對(duì)每個(gè)結(jié)點(diǎn)的查看通常都是“先左后右” 。3、遍歷二叉樹和線索二叉樹遍歷規(guī)則二叉樹由根、左子樹、右子樹構(gòu)成，定義為D、 L、R以根結(jié)點(diǎn)為參照系注：“先、中、后”的意思是指訪問的結(jié)點(diǎn)D是先于子樹出現(xiàn)還是后于子樹出現(xiàn)。 D、 L、R的組合定義了六種可能的遍歷方案： LDR, LRD, DLR, DRL, RDL, RLD 若限定先左后右，則有三種實(shí)現(xiàn)方案： D

18、LR LDR LRD先序遍歷 中序遍歷 后序遍歷 3、遍歷二叉樹和線索二叉樹例1：先序遍歷的結(jié)果是：中序遍歷的結(jié)果是：后序遍歷的結(jié)果是： A B CD ED B E A CD E B C A口訣：DLR先序遍歷，即先根再左再右LDR中序遍歷，即先左再根再右LRD后序遍歷，即先左再右再根ABDEC+*A*/EDCB先序遍歷結(jié)果+ * * / A B C D E前綴表示法中序遍歷結(jié)果A / B * C * D + E中綴表示法后序遍歷結(jié)果A B / C * D * E +后綴表示法層次遍歷結(jié)果+ * E * D / C A B例2：用二叉樹表示算術(shù)表達(dá)式中序遍歷算法LDR(node *root)i

19、f(root !=NULL) LDR(root-lchild); printf(“%d”,root-data); LDR(root-rchild); return(0);后序遍歷算法LRD (node *root)if(root !=NULL) LRD(root-lchild); LRD(root-rchild); printf(“%d”,root-data); return(0);結(jié)點(diǎn)數(shù)據(jù)類型自定義typedef struct nodeint data; struct node *lchild,*rchild； node;node *root; 先序遍歷算法DLR( node *root )

20、if (root !=NULL) /非空二叉樹 printf(“%d”,root-data); /訪問DDLR(root-lchild); /遞歸遍歷左子樹DLR(root-rchild); /遞歸遍歷右子樹 return(0); 對(duì)遍歷的分析：1. 從前面的三種遍歷算法可以知道：如果將print語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的訪問路徑是相同的，只是訪問結(jié)點(diǎn)的時(shí)機(jī)不同。從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑上，每個(gè)結(jié)點(diǎn)經(jīng)過3次。AFEDCBG第1次經(jīng)過時(shí)訪問，是先序遍歷第2次經(jīng)過時(shí)訪問，是中序遍歷第3次經(jīng)過時(shí)訪問，是后序遍歷2. 二叉樹遍歷的時(shí)間效率和空間效率時(shí)間效

21、率:O(n) /每個(gè)結(jié)點(diǎn)只訪問一次空間效率:O(n) /棧占用的最大輔助空間精確值：樹深為k的遞歸遍歷需要k+1個(gè)輔助單元3、遍歷二叉樹和線索二叉樹BCDELA(1)、遍歷二叉樹：續(xù)先序的非遞歸實(shí)現(xiàn)：1、根結(jié)點(diǎn)進(jìn)棧2、結(jié)點(diǎn)出棧，被訪問3、結(jié)點(diǎn)的右、左兒子（非空）進(jìn)棧4、反復(fù)執(zhí)行 2、3 ，至?？諡橹?。先序：A、L、B、E、C、De.g:A出棧訪問L出棧訪問B出棧訪問E出棧訪問C出棧訪問D出棧訪問后，棧空結(jié)束A進(jìn)棧C、L進(jìn)棧E、B進(jìn)棧D進(jìn)棧3、遍歷二叉樹和線索二叉樹(1)、遍歷二叉樹：續(xù)中序的非遞歸實(shí)現(xiàn)：1、結(jié)點(diǎn)（初始時(shí)是根結(jié)點(diǎn)）進(jìn)棧，沿左指針查找左兒子。2、若有左兒子，返回第一步。3、若無左兒

22、子，判?？?？空則結(jié)束。非空，棧頂結(jié)點(diǎn)出棧 訪問。轉(zhuǎn)向右子樹，返回1。e.g:BCDELAXW中序：B、L、E、 A、C、W、 X、Dinitstack(s);push(s,t); / t 是根結(jié)點(diǎn)while (!stackempty(s) while (Gettop(s,p) & p ) / 有值且非空時(shí) push(s, p-lchild)； / null 值可能進(jìn)棧 pop (s,p); / 空指針退棧 if (!stackempty(s) / 訪問結(jié)點(diǎn)，向右一步 pop(s, p); visit( p-data); push(s,p-rchild); 反復(fù)執(zhí)行：向左走到盡頭退棧訪問 轉(zhuǎn)向右

23、子樹3、遍歷二叉樹和線索二叉樹(2)、線索二叉樹(自學(xué))為什么采用線索二叉樹：二叉樹中的空指針場(chǎng)多達(dá) n + 1 個(gè)。簡(jiǎn)單證明：設(shè)二叉樹中結(jié)點(diǎn)的總數(shù)為 n，度為 2 的結(jié)點(diǎn)總數(shù)為 n2 ?？罩羔槇?chǎng)用方框代表。增加了方框結(jié)點(diǎn)的二叉樹稱之為擴(kuò)展二叉樹。在該二叉樹之中，原來的 n 個(gè)結(jié)點(diǎn)全部成為度為 2 的結(jié)點(diǎn)，方框結(jié)點(diǎn)成為葉子。根據(jù)二叉樹的性質(zhì) 3 ，原命題得證。e.g: n = 8 的二叉樹BCDELAXWBCDELAXW擴(kuò)展二叉樹怎樣利用這 n + 1 個(gè)空指針場(chǎng)？中序穿線樹后序穿線樹作業(yè)：習(xí)題3本次課小結(jié)1、掌握樹和二叉樹的基本概念，性質(zhì)；2、滿二叉樹和完全二叉樹及其性質(zhì)；3、二叉樹的順序存

24、儲(chǔ)是通過補(bǔ)全為完全二叉樹，依從上到下、從左到右的規(guī)定順序來實(shí)現(xiàn)的；4、二叉樹的鏈?zhǔn)酱鎯?chǔ)和線性表的鏈?zhǔn)酱鎯?chǔ)一樣，是通過指向前驅(qū)和后繼結(jié)點(diǎn)來實(shí)現(xiàn)，二叉鏈表較常用；5、二叉樹的遍歷是其它操作和運(yùn)算的基礎(chǔ)，務(wù)必掌握遍歷二叉樹的遞歸和非遞歸算法；6、下面的“遍歷算法的應(yīng)用舉例”請(qǐng)認(rèn)真消化。4、遍歷算法的應(yīng)用舉例(稍加提示，同學(xué)們課后閱讀)(2)、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)(3)、求二叉樹的深度(后序遍歷)(4)、復(fù)制二叉樹(后序遍歷)(5)、建立二叉樹的存儲(chǔ)結(jié)構(gòu)(1)、查詢二叉樹中某個(gè)結(jié)點(diǎn)1) 在二叉樹不空的前提下,和根結(jié)點(diǎn)的元素進(jìn)行比較,若相等,則找到返回 TRUE;2) 否則在左子樹中進(jìn)行查找,若找

25、到, 則返回 TRUE;3) 否則繼續(xù)在右子樹中進(jìn)行查找,若找到,則返回 TRUE,否則返回 FALSE;(1)、查詢二叉樹中某個(gè)結(jié)點(diǎn)Status Preorder (BiTree T, ElemType x, BiTree &p) /若二叉樹中存在和 x 相同的元素，則p指向該結(jié)點(diǎn)并返回OK, 否則返回 FALSE if (T) if (T-data=x) p = T; return OK, /if else return FALSE;else if (Preorder(T-lchild, x, p) return OK; else return(Preorder(T-rchild, x,

26、p) ;/else(2)、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)算法基本思想:先序(或中序或后序)遍歷二叉樹，在遍歷過程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。由此，需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)，并將算法中“訪問結(jié)點(diǎn)” 的操作改為:若是葉子，則計(jì)數(shù)器增1。void CountLeaf (BiTree T, int& count) if ( T ) if (!T-lchild)& (!T-rchild) count+; / 對(duì)葉子結(jié)點(diǎn)計(jì)數(shù) CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeafint CountLeaf (

27、BiTree T) /返回指針T所指二叉樹中所有葉子結(jié)點(diǎn)個(gè)數(shù) if (!T ) return 0; if (!T-lchild & !T-rchild) return 1; else m = CountLeaf( T-lchild); n = CountLeaf( T-rchild); return (m+n); /else / CountLeaf(3)、求二叉樹的深度(后序遍歷)算法基本思想:首先分析二叉樹的深度和它的左、右子樹深度之間的關(guān)系。 從二叉樹深度的定義可知，二叉樹的深度應(yīng)為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，算法中訪問結(jié)點(diǎn)的操作為:求得左、右子樹深度

28、的最大值，然后加1 。int Depth (BiTree T ) / 返回二叉樹的深度 if (!T) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1+(depthLeftdepthRight?depthLeft:depthRight); return depthval;void Depth(BiTree T , int level, int &dval) if ( T ) if (leveldval) dval = level; Depth( T-lch

29、ild, level+1, dval ); Depth( T-rchild, level+1, dval ); /調(diào)用之前 level 的初值為 1, dval 的初值為 0.(4)、復(fù)制二叉樹(后序遍歷)其基本操作為:生成一個(gè)結(jié)點(diǎn)。根元素NEWT左子樹右子樹根元素T左子樹右子樹左子樹右子樹ABCDEFGHK D C H K G AnewT F B E BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) if (!(T = new BiTNode) exit(1); T- data = item; T- lc

30、hild = lptr; T- rchild = rptr; return T;生成一個(gè)二叉樹的結(jié)點(diǎn)(其數(shù)據(jù)域?yàn)閕tem,左指針域?yàn)閘ptr,右指針域?yàn)閞ptr)BiTNode *CopyTree(BiTNode *T) if (!T) return NULL; if (T-lchild ) newlptr = CopyTree(T-lchild); /復(fù)制左子樹 else newlptr = NULL; if (T-rchild ) newrptr = CopyTree(T-rchild); /復(fù)制右子樹 else newrptr = NULL; newT = GetTreeNode(T-d

31、ata, newlptr, newrptr); return newT; / CopyTree(5)、建立二叉樹的存儲(chǔ)結(jié)構(gòu)用空格字符表示無孩子或指針為空注：要實(shí)現(xiàn)遍歷運(yùn)算，必須先把二叉樹存入電腦內(nèi)怎樣建樹？見教材P131例例：將下面的二叉樹以二叉鏈表形式存入計(jì)算機(jī)內(nèi)。ABGDFCE考慮1：輸入結(jié)點(diǎn)時(shí)怎樣表示“無孩子”？考慮2：以何種遍歷方式來輸入和建樹？將二叉樹按先序遍歷次序輸入：A B C D E G F 以先序遍歷最為合適，讓每個(gè)結(jié)點(diǎn)都能及時(shí)被連接到位。建樹算法：Status CreateBiTree( BiTree &T ) /構(gòu)造二叉樹Tscanf(“%c”,&ch);if(ch=)T

32、=NULL; else if(!(T=( BiTNode*)malloc(sizeof(BiTNode)exit(overflow); T-data=ch; /生成根結(jié)點(diǎn) CreateBiTree(T-lchild); /構(gòu)造左子樹 CreateBiTree(T-rchild); /構(gòu)造右子樹 return OK; /CreateBiTree輸入序列： A B C D E G F 上次課回顧和本次課內(nèi)容提示:本章（樹和二叉樹）第二次授課已經(jīng)弄清和解決二叉樹的存儲(chǔ)，及其重要的遍歷運(yùn)算。請(qǐng)同學(xué)們繼續(xù)：1、設(shè)法理清楚解決二叉樹的存儲(chǔ)問題的基本思路；和線性結(jié)構(gòu)相比，它有什么特點(diǎn)；2、完全二叉樹的特點(diǎn)和

33、性質(zhì)為我們實(shí)現(xiàn)普通二叉樹的順序存儲(chǔ)提供了什么啟示和幫助，該順序存儲(chǔ)有什么缺陷？3、二叉樹的遞歸性定義，使得“遍歷”運(yùn)算很容易實(shí)現(xiàn)；充分理解使用堆棧實(shí)現(xiàn)“遍歷”的非遞歸算法；本次課主要解決1、一般樹的存儲(chǔ)問題和“遍歷”運(yùn)算的實(shí)現(xiàn)（只要掌握了樹轉(zhuǎn)化為二叉樹的方法，那么上述問題就是直接的）；2、重點(diǎn)介紹赫夫曼的構(gòu)造及其應(yīng)用。4、樹和森林1、樹的存儲(chǔ)結(jié)構(gòu)標(biāo)準(zhǔn)形式：樹中的每個(gè)結(jié)點(diǎn)除有數(shù)據(jù)場(chǎng)之外，還有 K 個(gè)指針場(chǎng)；其中 K 為樹的度數(shù)。1、數(shù)據(jù)場(chǎng)第一個(gè)兒子結(jié)點(diǎn)的地址第二個(gè)兒子結(jié)點(diǎn)的地址第 K 個(gè)兒子結(jié)點(diǎn)的地址父親結(jié)點(diǎn)的地址廣義標(biāo)準(zhǔn)形式：在標(biāo)準(zhǔn)形式的基礎(chǔ)上，再增加指向父親結(jié)點(diǎn)的指針場(chǎng)。 E.g: 度數(shù) K

34、 3 的樹ABCDEFGHILA 1 2 3 -1B 9 4 -1 0C 5 -1 -1 0D 6 7 -1 0E -1 -1 -1 1F -1 -1 -1 2G 8 -1 -1 3H -1 -1 -1 3I -1 -1 -1 6P -1 -1 -1 -1 0123456789-1 表示空缺點(diǎn)：空指針場(chǎng)太多，多達(dá) ( K -1 ) n + 1 個(gè)。改進(jìn)：結(jié)點(diǎn)中設(shè)立度數(shù)場(chǎng)， 指針場(chǎng)依度數(shù)定。但 操作麻煩。 采用左兒子、兄弟表 示法。用數(shù)組表示左圖的樹 4、樹和森林1、樹的存儲(chǔ)結(jié)構(gòu)左兒子、兄弟表示法：樹中的每個(gè)結(jié)點(diǎn)有數(shù)據(jù)場(chǎng)、指向它的第一棵子樹樹根的指針場(chǎng)、指向它的兄弟結(jié)點(diǎn)的指針場(chǎng)。實(shí)質(zhì)上是用二叉樹

35、表示一棵樹。數(shù)據(jù)場(chǎng)第一棵子樹根結(jié)點(diǎn)的地址下一個(gè)親兄弟結(jié)點(diǎn)的地址 E.g: 度數(shù) K 3 的樹ABCDEFGHIL A B C D E F G H L I 4、樹和森林2、樹、森林于二叉樹的轉(zhuǎn)換樹轉(zhuǎn)換成相對(duì)應(yīng)的二叉樹：1、保留每個(gè)結(jié)點(diǎn)的最左面的分支，其余分支都被刪除。2、同一父結(jié)點(diǎn)下面的結(jié)點(diǎn)成為它的左方結(jié)點(diǎn)的兄弟。 E.g: 度數(shù) K 3 的樹ABCDEFGHILABCDEFGHILABCDEFGHIL4、樹和森林2、樹、森林于二叉樹的轉(zhuǎn)換森林轉(zhuǎn)換成相對(duì)應(yīng)的二叉樹：增加一個(gè)虛擬的根結(jié)點(diǎn)，它的兒子為各棵樹的根。那么，就變成了樹轉(zhuǎn)換成二叉樹的問題。 E.g: 3 棵分別以B、 C、D為根的樹BCDE

36、FGHILBCDEFGHILABCDEFGHILA 相應(yīng)的二叉樹4、樹和森林2、樹、森林于二叉樹的轉(zhuǎn)換森林轉(zhuǎn)換成相對(duì)應(yīng)的二叉樹：增加一個(gè)虛擬的根結(jié)點(diǎn)，它的兒子為各棵樹的根。那么，就變成了樹轉(zhuǎn)換成二叉樹的問題。 E.g: 3 棵分別以B、 C、D為根的樹BCDEFGHILBCDEFGHILABCDEFGHIL 相應(yīng)的二叉樹樹與二叉樹轉(zhuǎn)換ACBED樹ABCDE二叉樹 A B C D E A B C D E A B C D E 對(duì)應(yīng)存儲(chǔ)存儲(chǔ)解釋解釋將樹轉(zhuǎn)換成二叉樹加線：在兄弟之間加一連線抹線：對(duì)每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除其與其余孩子之間的關(guān)系旋轉(zhuǎn)：以樹的根結(jié)點(diǎn)為軸心，將整樹順時(shí)針轉(zhuǎn)45ABCDE

37、FGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI樹轉(zhuǎn)換成的二叉樹其右子樹一定為空將二叉樹轉(zhuǎn)換成樹加線：若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都與p的雙親用線連起來抹線：抹掉原二叉樹中雙親與右孩子之間的連線調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹結(jié)構(gòu)ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI森林轉(zhuǎn)換成二叉樹將各棵樹分別轉(zhuǎn)換成二叉樹將每棵樹的根結(jié)點(diǎn)用線相連以第一棵樹根結(jié)點(diǎn)為二叉樹的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)ABCDEFGHIJABCDEFGHIJABCDEFG

38、HIJABCDEFGHIJ二叉樹轉(zhuǎn)換成森林抹線：將二叉樹中根結(jié)點(diǎn)與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹還原：將孤立的二叉樹還原成樹ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ4、樹和森林3、樹、森林的遍歷樹的前序、后序遍歷：1、類似于二叉樹的前序遍歷：NLR；N:根；L：左子樹（第一棵子樹）， R：其余的那些子樹，遍歷方向由第二棵子樹至最后一棵子樹2、類似于二叉樹的后序遍歷：LRN：L：左子樹（第一棵子樹），R：其 余的那些子樹，遍歷方向由第二棵子樹至最后一棵子樹， N:根NBCDEFGHILA T1 T2 T3LR

39、前序：A、B、L、E、C、F、D、G、I、H后序：L、E、B、F、C、I、G、H、D、A4、樹和森林3、樹、森林的遍歷森林的前序、中序遍歷：前序遍歷類似于樹的前序遍歷。增加一個(gè)虛擬的根結(jié)點(diǎn)，它的兒子為各棵樹的根。那么對(duì)這棵樹進(jìn)行前序遍歷，即得到森林的前序序列（不含樹根結(jié)點(diǎn)）后序遍歷類似于樹的后序遍歷。增加一個(gè)虛擬的根結(jié)點(diǎn)，它的兒子為各棵樹的根。那么對(duì)這棵樹進(jìn)行后序遍歷，即得到森林的后序序列（去掉樹根結(jié)點(diǎn)） 注意：本書稱之為中序遍歷, 如稱之為后序遍歷更合理。前序：B、L、E、C、F、D、G、I、H中序：L、E、B、F、C、I、G、H、DBCDEFGHILABCDEFGHIL4、樹和森林3、樹、

40、森林的遍歷樹的前序、后序遍歷序列和相應(yīng)的二叉樹的前序、中序遍歷序列一一對(duì)應(yīng)：前序序列和對(duì)應(yīng)的二叉樹的前序序列完全一致。E、G：左圖的樹的根 A，及它的兒子結(jié)點(diǎn) B、C、D 在樹的 的前序序列和相應(yīng)的二叉樹中前序序列中的序號(hào)。 根 A: 11 結(jié)點(diǎn) B： 22 結(jié)點(diǎn) C： 55 結(jié)點(diǎn) D： 77BCDEFGHILAABCDEFGHIL以 C 為例：在樹中： 序號(hào) 根節(jié)點(diǎn)數(shù) 第一棵子樹的結(jié)點(diǎn)數(shù) 1 5在二叉樹中： 序號(hào) 根節(jié)點(diǎn)數(shù) 左兒子數(shù)左兒子子樹結(jié)點(diǎn)數(shù) 1 54、樹和森林3、樹、森林的遍歷樹的前序、后序遍歷序列和相應(yīng)的二叉樹的前序、中序遍歷序列一一對(duì)應(yīng)：后序序列和對(duì)應(yīng)的二叉樹的中序序列完全一致。

41、E、G：左圖的樹的根 A，及它的兒子結(jié)點(diǎn) B、C、D 在樹的 的后序序列和相應(yīng)的二叉樹的中序序列中的序號(hào)。 根 A: 1010 結(jié)點(diǎn) B： 33 結(jié)點(diǎn) C： 55 結(jié)點(diǎn) D： 99BCDEFGHILAABCDEFGHIL后序：L、E、B、F、C、I、G、H、D、A以 C 為例：在樹中： 序號(hào) 第一棵子樹的結(jié)點(diǎn)數(shù) C 的子樹的結(jié)點(diǎn)數(shù) 1 5在二叉樹中： 序號(hào) B 的左子樹的結(jié)點(diǎn)數(shù) B 的結(jié)點(diǎn)數(shù) C 的左子樹結(jié)點(diǎn)數(shù) 1 5中序：L、E、B、F、C、I、G、H、D、A4、樹和森林3、樹、森林的遍歷森林的前序、中序（當(dāng)作后序更好理解）和相應(yīng)的二叉樹的前序、中序遍歷序列一一對(duì)應(yīng) E.g: 3 棵分別以B

42、、 C、D為根的樹BCDEFGHILBCDEFGHILABCDEFGHILA 相應(yīng)的二叉樹6、赫夫曼樹及其應(yīng)用1、最優(yōu)二叉樹（赫夫曼樹） 路徑長(zhǎng)度：結(jié)點(diǎn)之間的樹枝的總數(shù)樹的路徑長(zhǎng)度：從根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和樹的帶權(quán)路徑長(zhǎng)度：葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。設(shè)有 n 片葉子，它們的權(quán)值分別 為 w1、w2、.wn， 相應(yīng)的路徑長(zhǎng)度分別為 L1、L2、.Ln。 則樹的帶權(quán)路徑長(zhǎng)度可記為： nWPL = wklk k=1EGHLLEHGEGHL777524442255WPL=36WPL=46WPL=35最優(yōu)二叉樹或赫夫曼樹：樹的帶權(quán)路徑長(zhǎng)度 WPL 最小的二叉樹。6、赫夫曼樹及其應(yīng)用1、最優(yōu)二叉樹（

43、赫夫曼樹） 赫夫曼算法（產(chǎn)生最優(yōu)二叉樹的算法）的實(shí)現(xiàn)：1、給定一個(gè)具有 n 個(gè)權(quán)值 w1,w2,wn 的結(jié)點(diǎn)的集合 F = T1,T2,Tn 。2、初始時(shí)，設(shè) A F。3、執(zhí)行 i = 1 至 n-1 次循環(huán)，在每次循環(huán)時(shí)，做以下事情：從當(dāng)前集合中選取權(quán)值最小、次最小的兩個(gè)結(jié)點(diǎn)，以 這兩個(gè)結(jié)點(diǎn)作為內(nèi)部結(jié) 點(diǎn) bi 的左右兒子，bi 的權(quán)值為其左右兒子權(quán)值之和。在集合中刪除這兩個(gè)權(quán) 值最小、次最小的結(jié)點(diǎn)。這樣，在集合 A 中，結(jié)點(diǎn)個(gè)數(shù)便減少了一個(gè)。 e.g: 權(quán)值（此處為使用概率）分別為 2, 7, 4, 5 的結(jié)點(diǎn)集合 F C, A, S, T 已知。 請(qǐng)利用赫夫曼算法產(chǎn)生最優(yōu)二叉樹。C, 2

44、A, 7S, 4T, 51、A=b1,6A, 7T, 5S, 4C, 22、A=b1,6A, 7S, 4C, 2b2,11 T, 53、A=b3,184、A=6、赫夫曼樹及其應(yīng)用2、赫夫曼編碼 赫夫曼算法用于通信中的字符的編碼。將權(quán)值當(dāng)著使用概率。赫夫曼樹的左分支 標(biāo)記為 1，而右分枝標(biāo)記為 0；這從根到每一個(gè)葉子結(jié)點(diǎn)（字符）的路經(jīng)上標(biāo)記的字符組成的字 符串，即為該字符的赫夫曼編碼。 e.g: 權(quán)值（此處為使用概率）分別為 2, 7, 4, 5 的結(jié)點(diǎn)集合 F C, A, S, T 已知。 請(qǐng)利用赫夫曼算法產(chǎn)生最優(yōu)二叉樹。b1,6A, 7S, 4C, 2b2,11T, 5b3,18111000

45、赫夫曼編碼：A：0T：10C：110S ：111赫夫曼編碼優(yōu)點(diǎn)： 占用二進(jìn)制位少e.g: 左圖發(fā)送長(zhǎng)度為 n 的字符串，等長(zhǎng)表示需 2n 個(gè)比特。因共有四個(gè)字符，表示每個(gè)字符需 二個(gè) 比特。 采用赫夫曼編碼后，總的比特?cái)?shù) 35n/18, 因： A：1*7n /18 T： 2*5n /18 S： 3*4n /18 C：3*2n /18 6、赫夫曼樹及其應(yīng)用2、赫夫曼編碼 赫夫曼算法的實(shí)現(xiàn)：1、建立具有 2n-1 個(gè)單元的數(shù)組，其中 n 個(gè)單元用于保存初始結(jié)點(diǎn)，n-1 個(gè)結(jié)點(diǎn)用于表示內(nèi)部結(jié)點(diǎn)。2、執(zhí)行 n-1 次循環(huán)，每次產(chǎn)生一個(gè)內(nèi)部結(jié)點(diǎn)。權(quán)值最小的兩個(gè)結(jié)點(diǎn)為其左右兒子。3、計(jì)算每個(gè)字符的赫夫曼編碼。b1,6A, 7S, 4C, 2b2,11T, 5b3,18111000數(shù)據(jù)結(jié)構(gòu)： typedef st