1、1知識回顧知識回顧線性表 一般的線性表 特殊的線性表：棧、隊列線性表的擴展：數組、廣義表特點：有序前趨、后繼2第六章第六章 樹和二叉樹樹和二叉樹樹是以分支關系定義的層次結構。樹是以分支關系定義的層次結構。樹結構在客觀世界廣泛存在樹結構在客觀世界廣泛存在: : 在自然科學，如地理學領域，水系、地貌（等高線）、行政區劃等都具有樹結構關系； 在社會人文領域，人類社會構成、組織機構等也具有樹結構關系。樹型結構：樹型結構：非線性數據結構非線性數據結構4要求要求1. 熟練掌握二叉樹的結構特性。熟練掌握二叉樹的結構特性。2. 熟悉二叉樹的各種存儲結構的特點及適用范圍。熟悉二叉樹的各種存儲結構的特點及適用范圍

2、。3. 掌握各種遍歷策略的遞歸算法，靈活運用遍歷算法實掌握各種遍歷策略的遞歸算法，靈活運用遍歷算法實現二叉樹的其它操作。現二叉樹的其它操作。4. 熟練掌握二叉樹的線索化過程以及在中序線索化樹上熟練掌握二叉樹的線索化過程以及在中序線索化樹上找給定結點的前驅和后繼的方法。找給定結點的前驅和后繼的方法。5. 熟悉樹的各種存儲結構及其特點，掌握樹和森林與二熟悉樹的各種存儲結構及其特點，掌握樹和森林與二叉樹的轉換方法。叉樹的轉換方法。6. 了解最優樹的特性，掌握建立最優樹和哈夫曼編碼的了解最優樹的特性，掌握建立最優樹和哈夫曼編碼的方法。方法。6.1 6.1 樹的定義和基本術語樹的定義和基本術語6.2 6

3、.2 二叉樹二叉樹6.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 6.4 樹和森林樹和森林6.5 6.5 赫夫曼樹與其應用赫夫曼樹與其應用主要內容66.1.1 6.1.1 樹的定義樹的定義樹（樹（tree）是）是n (n0)個結點的有限集。在任意一棵個結點的有限集。在任意一棵非非空樹空樹中：中：（1）有且僅有一個特定的稱為）有且僅有一個特定的稱為根根的結點；的結點；（2）當）當n1時，其余結點可分為時，其余結點可分為m (m0)個互不相交個互不相交的有限集的有限集t1,t2,tm，其中每一個集合本身又是一棵，其中每一個集合本身又是一棵樹，并且稱為根的樹，并且稱為根的子樹子樹

