第7章 樹和二叉樹

第7章樹和二叉樹本章講解樹和二叉樹。要求理解樹和二叉樹的性質(zhì)、存儲結(jié)構(gòu)；學會創(chuàng)建二叉樹；掌握二叉樹的遍歷；理解線索二叉樹的存儲結(jié)構(gòu)和構(gòu)造；掌握遍歷線索二叉樹；理解哈夫曼樹的概念和構(gòu)造；掌握哈夫曼編碼；了解二叉樹與樹、森林之間的轉(zhuǎn)換；靈活應用樹及二叉樹。你可以成績不好，但不可以中國菜做不好！你看鍋里的蓮藕片，從上到下一層一層還可以再分層，變換出許多層次樣式。這不就像樹的分支分支再分支嗎？若最多有2個分支，則成了二叉樹。提綱7.1樹7.2二叉樹7.3二叉樹遍歷7.4二叉樹構(gòu)造7.5線索二叉樹7.6哈夫曼樹7.7二叉樹與樹、森林之間的轉(zhuǎn)換7.8樹及二叉樹應用7.9樹和二叉樹學習總結(jié)7.1樹樹是一種1對多的非線性結(jié)構(gòu)，每1個節(jié)點可以有零個或多個后繼節(jié)點，但有且只有1個前驅(qū)節(jié)點（根節(jié)點除外），元素節(jié)點之間是1種層次關(guān)系。7.1.1樹基本概念

7.1.1樹基本概念2.術(shù)語7.1.1樹基本概念7.1.1樹基本概念7.1.1樹基本概念3.表示樹的表示是指樹的邏輯結(jié)構(gòu)中元素之間的層次關(guān)系的展示。7.1.1樹基本概念

7.1.1樹基本概念【思考與練習7.1】若1棵3次樹中度為3的節(jié)點為2個，度為2的節(jié)點為1個，度為1的節(jié)點為2個，則該3次樹中總的節(jié)點個數(shù)和度為0的節(jié)點個數(shù)分別是多少？答：設(shè)該3次樹中總節(jié)點個數(shù)、度為0的節(jié)點個數(shù)、度為1的節(jié)點個數(shù)、度為2的節(jié)點個數(shù)和度為3的節(jié)點個數(shù)分別為n、n0、n1、n2和n3。

n=所有節(jié)點的度數(shù)之和+1

=0×n0+1×n1+2×n2+3×n3+1

=1×2+2×1+3×2+1=11又因為n=n0+n1+n2+n3即：n0=n-n1-n2-n3=11-2-1-2=6所以該三次樹中總的節(jié)點個數(shù)和度為0的節(jié)點個數(shù)分別是11和6。7.1.1樹基本概念節(jié)點數(shù)、度數(shù)、分支數(shù)它們之間的常用關(guān)系要理清楚：總度數(shù)=總分支數(shù)總節(jié)點數(shù)=總度數(shù)/總分支數(shù)+1總度數(shù)=0×n0+1×n1+2×n2+3×n3+...+m×nm7.1.2樹存儲結(jié)構(gòu)順序存儲樹的順序存儲分為雙親表示法、孩子表示法和雙親孩子表示法。7.1.2樹存儲結(jié)構(gòu)2.鏈式存儲樹的鏈式存儲分為孩子鏈表示法和孩子兄弟表示法。7.2二叉樹定義二叉樹也稱為二分樹，它是有限的節(jié)點集合，這個集合或者是空，或者由一個根節(jié)點和兩棵互不相交的稱為左子樹和右子樹的二叉樹組成。7.2二叉樹留意：二叉樹的左右子樹不可以互換；二叉樹與度為2的樹是不同的，前者度可以為0即空樹，后者必須有度為2的節(jié)點即至少有3個節(jié)點且不區(qū)分左右子樹。7.2二叉樹

7.2二叉樹【思考與練習7.2】判斷下面的二叉樹，哪些是滿二叉樹？答：只有(4)為滿二叉樹，因為只有(4)滿足滿二叉樹的定義。7.2二叉樹3.完全二叉樹葉子節(jié)點只可能出現(xiàn)在最下面兩層中；對于最大層次中的葉子節(jié)點，都依次排列在該層最左邊的位置上；如果有度為1的節(jié)點，只可能有一個，且該節(jié)點只有左孩子而無右孩子；按層序編號后，一旦出現(xiàn)某節(jié)點（其編號為i）為葉子節(jié)點或只有左孩子，則編號大于i的節(jié)點均為葉子節(jié)點。7.2二叉樹【思考與練習7.3】判斷下面的二叉樹，哪些是完全二叉樹？答：(2)和(4)為完全二叉樹，因為(2)和(4)滿足完全二叉樹的定義。留意：滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。7.2.1二叉樹性質(zhì)

7.2.1二叉樹性質(zhì)

7.2.2二叉樹存儲結(jié)構(gòu)順序存儲7.2.2二叉樹存儲結(jié)構(gòu)2.鏈式存儲7.2.3二叉樹遞歸算法設(shè)計二叉樹本身是一種遞歸結(jié)構(gòu)，因此左右子樹常用于被遞歸調(diào)用。對于二叉樹b，設(shè)f(b)是求解的“大問題”。f(b->lchild)和f(b->rchild)為“小問題”。7.2.3二叉樹遞歸算法設(shè)計

7.2.4二叉樹基本操作二叉鏈節(jié)點類BTNode描述二叉樹類BTree描述7.2.4二叉樹基本操作創(chuàng)建二叉樹【算法7.2】將括號表示法的字符串str創(chuàng)建為以b為根節(jié)點的二叉鏈存儲結(jié)構(gòu)。（代碼見算法7.2）思路:掃描str，處理如下。(1)若ch是單個字符，創(chuàng)建新節(jié)點p，當b為空則p代替b；當棧不為空且flag=true時，p節(jié)點作為棧頂節(jié)點的左孩子節(jié)點；當棧不為空且flag=false時，p節(jié)點作為棧頂節(jié)點的右孩子節(jié)點。(2)若ch=‘(‘：將剛創(chuàng)建的p節(jié)點進棧，置flag=true。(3)若ch=‘)‘：將棧頂節(jié)點出棧。(4)若ch=','：置flag=false。(5)直到掃描完str。7.2.4二叉樹基本操作2.返回二叉鏈括號表示返回二叉鏈括號表示操作是指將1棵以二叉鏈存儲的二叉樹轉(zhuǎn)換為括號表示法?！舅惴?.3】求1棵用二叉鏈存儲的二叉樹的字符串括號表示法。思路:(1)若二叉樹非空，先輸出根節(jié)點t的值；(2)當t有左孩子或右孩子時，輸出“（”；(3)遞歸處理左子樹；(4)當存在右孩子時，輸出“,”；(5)遞歸處理右子樹；(6)最后輸出“）”。代碼見算法7.37.2.4二叉樹基本操作

7.3二叉樹遍歷二叉樹遍歷是指按照一定次序訪問二叉樹中所有節(jié)點，并且每個節(jié)點僅被訪問一次的過程。設(shè)D為根節(jié)點，L、R分別為左、右子樹，我們可以組合為6種遍歷方式：DLR、LDR、LRD、DRL、RDL、RLD），若再規(guī)定先遍歷左子樹，后遍歷右子樹，則對于非空二叉樹，可得到如下3種遍歷方式：DLR、LDR和LRD。7.3.1層次遍歷從上往下、從左往右層層遍歷。7.3.1層次遍歷【算法7.5】設(shè)計1個算法實現(xiàn)二叉樹層次遍歷。思路:(1)若二叉樹非空，先將根節(jié)點b進隊；(2)在隊不空時循環(huán)：從隊列中出隊一個節(jié)點p，訪問它；(3)若它有左孩子節(jié)點，將左孩子節(jié)點進隊；若它有右孩子節(jié)點，將右孩子節(jié)點進隊；(4)重復（2）、（3），直到隊列為空。代碼見算法7.57.3.2先序遍歷①訪問根節(jié)點。②先序遍歷左子樹。③先序遍歷右子樹。7.3.2先序遍歷【思考與練習7.4】寫出下圖二叉樹先序遍歷序列。答：ABDECFG。7.3.2先序遍歷

7.3.3中序遍歷①中序遍歷左子樹。②訪問根節(jié)點。③中序遍歷右子樹。7.3.3中序遍歷【思考與練習7.5】寫出下圖二叉樹中序遍歷序列。答：DBEAFGC。7.3.3中序遍歷

7.3.4后序遍歷后序遍歷左子樹。后序遍歷右子樹。③訪問根節(jié)點。7.3.4后序遍歷【思考與練習7.6】寫出下圖二叉樹后序遍歷序列。答：DEBGFCA。7.3.4后序遍歷