4、。a只有根結點的樹abcdefghijklm有子樹的樹根子樹樹的表示法樹的表示法v 圖形表示法圖形表示法v 嵌套集合表示法嵌套集合表示法v 廣義表表示法廣義表表示法v 凹入表示法凹入表示法v 左孩子右兄弟表示法左孩子右兄弟表示法教師教師學生學生其他人員其他人員20012001級級 20022002級級 20032003級級20042004級級西安石油大學西安石油大學計算機系計算機系電信系電信系自控系自控系葉子葉子根根子樹子樹( a ( b ( e ( k, l ), f ), c ( g ), d ( h ( m ), i, j ) ) 約定：約定：根根作為由子樹森林組成的作為由子樹森林組成的

5、表的名字寫在表的左邊表的名字寫在表的左邊又稱目錄表示法又稱目錄表示法data左孩子左孩子 右兄弟右兄弟多叉樹轉為多叉樹轉為了二叉樹了二叉樹15數據對象數據對象 d：d是具有相同特性的數據元素的集合。是具有相同特性的數據元素的集合。 若若d為空集，則稱為空樹為空集，則稱為空樹 。 否則否則: (1) 在在d中存在唯一的稱為根的數據元素中存在唯一的稱為根的數據元素root；(2) 當當n1時，其余結點可分為時，其余結點可分為m (m0)個互個互 不相交的有限集不相交的有限集t1, t2, , tm，其中每一，其中每一 棵子集本身又是一棵符合本定義的樹，棵子集本身又是一棵符合本定義的樹， 稱為根稱為

6、根root的子樹。的子樹。 數據關系數據關系 r：adt tree16 基本操作：基本操作：查查 找找 類類 插插 入入 類類刪刪 除除 類類17 root(t) / 求樹的根結點求樹的根結點 查找類：查找類：value(t, cur_e) / 求當前結點的元素值求當前結點的元素值 parent(t, cur_e) / 求當前結點的雙親結點求當前結點的雙親結點leftchild(t, cur_e) / 求當前結點的最左孩子求當前結點的最左孩子 rightsibling(t, cur_e) / 求當前結點的右兄弟求當前結點的右兄弟treeempty(t) / 判定樹是否為空樹判定樹是否為空樹 t

7、reedepth(t) / 求樹的深度求樹的深度traversetree( t, visit() ) / 遍歷遍歷18inittree(&t) / 初始化置空樹初始化置空樹 插入類：插入類：createtree(&t, definition) / 按定義構造樹按定義構造樹assign(t, cur_e, value) / 給當前結點賦值給當前結點賦值insertchild(&t, &p, i, c) / 將以將以c為根的樹插入為結點為根的樹插入為結點p的第的第i棵子樹棵子樹19 cleartree(&t) / 將樹清空將樹清空 刪除類：刪除類：destr

8、oytree(&t) / 銷毀樹的結構銷毀樹的結構deletechild(&t, &p, i) / 刪除結點刪除結點p的第的第i棵子樹棵子樹20abcdefghijmkla( b(e, f(k, l), c(g), d(h, i, j(m) )t1t3t2樹根例如例如: :21() 有確定的根；() 樹根和子樹根之間為有向關系。有向樹：有向樹：有序樹：有序樹：子樹之間存在確定的次序關系。無序樹：無序樹：子樹之間不存在確定的次序關系。22對比對比樹型結構樹型結構和和線性結構線性結構的結構特點的結構特點線性結構線性結構樹型結構樹型結構第一個數據元素第一個數據元素 ( (無前

9、驅無前驅) ) 根結點根結點 ( (無前驅無前驅) )最后一個數據元素最后一個數據元素 (無后繼無后繼)多個葉子結點多個葉子結點 ( (無后繼無后繼) )其它數據元素其它數據元素( (一個前驅、一個前驅、 一個后繼一個后繼) )其它數據元素其它數據元素( (一個前驅、一個前驅、 多個后繼多個后繼) )對比對比樹型結構樹型結構和和線性結構線性結構的結構特點的結構特點6.1.2 6.1.2 基本術語基本術語25結點結點: :結點的度結點的度: :樹的度樹的度: :葉子結點葉子結點: :分支結點分支結點: :數據元素+ +若干指向子樹的分支分支的個數樹中所有結點的度的最大值度為零的結點度大于零的結點

10、dhijm26子孫子孫: :以某結點為根的子樹中的任一結點。以某結點為根的子樹中的任一結點。abcdefghijmkl孩子孩子: :結點的子樹的根。結點的子樹的根。雙親雙親: :該結點稱為孩子的雙親。該結點稱為孩子的雙親。兄弟兄弟: :同一個雙親的孩子之間互稱兄弟。同一個雙親的孩子之間互稱兄弟。祖先祖先: :從根到該結點所經分支上的所有結點從根到該結點所經分支上的所有結點27有序樹：有序樹：子樹之間存在確定的次序關系子樹之間存在確定的次序關系無序樹：無序樹：子樹之間不存在確定的次序關系子樹之間不存在確定的次序關系樹的深度：樹的深度：樹中結點的最大層次樹中結點的最大層次堂兄弟堂兄弟: :其雙親在

11、同一層的結點其雙親在同一層的結點結點的層次結點的層次:假設根結點的層次為假設根結點的層次為1，第，第l 層的結點的子樹根結點的層次為層的結點的子樹根結點的層次為l+128a ab bc cd de ef fg gh hi ij jk kl lm m結點結點a的度：的度：3結點結點b的度：的度：2結點結點m的度：的度：0葉子：葉子：k，l，f，g，m，i，j結點結點a的孩子：的孩子：b，c，d結點結點b的孩子：的孩子：e，f結點結點i的雙親：的雙親：d結點結點l的雙親：的雙親：e結點結點b，c，d為兄弟為兄弟結點結點k，l為兄弟為兄弟樹的度：樹的度：3結點結點a的層次：的層次：1結點結點m的層次

12、：的層次：4樹的深度：樹的深度：4結點結點f，g為堂兄弟為堂兄弟29任何一棵非空樹是一個二元組 tree = （root，f）其中：root 被稱為根結點 f 被稱為子樹森林森林：森林：是m（m0）棵互不相交的樹的集合arootbcdefghijmklf先研究最簡單、最有規律的樹，然先研究最簡單、最有規律的樹，然后設法把一般的樹轉化為簡單樹。后設法把一般的樹轉化為簡單樹。解決思路：解決思路： 樹的操作實現比較復雜。樹的操作實現比較復雜。為何要重點研究每結點最多只有兩個為何要重點研究每結點最多只有兩個 “ “叉叉” ” 的樹？的樹？ 二叉樹的結構最簡單，規律性最強；二叉樹的結構最簡單，規律性最強

13、； 可以證明，所有樹都能轉為唯一對應的二叉樹，可以證明，所有樹都能轉為唯一對應的二叉樹，不失一般性。不失一般性。 二叉樹二叉樹:或為空樹，或是由一個或為空樹，或是由一個根根結點結點加上兩棵分別稱為加上兩棵分別稱為左子樹左子樹和和右子右子樹樹的、的、互不相交互不相交的二叉樹組成。的二叉樹組成。abcdefghk根結點根結點左子樹左子樹右子樹右子樹二叉樹的特點二叉樹的特點（1 1）每個結點至多有二棵子樹）每個結點至多有二棵子樹( (即不存在度大于即不存在度大于2 2的結點的結點) )；（2 2）二叉樹的子樹有左、右之）二叉樹的子樹有左、右之分，且其次序不能任意顛倒。分，且其次序不能任意顛倒。二叉樹

14、的五種基本形態：二叉樹的五種基本形態：空樹空樹只含根結點只含根結點lrr右子樹為空樹右子樹為空樹l左子樹為空樹左子樹為空樹左右子左右子樹均不樹均不為空樹為空樹34 二叉樹的主要基本操作二叉樹的主要基本操作：查查 找找 類類插插 入入 類類刪刪 除除 類類35 root(t); value(t, e); parent(t, e); leftchild(t, e); rightchild(t, e); leftsibling(t, e); rightsibling(t, e); bitreeempty(t); bitreedepth(t); preordertraverse(t, visit();

15、 inordertraverse(t, visit(); postordertraverse(t, visit(); levelordertraverse(t, visit();36 initbitree(&t); assign(t, &e, value); createbitree(&t, definition); insertchild(t, p, lr, c);37clearbitree(&t); destroybitree(&t);deletechild(t, p, lr);38二叉樹二叉樹的重要特性的重要特性39 性質性質 1 ： 在二叉樹的第

16、 i 層上至多有2i-1 個結點。 (i1)用歸納法證明用歸納法證明： 歸納基歸納基： 歸納假設：歸納假設： 歸納證明：歸納證明：i = 1 層時，只有一個根結點： 2i-1 = 20 = 1；假設對所有的 j，1 j i，命題成立；二叉樹上每個結點至多有兩棵子樹，則第 i 層的結點數 = 2i-2 2 = 2i-1 。40 性質性質 2 ： 深度為 k 的二叉樹上至多含 2k-1 個結點（k1）。證明：證明： 基于性質1，深度為 k 的二叉樹上的結點數至多為 20+21+ +2k-1 = 2k-1 。41 性質性質 3 ： 對任何一棵二叉樹，若它含有對任何一棵二叉樹，若它含有n0 個葉個葉子

17、結點、子結點、n2 個度為個度為 2 的結點，則必存在的結點，則必存在關系式：關系式：n0 = n2+1。二叉樹中全部結點數二叉樹中全部結點數nn0+n1+n2(葉子數葉子數1度結度結點數點數2度結點數度結點數)二叉樹中全部結點數二叉樹中全部結點數nb+1 ( 總分支數根結點總分支數根結點 ) （除根結點外，每個結點必有一個直接前趨，即一（除根結點外，每個結點必有一個直接前趨，即一個分支）個分支）總分支數總分支數b= n1+2n2 (1度結點必有度結點必有1個直接后繼，個直接后繼，2度結點必有度結點必有2個個)n0+n1+n2= n1+2n2 +1, 即即n0=n2+142兩類兩類特殊特殊的二

18、叉樹：的二叉樹：滿二叉樹滿二叉樹：深度為k且含有2k-1個結點的二叉樹。完全二叉樹完全二叉樹：樹中所含的 n 個結點和滿二叉樹中編號編號為為 1 至至 n 的結點的結點一一對應。123456789 10 11 12 13 14 15abcdefghij43123114589121367101415123114589126710123456712345644完全二叉樹特點：完全二叉樹特點：（1 1）葉子結點只可能在層次最大的兩層上出現）葉子結點只可能在層次最大的兩層上出現; ;（2 2）對任一結點，若其右分支下子孫的最大層次為）對任一結點，若其右分支下子孫的最大層次為i i，則其左分支下子孫的最

19、大層次必為則其左分支下子孫的最大層次必為i i或或i+1i+1。滿二叉樹與完全二叉樹的區別滿二叉樹與完全二叉樹的區別滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前然前k-1k-1層是滿的，但最底層卻允許在右邊缺少連續若干層是滿的，但最底層卻允許在右邊缺少連續若干個結點。滿二叉樹是完全二叉樹的一個特例。個結點。滿二叉樹是完全二叉樹的一個特例。為何要研究這兩種特殊形式？為何要研究這兩種特殊形式？45性質性質 4 ：具有具有 n 個結點的完全二叉樹的深度為個結點的完全二叉樹的深度為 log2n +1 。 x 表示表示= x的最大整數。的最大整數。證明：設

20、完全二叉樹的深度為證明：設完全二叉樹的深度為 k 則根據第二條性質得則根據第二條性質得 2k-1 (第第k層第一個結點的編號）層第一個結點的編號） n 2k（第（第k1層第一個結點的編號）層第一個結點的編號） 即即 k-1 log2 n = (2k-1-1)+1，根據第二條性質得 n 2k -1，因此：2k-1 n 2k 即 k-1 log2 n n，則該結點無左孩子， 否則，編號為 2i 的結點為其左孩子左孩子結點；(3) 若 2i+1n，則該結點無右孩子結點， 否則，編號為2i+1 的結點為其右孩子右孩子結點。123114589126710第第k層上最后一個結點的編號是層上最后一個結點的編

21、號是2k-1,它的右孩它的右孩子是第子是第k+1層上最后一個結點層上最后一個結點,編號是編號是2k+1-1,右右孩子編號是它的雙親結點編號的孩子編號是它的雙親結點編號的(2k-1)*2+1,左左孩子的編號是孩子的編號是(2k-1)*2所以，編號為所以，編號為 i 的結點的左孩子結點編號是的結點的左孩子結點編號是2i，右孩子結點編號是右孩子結點編號是2i+1,雙親結點編號雙親結點編號 i/2 49問問 題題 具有具有n n個結點的非空二叉樹的最小深度個結點的非空二叉樹的最小深度是多少？最大深度是多少？是多少？最大深度是多少？ 答1： 當是滿二叉樹時深度最小。最小深度： log2n +1 當每個節

22、點都只有左（右）子樹時深度最大最大深度： n 50思考題1.具有n個結點的完全二叉樹中有多少個葉子結點？有多少個度為2的結點？2.具有n0個葉子結點的完全二叉樹中共有多少個結點？51二叉樹的存儲結構二叉樹的存儲結構二、二叉樹的鏈式二、二叉樹的鏈式 存儲表示存儲表示一、一、 二叉樹的順序二叉樹的順序 存儲表示存儲表示存儲方式：用一組地址連續的存儲單元依次存儲方式：用一組地址連續的存儲單元依次自上而下、自左至右自上而下、自左至右存儲存儲完全二叉樹完全二叉樹上的結上的結點元素，即將完全二叉樹上編號為點元素，即將完全二叉樹上編號為i的結點元的結點元素存儲在一維數組中下標為素存儲在一維數組中下標為i-1

23、的分量中。的分量中。一、一、 二叉樹的順序存儲結構二叉樹的順序存儲結構/-二叉樹的順序存儲表示二叉樹的順序存儲表示-#define max_tree_size 100/ 二叉樹的最大結點數二叉樹的最大結點數typedef telemtype sqbitreemax_ tree_size; / 0號單元存儲根結點號單元存儲根結點sqbitree bt;例如例如: :abcdef a b d 0 c 0 e 0 0 0 0 0 0 f 0 1 2 3 4 5 6 7 8 9 10 11 12 1314013260表示不存在此結點完全二叉樹的數組表示完全二叉樹的數組表示 一般二叉樹的數組表示一般二叉

24、樹的數組表示55特點：特點： 結點間關系蘊含在其存儲位置中，浪費空間，適于結點間關系蘊含在其存儲位置中，浪費空間，適于存滿二叉樹和完全二叉樹（在最壞情況下，深度為存滿二叉樹和完全二叉樹（在最壞情況下，深度為k且只有且只有k個結點的單支樹需要長度為個結點的單支樹需要長度為2k-1的一維數組）的一維數組）。 由于一般二叉樹必須仿照完全二叉樹那樣存儲，可由于一般二叉樹必須仿照完全二叉樹那樣存儲，可能會浪費很多存儲空間，單支樹就是一個極端情況。能會浪費很多存儲空間，單支樹就是一個極端情況。二、二叉樹的鏈式存儲結構二、二叉樹的鏈式存儲結構（1 1）二叉鏈表）二叉鏈表（2）三叉鏈表三叉鏈表adebcf r

25、ootlchild data rchild結點結構結點結構:1. 1. 二叉鏈表二叉鏈表fabcde在在n n個結點的二叉鏈表中，有個結點的二叉鏈表中，有n+1n+1個空指針域個空指針域typedef struct bitnode /結點結構結點結構 telemtype data; struct bitnode *lchild, *rchild; / 左右孩子指針 bitnode, *bitree;lchild data rchild結點結構結點結構:c 語言的類型描述如下語言的類型描述如下: :adebcf root 2三叉鏈表三叉鏈表parent lchild data rchild結點結

26、構結點結構:abcdef typedef struct tritnode / 結點結構結點結構 telemtype data; struct tritnode *lchild, *rchild; / 左右孩子指針 struct tritnode *parent; /雙親指針 tritnode, *tritree;parent lchild data rchild結點結構結點結構:c 語言的類型描述如下語言的類型描述如下: :二叉鏈存儲結構的二叉樹操作實現二叉鏈存儲結構的二叉樹操作實現 在二叉鏈存儲結構下，針對一棵二叉樹，主要涉及如下幾在二叉鏈存儲結構下，針對一棵二叉樹，主要涉及如下幾個功能模塊

27、：個功能模塊：v 二叉樹的初始化操作；二叉樹的初始化操作；v 二叉樹中給某結點插入一個左結點的操作；二叉樹中給某結點插入一個左結點的操作；v 二叉樹中給某結點插入一個右結點的操作；二叉樹中給某結點插入一個右結點的操作；v 刪除二叉樹中某結點的左子樹操作；刪除二叉樹中某結點的左子樹操作；v 刪除二叉樹中某結點的右子樹操作。刪除二叉樹中某結點的右子樹操作。 各算法的基本思想及程序實現如下：各算法的基本思想及程序實現如下： typedef structtypedef struct node node datatypedatatype data; data;struct node struct nod

28、e * *leftchildleftchild; ; struct node struct node * *rightchildrightchild; ; bitreenode bitreenode; /; /* *結點的結構體定義結點的結構體定義* */ /1.1.二叉樹的初始化二叉樹的初始化 算法的基本思想算法的基本思想: :創建二叉樹的頭結點。創建二叉樹的頭結點。 程序實現：程序實現： void initiate(bitreenodevoid initiate(bitreenode * * *root)root) * *root = (bitreenode root = (bitreen

29、ode * *)malloc(sizeof(bitreenode)malloc(sizeof(bitreenode););( (* *root)-leftchildroot)-leftchild=null;=null;( (* *root)-rightchildroot)-rightchild=null;=null; 2.2.二叉樹中給某結點插入一個左結點的操作二叉樹中給某結點插入一個左結點的操作 算法的基本思想算法的基本思想: : 若當前結點若當前結點( (假設為假設為currcurr）非空，在非空，在currcurr的左子的左子樹插入元素值為樹插入元素值為x x的新結點的新結點 ，原，原c

30、urrcurr所指結點的左所指結點的左子樹成為新插入結點的左子樹。若插入成功返回新子樹成為新插入結點的左子樹。若插入成功返回新插入結點的指針，否則返回空指針。插入結點的指針，否則返回空指針。程序實現：程序實現： bitreenode bitreenode * *insertleftnode(bitreenode insertleftnode(bitreenode * *curr,datatype x) curr,datatype x) bitreenode bitreenode * *s, s, * *t;t; if(curr if(curr=null) return null;=null)

31、return null;t=curr-leftchildt=curr-leftchild; ;s=(bitreenode s=(bitreenode * *)malloc(sizeof(bitreenode)malloc(sizeof(bitreenode);); s-data=x; s-data=x;s-leftchilds-leftchild=t;=t; s-rightchild s-rightchild=null;=null;curr-leftchildcurr-leftchild=s;=s;return curr-leftchildreturn curr-leftchild; ; 3.

32、3.刪除二叉樹中某結點的左子樹操作刪除二叉樹中某結點的左子樹操作算法的基本思想算法的基本思想: :若若currcurr非空，刪除非空，刪除currcurr所指結點的左子樹。若所指結點的左子樹。若刪除成功，返回刪除結點的雙親結點指針，否則返回空指針。刪除成功，返回刪除結點的雙親結點指針，否則返回空指針。程序實現程序實現：bitreenode bitreenode * *deletelefttree(bitreenode deletelefttree(bitreenode * *currcurr) ) if(curr=null|curr-leftchildif(curr=null|curr-lef

33、tchild=null)=null) return null; return null;destroy(&curr-leftchilddestroy(&curr-leftchild););curr-leftchildcurr-leftchild=null;=null;return currreturn curr; ; 66知識回顧 樹和二叉樹的定義 二叉樹的特點 二叉樹的存儲結構676.3.1二叉樹的遍歷二叉樹的遍歷68一、問題的提出一、問題的提出二、先左后右的遍歷算法二、先左后右的遍歷算法三、算法的遞歸描述三、算法的遞歸描述四、中序遍歷算法的非遞歸描述四、中序遍歷算法的非遞歸

34、描述五五、遍歷算法的應用舉例遍歷算法的應用舉例69 順著某一條搜索路徑巡訪巡訪二叉樹中的結點，使得每個結點均被訪問一均被訪問一次次，而且僅被訪問一次僅被訪問一次。一、問題的提出一、問題的提出“訪問訪問”的含義可以很廣，如：輸出結點的信息等。70 “遍歷遍歷”是任何類型均有的操作，對線性結構而言，只有一條搜索路徑(因為每個結點均只有一個后繼)，故不需要另加討論。而二叉樹是非線性結構， 每個結點有兩個后繼每個結點有兩個后繼，則存在如何遍歷存在如何遍歷即按什么樣的搜索搜索路徑路徑遍歷的問題。71 對對“二叉樹二叉樹”而言，可以有而言，可以有三條搜索路徑：三條搜索路徑：1先上后下先上后下的按層次遍歷；

35、2先左先左（子樹）后右后右（子樹）的遍歷；3先右先右（子樹）后左后左（子樹）的遍歷。72二、先左后右的遍歷算法二、先左后右的遍歷算法先先（根）序的遍歷算法中中（根）序的遍歷算法后后（根）序的遍歷算法73 若二叉樹為空樹，則空操作；否則，（1）訪問根結點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。先（根）序的遍歷算法：先（根）序的遍歷算法：74 若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結點；（3）中序遍歷右子樹。中（根）序的遍歷算法：中（根）序的遍歷算法：75 若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結點。后（根）序的遍

36、歷算法：后（根）序的遍歷算法：76adbct l rat l rt l rbdct l r先序遍歷序列：先序遍歷序列：a b d c先序遍歷:77adbcl t rbl t rl t radcl t r中序遍歷序列：中序遍歷序列：b d a c中序遍歷:78adbc l r tl r tl r tadcl r t后序遍歷序列：后序遍歷序列： d b c a后序遍歷:b79-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：- + a * b - c d / e f-+a*b-cd/ef-+a*b-c d/e f80三、算法的遞歸描述三、算法的遞歸描述void inordertraverse (

37、bitree t, status(*visit)(telemtype e) / 中中序遍歷二叉樹序遍歷二叉樹 if (t) inordertraverse (t-lchild, visit) ;/中中序遍歷左子樹序遍歷左子樹 visit(t-data) / 訪問根結點訪問根結點 inordertraverse (t-rchild, visit);/中序遍歷右子樹中序遍歷右子樹 見演示見演示81status inordertraverse(bitree t,status(*visit)(telemtype e)initstack(s); push(s,t); /根指針進棧根指針進棧while(!

38、stackempty(s) while(gettop(s,p)&p) push(s,p-lchild); /向左走到盡頭向左走到盡頭 pop(s,p); /空指針退棧空指針退棧 if(!stackempty(s) /訪問結點訪問結點,向右一步向右一步 pop(s,p); visit(p-data); push(s,p-rchild); /if /whilereturn ok;/inordertraverse算法算法1四、中序遍歷算法的非遞歸描述四、中序遍歷算法的非遞歸描述82-b*ca-*anullnullbnullnullcnullnull中序遍歷序列:a*b-cwhile(!sta

39、ckempty(s) while(gettop(s,p)&p)push(s,p-lchild); /向左走到盡頭向左走到盡頭 pop(s,p); /空指針退棧空指針退棧 if(!stackempty(s)/訪問結點訪問結點,向右一步向右一步 pop(s,p); if(!visit(p-data) return error; push(s,p-rchild); /if83status inordertraverse(bitree t, status (*visit)(telemtype e) initstack(s); p=t; while(p|!stackempty(s) if (p)

40、 push(s,p); p=p-lchild; /根指針進棧根指針進棧, ,遍歷左子樹遍歷左子樹 else/根指針退棧根指針退棧,訪問根結點訪問根結點,遍歷右子樹遍歷右子樹 pop(s,p); visit(p-data); p=p-rchild; / else / while return ok;/inordertraverse算法算法2中序遍歷算法的非遞歸描述中序遍歷算法的非遞歸描述84p=t; while(p|!stackempty(s) if (p) push(s,p); p=p-lchild;/根指針進棧根指針進棧,遍歷左子樹遍歷左子樹 else/根指針退棧根指針退棧,訪問根結點訪問根

41、結點,遍歷遍歷右子樹右子樹 pop(s,p);if(!visit(p-data)return error; p=p-rchild; / else / while-b*ca-*abc85+*a*/edcb先序遍歷結果先序遍歷結果+ * * / a b c d e前綴表示法前綴表示法中序遍歷結果中序遍歷結果a / b * c * d + e中綴表示法中綴表示法后序遍歷結果后序遍歷結果a b / c * d * e +后綴表示法后綴表示法層次遍歷結果層次遍歷結果+ * e * d / c a b用二叉樹表示算術表達式用二叉樹表示算術表達式void layerorder(bitreevoid laye

42、rorder(bitree t) t) /層序遍歷二叉樹層序遍歷二叉樹 if (t) if (t) initqueue(q initqueue(q); ); /建一個空隊（初始化隊列）建一個空隊（初始化隊列） enqueue(q,tenqueue(q,t); ); /將一個結點插入隊尾的函數將一個結點插入隊尾的函數 while(while( !queueempty(q!queueempty(q) ) ) ) dequeue(q dequeue(q, &p); , &p); /隊首結點出隊隊首結點出隊( (送入送入p)p) visit(p); visit(p); if(p-lch

43、ild) enqueue(q,p-lchild if(p-lchild) enqueue(q,p-lchild); ); /p/p的左孩子入隊的左孩子入隊 if(p-rchild) enqueue(q,p-rchildif(p-rchild) enqueue(q,p-rchild); ); /p/p的右孩子入隊的右孩子入隊 /layerorder/layerorder 當孩子為空時不要當孩子為空時不要將空指針入隊將空指針入隊遍歷算法思想的應用-步驟 要明確所要編寫的算法的功能描述（包括所涉及的各參數或要明確所要編寫的算法的功能描述（包括所涉及的各參數或變量的含義）變量的含義）這在遞歸算法中尤其

44、要注意。在此基礎上這在遞歸算法中尤其要注意。在此基礎上按如下步驟討論算法的實現：按如下步驟討論算法的實現：v如果如果t為空，則按預定功能實現對空樹的操作，以滿足功為空，則按預定功能實現對空樹的操作，以滿足功能要求（包括對相應參數，變量的操作）。能要求（包括對相應參數，變量的操作）。v否則，假設算法對否則，假設算法對t的左右子樹都能分別實現預定功能，的左右子樹都能分別實現預定功能，在此基礎上，通過按預定要求適當調用對左右子樹的算在此基礎上，通過按預定要求適當調用對左右子樹的算法的功能，及對當前結點的操作實現對整個二叉樹的功法的功能，及對當前結點的操作實現對整個二叉樹的功能（包括對各變量、參數的操

45、作）。能（包括對各變量、參數的操作）。89例例1 1：統計二叉樹中葉子結點的：統計二叉樹中葉子結點的個數個數.(.(先序遍歷先序遍歷) )90算法基本思想算法基本思想: : 先序(或中序或后序)遍歷二叉樹，在遍歷過程中查找葉子結點，并計數。由此，需在遍歷算法中增添一個需在遍歷算法中增添一個“計數計數”的參數的參數，并將算法中“訪問結點”的操作改為：若是葉子，則計數器增若是葉子，則計數器增1 1。91void countleaf (bitree t, int& count) if ( t ) if (!t-lchild)& (!t-rchild) count+; / 對葉子結點計

46、數 countleaf( t-lchild, count); countleaf( t-rchild, count); / if / countleaf92例例2 2：求二叉樹的深度：求二叉樹的深度 ( (后序遍歷后序遍歷) )93算法基本思想算法基本思想: : 從二叉樹深度的定義可知，二叉樹的二叉樹的深度應為其左、右子樹深度的最大值加深度應為其左、右子樹深度的最大值加1 1。由此，需先分別求得左、右子樹的深度需先分別求得左、右子樹的深度，算法中“訪問結點”的操作為：求得左、求得左、右子樹深度的最大值，然后加右子樹深度的最大值，然后加 1 1 。 首先分析二叉樹的深度二叉樹的深度和它的左左、右

47、子右子樹深度樹深度之間的關系。94int depth (bitree t ) / 返回二叉樹的深度 if ( !t ) depthval = 0; else depthleft = depth( t-lchild ); depthright= depth( t-rchild ); depthval = 1 + (depthleft depthright ? depthleft : depthright); return depthval;95例例3 3：建立二叉樹的存：建立二叉樹的存儲結構儲結構96 以字符串的形式以字符串的形式 根根 左子樹左子樹 右子樹右子樹定義一棵二叉樹定義一棵二叉樹例如

48、:abcd以空白字符“ ”表示a(b( ,c( , ),d( , )空樹空樹只含一個根結點只含一個根結點的二叉樹的二叉樹a以字符串“a ”表示以下列字符串表示97status createbitree(bitree &t) scanf(&ch); if (ch= ) t = null; else if (!(t = (bitnode *)malloc(sizeof(bitnode) exit(overflow); t-data = ch; / 生成根結點 createbitree(t-lchild); / 構造左子樹 createbitree(t-rchild); / 構造右子

49、樹 return ok; / createbitree98a b c d a bcd上頁算法執行過程舉例如下：atbcdstatus createbitree(bitree &t) scanf(&ch); if (ch= ) t = null; else if (!(t = (bitnode *)malloc(sizeof(bitnode) exit(overflow); t-data = ch; createbitree(t-lchild); createbitree(t-rchild); return ok; 99問題 已知一棵二叉樹的先序遍歷序列，能否已知一棵二叉樹的先序

50、遍歷序列，能否得到這棵樹？得到這棵樹？100例：一棵樹的先序序列為：1，2，3。請畫出這棵樹。101 9可以證明：可以證明：一棵二叉樹的先序序列和中一棵二叉樹的先序序列和中序序列可以唯一的確定這棵二叉樹。序序列可以唯一的確定這棵二叉樹。結論結論 僅已知一棵二叉樹的先序遍歷序列，僅已知一棵二叉樹的先序遍歷序列，不不能能唯一確定這棵樹。唯一確定這棵樹。已知一棵二叉樹的中序序列和已知一棵二叉樹的中序序列和后序序列后序序列分別是分別是bdceafhg bdceafhg 和和 decbhgfadecbhgfa，請畫出這棵二叉樹。，請畫出這棵二叉樹。分析：分析：由后序遍歷特征，根結點必在后序序列尾部由后序

51、遍歷特征，根結點必在后序序列尾部（即（即a a）；由中序遍歷特征，根結點必在其中間，而且其左部必由中序遍歷特征，根結點必在其中間，而且其左部必全部是左子樹的子孫全部是左子樹的子孫（即（即bdcebdce），其右部必全部是右，其右部必全部是右子樹的子孫子樹的子孫（即（即fhgfhg）；繼而，根據后序中的繼而，根據后序中的decbdecb子樹可確定子樹可確定b b為為a a的左孩子，的左孩子，根據根據hgfhgf子串可確定子串可確定f f為為a a的右孩子；以此類推。的右孩子；以此類推。105106 二叉樹的遍歷：以一定的次序排列二叉樹的結點。-非線性結構的線性化。 傳統的二叉鏈表存儲結構只存儲了

52、結點的左右孩子的信息，沒有存儲其前趨和后繼信息。 這些信息只有在遍歷過程中才能得到。 傳統的二叉樹遍歷方法：-利用堆棧 效率低知識回顧知識回顧107-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：- + a * b - c d / e f-+a*b-cd/ef-+a*b-c d/e f108問題：問題：能否在遍歷過程中把結點的能否在遍歷過程中把結點的前趨和后繼信息保存下來，并且提前趨和后繼信息保存下來，并且提高算法的效率呢？高算法的效率呢？1096.3.2線索二叉樹線索二叉樹threaded binary treethreaded binary tree110主要內容（1）什么是線索二叉樹

53、（2）基于線索二叉樹的遍歷方法（3）如何建立線索二叉樹111線索二叉樹的引入和定義線索二叉樹的引入和定義所以，所以， 空指針數目空指針數目2n(n-1)=n+1個個。證明：證明：用二叉鏈表存儲包含用二叉鏈表存儲包含n n個結點的二叉樹，結點必有個結點的二叉樹，結點必有2n個鏈域。個鏈域。除根結點外，二叉樹中每一個結點除根結點外，二叉樹中每一個結點有且僅有一個雙親有且僅有一個雙親，即每個結點地址占用了雙親的一個直接后繼，即每個結點地址占用了雙親的一個直接后繼，n n個結點地址共個結點地址共占用了占用了n-1n-1個雙親的指針域個雙親的指針域。也就是說，只會有。也就是說，只會有n n1 1個結點的

54、個結點的鏈域存放指針。鏈域存放指針。用二叉鏈表法存儲包含用二叉鏈表法存儲包含n n個結點的二叉個結點的二叉樹，結點的指針區域中會有樹，結點的指針區域中會有n+1n+1個空指個空指針。針。112adebcf rootlchild data rchild結點結構結點結構:fabcde113思考：思考：二叉鏈表空間效率這么低，能否利用二叉鏈表空間效率這么低，能否利用這些空閑區存放有用的信息或線索？這些空閑區存放有用的信息或線索？可以用它來存放當前結點的可以用它來存放當前結點的直接前驅和后直接前驅和后繼繼等線索，以加快查找速度。等線索，以加快查找速度。這就是這就是（threaded binary tr

55、ee） 對二叉樹進行某種遍歷之后，將得到一個對二叉樹進行某種遍歷之后，將得到一個線性有序的序列。線性有序的序列。例如對某二叉樹的例如對某二叉樹的中序遍歷中序遍歷結果是結果是b d c e a f h gb d c e a f h g，意味著，意味著已將該樹轉已將該樹轉為線性排列，顯然其中結點為線性排列，顯然其中結點具有唯一前驅和唯具有唯一前驅和唯一后繼。一后繼。討論討論1 1：二叉樹是二叉樹是1:21:2的非線性結構，如的非線性結構，如何定義其直接后繼？何定義其直接后繼？先定義遍歷規則，然后才能定義先定義遍歷規則，然后才能定義直接前驅和后繼。直接前驅和后繼。115討論討論2 2：如何獲得這種如

56、何獲得這種“直接前驅直接前驅”或或“直接后繼直接后繼”？有何意義？有何意義？二叉樹中容易找到結點的二叉樹中容易找到結點的左右孩子左右孩子信息，信息，但該結點的直接前驅和直接后繼只能在某種但該結點的直接前驅和直接后繼只能在某種遍歷過程中遍歷過程中動態動態獲得。獲得。先依先依遍歷規則遍歷規則把每個結點對應的把每個結點對應的前驅前驅和和后繼線索后繼線索預存預存起來，這叫做起來，這叫做“線索化線索化”。意義：意義：從從任一結點任一結點出發都能快速找到其出發都能快速找到其前驅和后繼，且前驅和后繼，且不必借助堆棧。不必借助堆棧。 每個結點增加兩個域：每個結點增加兩個域：fwd和和bwd；存放前驅指針存放前

57、驅指針存放后繼指針存放后繼指針如何預存這類信息？如何預存這類信息？ 與原有的左右孩子指針域與原有的左右孩子指針域“復用復用”，充分利用那，充分利用那n+1個空鏈域。個空鏈域。規規 定：定：1）若結點有左子樹，則）若結點有左子樹，則lchild指向其指向其左孩子；否則，左孩子；否則， lchild指向其直接前驅指向其直接前驅(即線索即線索)；2）若結點有右子樹，則）若結點有右子樹，則rchild指向其右指向其右孩子；否則，孩子；否則，rchild指向其直接后繼指向其直接后繼(即即線索線索) 。datalchildrchildfwdbwddatalchildrchild缺點：空間效率太低！缺點：空

58、間效率太低！問題：計算機如何問題：計算機如何判斷是孩子指針還判斷是孩子指針還是線索指針？是線索指針？如何區別？如何區別？lchildltagdatartag rchild約定約定:當當tag域為域為0時時,表示表示正常正常情況情況;當當tag域為域為1時時,表示表示線索線索情況情況.前驅前驅(后繼后繼)左左(右右)孩子孩子為區別兩種不同情況，特增加兩個標志域：為區別兩種不同情況，特增加兩個標志域：各各1bit1bit1. 有關線索二叉樹的幾個術語有關線索二叉樹的幾個術語 線索鏈表：線索鏈表： 線線 索：索：線索二叉樹：線索二叉樹： 線線 索索 化：化：用用含含tag的結點樣式所構成的二叉鏈表。

59、的結點樣式所構成的二叉鏈表。指向結點前驅和后繼的指針。指向結點前驅和后繼的指針。在二叉樹的結點上加上線索的二叉樹。在二叉樹的結點上加上線索的二叉樹。對二叉樹以對二叉樹以某種次序遍歷某種次序遍歷使其變為線索二使其變為線索二叉樹的過程。叉樹的過程。線索化過程就是在遍歷過程中修改空指針的過程：線索化過程就是在遍歷過程中修改空指針的過程：將空的將空的lchildlchild改為結點的直接前驅；改為結點的直接前驅；將空的將空的rchildrchild改為結點的直接后繼。改為結點的直接后繼。非空指針仍然指向孩子結點（稱為非空指針仍然指向孩子結點（稱為“正常情況正常情況”）119typedef struct

60、 bithrnod telemtype data; struct bithrnode *lchild, *rchild; / 左右指針 pointerthr ltag, rtag; / 左右標志 bithrnode, *bithrtree; typedef enum link, thread pointerthr; / link=0:指針，thread=1:線索二叉樹的二叉線索存儲表示二叉樹的二叉線索存儲表示在二叉樹的線索鏈表上添加一個頭結點，并在二叉樹的線索鏈表上添加一個頭結點，并令其令其lchild域域的指針指向二叉樹的的指針指向二叉樹的根結點根結點，其，其rchild域域的指針指向中序遍歷時訪問的的指針指向中序遍歷時訪問的最后一最后一個結點個結點。令二叉樹中序序列中的第一個結點的令二叉樹中序序列中的第一個結點的lchild域域指針和最后一個結點指針和最后一個結點rchild域域的