7.3二叉樹遍歷二叉樹的先序、中序、后序遍歷非遞歸算法，了解它們的思路即可。見教材相關(guān)章節(jié)。7.4二叉樹構(gòu)造概念二叉樹的構(gòu)造就是給定某些遍歷序列來唯一地確定該二叉樹。7.4二叉樹構(gòu)造已知先序/中序/后序序列中的1種，能否唯一確定1棵二叉樹呢？No！二叉樹遍歷序列圖7.19(1)的二叉樹圖7.19(2)的二叉樹圖7.19(3)的二叉樹圖7.19(4)的二叉樹圖7.19(5)的二叉樹先序序列ABCABCABCABCABC中序序列BACBCAACBCBAABC后序序列BCACBACBACBACBA7.4二叉樹構(gòu)造2.證明定理7.1：任何n（n≥0）個不同節(jié)點的二又樹，都可由它的先序序列a和中序序列b唯一地確定。7.4二叉樹構(gòu)造定理7.2：任何n（n>0）個不同節(jié)點的二又樹，都可由它的中序序列b和后序序列a唯一地確定。7.4二叉樹構(gòu)造3.舉例已知先序序列為ABDGCEF，中序序列為DGBAECF，則構(gòu)造二叉樹的過程如圖7.22（1）所示。7.4二叉樹構(gòu)造已知中序序列為DGBAECF，后序序列為GDBEFCA，則構(gòu)造二叉樹的過程如圖7.22（2）所示（同先序+中序，略講，可作為課堂練習）7.4二叉樹構(gòu)造4.算法【算法7.12】由二叉樹的先序序列pre和中序序列in構(gòu)造二叉鏈。思路:（1）由先序確定根；（2）找到中序中的根位置，從而確定根的左邊部分為左子樹，右邊部分為右子樹；（3）先序左子樹+中序左子樹=根的左子樹，先序右子樹+中序右子樹=根的右子樹；（4）在根的左右子樹中再執(zhí)行（1）、（2）、（3），直到序列為空。如圖7.23所示。7.4二叉樹構(gòu)造代碼見算法7.12i：先序遍歷開始位置 j：中序遍歷開始位置7.4二叉樹構(gòu)造【算法7.13】由二叉樹的后序序列post和中序序列in構(gòu)造二叉鏈。思路:（1）由后序確定根；（2）找到中序中的根位置，從而確定根的左邊部分為左子樹，右邊部分為右子樹；（3）后序左子樹+中序左子樹=根的左子樹，后序右子樹+中序右子樹=根的右子樹；（4）在根的左右子樹中再執(zhí)行（1）、（2）、（3），直到序列為空。*代碼見算法7.13（類同算法7.12，略講）7.5線索二叉樹

7.5.1線索二叉樹存儲結(jié)構(gòu)7.5.1線索二叉樹存儲結(jié)構(gòu)線索二叉樹節(jié)點類ThNode描述7.5.2構(gòu)造線索二叉樹構(gòu)造線索二叉樹即二叉樹線索化的過程，實質(zhì)上是在遍歷過程中修改空指針的過程。7.5.2構(gòu)造線索二叉樹【算法7.14】構(gòu)造以root為頭節(jié)點的中序線索二叉樹。思路:（1）p指向根節(jié)點b，pre指向root節(jié)點；（2）若p節(jié)點沒有左孩子，置ltag為1，lchild指針為線索，指向其前驅(qū)節(jié)點pre。否則置其ltag為0，lchild指向其左孩子，如圖7.26（1）所示；（3）若pre節(jié)點的rchild為null，置其為線索，指向后繼節(jié)點p，置其rtag為1。否則置其rtag為0，rchild指向其右孩子，如圖7.26（2）所示；（4）將pre指向p，重復（2）、（3），直到線索化完成。代碼見算法7.147.5.3遍歷線索二叉樹2大規(guī)則如下：（1）求中序序列的開始節(jié)點：實際上該節(jié)點就是根節(jié)點的最左下節(jié)點。（2）對于一個節(jié)點p，求其后繼節(jié)點的過程是：①如果p節(jié)點的rchild指針為線索，則rchild所指為其后繼節(jié)點。②否則p節(jié)點的后繼節(jié)點是其右孩子q的最左下節(jié)點post。如圖7.27所示。7.5.3遍歷線索二叉樹【算法7.15】中序線索二叉樹的中序遍歷。思路:見圖7.27所示的2個規(guī)則。代碼見算法7.15

7.6哈夫曼樹哈夫曼樹是一種特殊的二叉樹。7.6哈夫曼樹

7.6.1哈夫曼樹基本概念在n0個帶權(quán)葉子節(jié)點構(gòu)成的所有二叉樹中，帶權(quán)路徑長度WPL最小的二叉樹稱為哈夫曼樹（或最優(yōu)二叉樹）。7.6.1哈夫曼樹基本概念【思考與練習7.7】給定4個葉子節(jié)點，設(shè)其權(quán)值分別為1、3、5、7，可以構(gòu)造出形狀不同的4棵二叉樹，如圖7.28所示，求這4棵二叉樹的WPL，并指出哪些是哈夫曼樹。答：（1）WPL=1×2+3×2+5×2+7×2=32（2）WPL=1×2+3×3+5×3+7×1=33（3）WPL=7×3+5×3+3×2+1×1=43（4）WPL=1×3+3×3+5×2+7×1=29根據(jù)哈夫曼樹定義，（4）為哈夫曼樹。7.6.2哈夫曼樹構(gòu)造概念哈夫曼樹構(gòu)造是指在給定n個帶權(quán)葉子節(jié)點的情況下，構(gòu)造1棵哈夫曼樹。7.6.2哈夫曼樹構(gòu)造規(guī)則：在n個葉子節(jié)點中選擇2個權(quán)值最小的節(jié)點作為左右孩子節(jié)點，它們權(quán)值之和作為其父節(jié)點；再在新生成的父節(jié)點和剩余節(jié)點中選擇2個權(quán)值最小的節(jié)點，重復（1）；重復（2），直到所有節(jié)點選擇完畢，構(gòu)成的二叉樹便是哈夫曼樹。7.6.2哈夫曼樹構(gòu)造舉例：好比我們小時候玩的搭積木，在給定的積木方塊情況下，從下到上搭建起來。7.6.2哈夫曼樹構(gòu)造思考與練習7.8】對于給定帶權(quán)葉子節(jié)點，構(gòu)造的哈夫曼樹是唯一的嗎？答：不是。如圖7.29所示，選擇好2個最小權(quán)值葉子節(jié)點后，它們在構(gòu)造過程中的左右孩子位置是不唯一的，故構(gòu)造的哈夫曼樹不唯一。但是在給定權(quán)值葉子節(jié)點情況下，構(gòu)造的所有哈夫曼樹的WPL值是唯一的。7.6.2哈夫曼樹構(gòu)造哈夫曼樹節(jié)點類HuffmanNode描述7.6.2哈夫曼樹構(gòu)造哈夫曼樹類HuffmanBTree描述7.6.2哈夫曼樹構(gòu)造2.定理7.3：對于具有n0個葉子節(jié)點的哈夫曼樹，共有2n0-1個節(jié)點。

7.6.2哈夫曼樹構(gòu)造3.算法【算法7.16】構(gòu)造哈夫曼樹。思路:由于在構(gòu)造哈夫曼樹的過程中，始終是選擇權(quán)值最小的2個節(jié)點來構(gòu)造，因此可以用到優(yōu)先隊列pq（pq中按照權(quán)值大小排序，權(quán)值越小的越優(yōu)先出隊）。（1）將所有n0個葉子節(jié)點進隊列pq。（2）pq出隊列2個節(jié)點，構(gòu)造它們的父節(jié)點，父節(jié)點的權(quán)值為它們權(quán)值之和。（3）將父節(jié)點入隊列pq。（4）重復（2）、（3），直到2*n0–1個節(jié)點構(gòu)造完畢，哈夫曼樹則構(gòu)造完畢。代碼見算法7.167.6.3哈夫曼編碼概念對于1棵哈夫曼樹，從根節(jié)點到每個葉子節(jié)點所經(jīng)過的左分支對應0和右分支對應1組成的序列便為該節(jié)點對應的哈夫曼編碼。7.6.3哈夫曼編碼留意：哈夫曼編碼是針對哈夫曼樹中的葉子節(jié)點的。哈夫曼編碼的實質(zhì)是使用頻率越高的采用越短的編碼。7.6.3哈夫曼編碼

7.7二叉樹與樹、森林之間的轉(zhuǎn)換樹轉(zhuǎn)換為二叉樹加線：在各兄弟節(jié)點之間加一連線，將其隱含的“兄－弟”關(guān)系以“雙親－右孩子”關(guān)系顯示表示出來。抹線：對任意節(jié)點，除了其最左子樹之外，抹掉該節(jié)點與其他子樹之間的“雙親－孩子”關(guān)系。調(diào)整：以樹的根節(jié)點作為二叉樹的根節(jié)點，將樹根與其最左子樹之間的“雙親－孩子”關(guān)系改為“雙親－左孩子”關(guān)系，且將各節(jié)點按層次排列，形成二叉樹。7.7二叉樹與樹、森林之間的轉(zhuǎn)換2.1棵由樹轉(zhuǎn)換的二叉樹還原為樹加線：在各節(jié)點的雙親與該節(jié)點右鏈上的每個節(jié)點之間加一連線，以“雙親－孩子”關(guān)系顯示