05_樹和二叉樹

1、線性結(jié)構(gòu)與非線性結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)課程中數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非 線性結(jié)構(gòu)。 對于數(shù)據(jù)結(jié)構(gòu)課程而言，簡單地說，線性結(jié)構(gòu)是n 個數(shù)據(jù)元素的有序（次序）集合。 特征 1集合中必存在唯一的一個第一個元素； 2集合中必存在唯一的一個最后的元素； 3除最后元素之外，其它數(shù)據(jù)元素均有唯一的后繼； 4除第一元素之外，其它數(shù)據(jù)元素均有唯一的前驅(qū)。 相對應(yīng)于線性結(jié)構(gòu)，非線性結(jié)構(gòu)的邏輯特征是一個 結(jié)點(diǎn)元素可能對應(yīng)多個直接前驅(qū)和多個后繼。 2 第五章 樹與二叉 樹 3 3 第五章第五章 樹與二叉樹樹與二叉樹 4 4 樹和森林的概念樹和森林的概念 n兩種樹：自由樹與有根樹。兩種樹：自由樹與有根樹。 n自由樹自由樹：

2、 一棵自由樹一棵自由樹 Tf 可定義為一個二元組可定義為一個二元組 Tf = (V, E) 其中其中V = v1, ., vn 是由是由 n (n0) 個元素組成的個元素組成的 有限非空集合，稱為頂點(diǎn)集合。有限非空集合，稱為頂點(diǎn)集合。E = (vi, vj) | vi, vj V, 1i, jn 是是n-1個序?qū)Φ募?，稱為邊集個序?qū)Φ募?，稱為邊集 合，合，E 中的元素中的元素 (vi, vj）稱為邊或分支。）稱為邊或分支。 n在自由樹中選定一頂點(diǎn)做根，則成為一棵通常在自由樹中選定一頂點(diǎn)做根，則成為一棵通常 的的樹樹 連通的，有連通的，有n-1條邊，條邊， 且沒有簡單回路且沒有簡單回路 5

3、5 自由樹 n有根樹有根樹：一棵有根樹一棵有根樹 T，簡稱為樹，簡稱為樹， 它是它是n (n0) 個結(jié)點(diǎn)的有限集合。當(dāng)個結(jié)點(diǎn)的有限集合。當(dāng)n = 0時，時， T 稱為空樹；否則，稱為空樹；否則，T 是非空樹，記作是非空樹，記作 6 6 u r 是是一個特定的稱為一個特定的稱為根根(root)的結(jié)點(diǎn)，它只的結(jié)點(diǎn)，它只 有直接后繼，但沒有直接前驅(qū)；有直接后繼，但沒有直接前驅(qū)； u根以外的其他結(jié)點(diǎn)劃分為根以外的其他結(jié)點(diǎn)劃分為 m (m 0) 個互不個互不 相交的有限集合相交的有限集合T1, T2, , Tm，每個集合又，每個集合又 是一棵樹，并且稱之為是一棵樹，并且稱之為根的子樹根的子樹。 u每棵子

4、樹的根結(jié)點(diǎn)有且僅有一個直接前驅(qū)，每棵子樹的根結(jié)點(diǎn)有且僅有一個直接前驅(qū)， 但可以有但可以有0個或多個直接后繼。個或多個直接后繼。 0 0 n,T,.,T,Tr, n, T m21 7 層次關(guān)系：層次關(guān)系： 家譜中的雙親子女關(guān)系家譜中的雙親子女關(guān)系 組織中的上下級關(guān)系組織中的上下級關(guān)系 計算機(jī)文件系統(tǒng)中的目錄與子目錄關(guān)系計算機(jī)文件系統(tǒng)中的目錄與子目錄關(guān)系 表達(dá)式中的括號嵌套關(guān)系，等等表達(dá)式中的括號嵌套關(guān)系，等等 對這些關(guān)系及相關(guān)對象進(jìn)行抽象，就形成了對這些關(guān)系及相關(guān)對象進(jìn)行抽象，就形成了 計算機(jī)科學(xué)中最重要的數(shù)據(jù)結(jié)構(gòu)之一計算機(jī)科學(xué)中最重要的數(shù)據(jù)結(jié)構(gòu)之一 樹。樹。 8 8 樹的基本術(shù)語樹的基本術(shù)語

5、n子女子女：若結(jié)點(diǎn)的子樹非空，結(jié)點(diǎn)子樹的根即：若結(jié)點(diǎn)的子樹非空，結(jié)點(diǎn)子樹的根即 為該結(jié)點(diǎn)的子女。為該結(jié)點(diǎn)的子女。 n雙親雙親：若結(jié)點(diǎn)有子女，該結(jié)點(diǎn)是子女雙親。：若結(jié)點(diǎn)有子女，該結(jié)點(diǎn)是子女雙親。 D A CB IJHGF E MLK 9 9 n兄弟兄弟：同一結(jié)點(diǎn)的子女互稱為兄弟。：同一結(jié)點(diǎn)的子女互稱為兄弟。 n度度：結(jié)點(diǎn)的子女個數(shù)即為該結(jié)點(diǎn)的度；樹中：結(jié)點(diǎn)的子女個數(shù)即為該結(jié)點(diǎn)的度；樹中 各個結(jié)點(diǎn)的度的最大值稱為各個結(jié)點(diǎn)的度的最大值稱為樹的度樹的度。 n分支結(jié)點(diǎn)分支結(jié)點(diǎn)：度不為：度不為0的結(jié)點(diǎn)即為分支結(jié)點(diǎn)，的結(jié)點(diǎn)即為分支結(jié)點(diǎn)， 亦稱為非終端結(jié)點(diǎn)。亦稱為非終端結(jié)點(diǎn)。 n葉結(jié)點(diǎn)葉結(jié)點(diǎn)：度為：度為0的結(jié)

6、點(diǎn)即為葉結(jié)點(diǎn)，亦稱為的結(jié)點(diǎn)即為葉結(jié)點(diǎn)，亦稱為 終端結(jié)點(diǎn)。終端結(jié)點(diǎn)。 n祖先祖先：某結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑上的各個結(jié)點(diǎn)：某結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑上的各個結(jié)點(diǎn) 都是該結(jié)點(diǎn)的祖先。都是該結(jié)點(diǎn)的祖先。 n子孫子孫：某結(jié)點(diǎn)的所有下屬結(jié)點(diǎn)，都是該結(jié)點(diǎn)：某結(jié)點(diǎn)的所有下屬結(jié)點(diǎn)，都是該結(jié)點(diǎn) 的子孫。的子孫。 1010 n結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次：規(guī)定根結(jié)點(diǎn)在第一層，其子女：規(guī)定根結(jié)點(diǎn)在第一層，其子女 結(jié)點(diǎn)的層次等于它的層次加一。以下類推。結(jié)點(diǎn)的層次等于它的層次加一。以下類推。 n深度深度：結(jié)點(diǎn)的深度即為結(jié)點(diǎn)的層次；離根最：結(jié)點(diǎn)的深度即為結(jié)點(diǎn)的層次；離根最 遠(yuǎn)結(jié)點(diǎn)的層次即為遠(yuǎn)結(jié)點(diǎn)的層次即為樹的深度樹的深度。 1層 2層 4層

7、 3層 depth = 4 D A CB IJHGF E MLK height = 4 11 11 n結(jié)點(diǎn)高度結(jié)點(diǎn)高度：規(guī)定葉結(jié)點(diǎn)的高度為：規(guī)定葉結(jié)點(diǎn)的高度為1，其雙親結(jié)，其雙親結(jié) 點(diǎn)的高度等于它的高度加一。點(diǎn)的高度等于它的高度加一。 n樹的高度樹的高度：等于根結(jié)點(diǎn)的高度。：等于根結(jié)點(diǎn)的高度。 n有序樹有序樹：樹中結(jié)點(diǎn)的各棵子樹：樹中結(jié)點(diǎn)的各棵子樹 T0, T1, 是是從左從左 到右有次序的到右有次序的(即不能互換即不能互換) ，即為有序樹，即為有序樹 (OrderedTree) 。 n無序樹無序樹：樹中結(jié)點(diǎn)的各棵子樹之間的次序是不：樹中結(jié)點(diǎn)的各棵子樹之間的次序是不 重要的，可以互相交換位置重

8、要的，可以互相交換位置(UnorderedTree)。 注意注意：若不特別指明，一般討論的樹都是有序樹：若不特別指明，一般討論的樹都是有序樹。 n森林森林：森林是：森林是m（m0）棵樹的集合。）棵樹的集合。 1212 樹的抽象數(shù)據(jù)類型樹的抽象數(shù)據(jù)類型 template class Tree /對象對象: 樹是由樹是由n (0) 個結(jié)點(diǎn)組成的有限集合。在個結(jié)點(diǎn)組成的有限集合。在 /類界面中的類界面中的 position 是樹中結(jié)點(diǎn)的地址。在順序是樹中結(jié)點(diǎn)的地址。在順序 /存儲方式下是下標(biāo)型存儲方式下是下標(biāo)型, 在鏈表存儲方式下是指針在鏈表存儲方式下是指針 /型。型。T 是樹結(jié)點(diǎn)中存放數(shù)據(jù)的類型是

9、樹結(jié)點(diǎn)中存放數(shù)據(jù)的類型, 要求所有結(jié)要求所有結(jié) /點(diǎn)的數(shù)據(jù)類型都是一致的。點(diǎn)的數(shù)據(jù)類型都是一致的。 public: Tree (); Tree (); 1313 BuildRoot (const T /建立樹的根結(jié)點(diǎn) position FirstChild(position p); /返回 p 第一個子女地址, 無子女返回 0 position NextSibling(position p); /返回 p 下一兄弟地址, 若無下一兄弟返回 0 position Parent(position p); /返回 p 雙親結(jié)點(diǎn)地址, 若 p 為根返回 0 T getData(position p);

10、 /返回結(jié)點(diǎn) p 中存放的值 bool InsertChild(position p, T /在結(jié)點(diǎn) p 下插入值為 value 的新子女, 若插 /入失敗, 函數(shù)返回false, 否則返回true 1414 bool DeleteChild (position p, int i); /刪除結(jié)點(diǎn) p 的第 i 個子女及其全部子孫結(jié) /點(diǎn), 若刪除失敗, 則返回false, 否則返回true void DeleteSubTree (position t); /刪除以 t 為根結(jié)點(diǎn)的子樹 bool IsEmpty (); /判樹空否, 若空則返回true, 否則返回false void Trave

11、rsal (void (*visit)(position p); /遍歷以 p 為根的子樹 ; 1515 LLRR 二叉樹二叉樹 (Binary Tree)(Binary Tree) n二叉樹的定義二叉樹的定義 一棵二叉樹是結(jié)點(diǎn)的一個有限集合，該集合一棵二叉樹是結(jié)點(diǎn)的一個有限集合，該集合 或者為空，或者是由一個根結(jié)點(diǎn)加上兩棵分或者為空，或者是由一個根結(jié)點(diǎn)加上兩棵分 別稱為左子樹和右子樹的、互不相交的二叉別稱為左子樹和右子樹的、互不相交的二叉 樹組成。樹組成。 1616 二叉樹的性質(zhì)二叉樹的性質(zhì) n性質(zhì)性質(zhì)1 若二叉樹結(jié)點(diǎn)的層次從若二叉樹結(jié)點(diǎn)的層次從 1 開始開始, 則在則在 二叉樹的第二叉樹的

12、第 i 層最多有層最多有 2i-1 個結(jié)點(diǎn)。個結(jié)點(diǎn)。( i1) 證明用數(shù)學(xué)歸納法證明用數(shù)學(xué)歸納法 n性質(zhì)性質(zhì)2 深度為深度為 k 的二叉樹最少有的二叉樹最少有 k 個結(jié)點(diǎn)，個結(jié)點(diǎn)， 最多有最多有 2k-1個結(jié)點(diǎn)。個結(jié)點(diǎn)。( k1 ) 因?yàn)槊恳粚幼钌僖幸驗(yàn)槊恳粚幼钌僖?個結(jié)點(diǎn)，因此，最個結(jié)點(diǎn)，因此，最 少結(jié)點(diǎn)數(shù)為少結(jié)點(diǎn)數(shù)為 k。最多結(jié)點(diǎn)個數(shù)借助性質(zhì)。最多結(jié)點(diǎn)個數(shù)借助性質(zhì)1： 用求等比級數(shù)前用求等比級數(shù)前k項(xiàng)和的公式項(xiàng)和的公式 20 +21 +22 + +2k-1 = 2k-1 1717 n性質(zhì)性質(zhì)3 對任何一棵二叉樹，如果其葉結(jié)點(diǎn)有對任何一棵二叉樹，如果其葉結(jié)點(diǎn)有 n0 個個, 度為度為 2

13、 的非葉結(jié)點(diǎn)有的非葉結(jié)點(diǎn)有 n2 個個, 則有則有 n0n21 若設(shè)度為若設(shè)度為 1 的結(jié)點(diǎn)有的結(jié)點(diǎn)有 n1 個，總結(jié)點(diǎn)數(shù)為個，總結(jié)點(diǎn)數(shù)為n， 總邊數(shù)為總邊數(shù)為e，則根據(jù)二叉樹的定義，則根據(jù)二叉樹的定義， n = n0+n1+n2 e = 2n2+n1 = n-1 因此，有因此，有 2n2+n1 = n0+n1+n2-1 n2 = n0-1 n0 = n2+1 1818 n定義定義1 滿二叉樹滿二叉樹 (Full Binary Tree) n定義定義2 完全二叉樹完全二叉樹 (Complete Binary Tree) 若設(shè)二叉樹的深度為若設(shè)二叉樹的深度為 k，則共有，則共有 k 層。除第層。

14、除第 k 層外，其它各層層外，其它各層 (1k-1) 的結(jié)點(diǎn)數(shù)都達(dá)到的結(jié)點(diǎn)數(shù)都達(dá)到 最大個數(shù)，第最大個數(shù)，第k層從右向左連續(xù)缺若干結(jié)點(diǎn)，層從右向左連續(xù)缺若干結(jié)點(diǎn)， 這就是完全二叉樹。這就是完全二叉樹。 每一層結(jié)點(diǎn)都達(dá)到最每一層結(jié)點(diǎn)都達(dá)到最 大個數(shù)大個數(shù); 除最底層結(jié)點(diǎn)的度為除最底層結(jié)點(diǎn)的度為0 外，其它各層結(jié)點(diǎn)的度外，其它各層結(jié)點(diǎn)的度 都為都為2 葉結(jié)點(diǎn)僅在層次最大葉結(jié)點(diǎn)僅在層次最大 的兩層出現(xiàn)；的兩層出現(xiàn)； 對任一結(jié)點(diǎn)，若其右對任一結(jié)點(diǎn)，若其右 子樹的高度為子樹的高度為l，則其，則其 左子樹的高度只能是左子樹的高度只能是l 或或l+1 1919 n性質(zhì)性質(zhì)4 具有具有 n (n0) 個結(jié)點(diǎn)的

15、完全二叉樹的個結(jié)點(diǎn)的完全二叉樹的 深度為深度為 log2(n+1) 設(shè)完全二叉樹的深度為設(shè)完全二叉樹的深度為k，則有，則有 2k-1-1 n 2k-1 變形變形 2k-1 n+12k 取對數(shù)取對數(shù) k-1 1, 則則 i 的雙親為的雙親為 i2 若若2*i = n, 則則 i 的左子女為的左子女為 2*i， 若若2*i+1 = n, 則則 i 的右子女為的右子女為2*i+1 若若 i 為奇數(shù)為奇數(shù), 且且i != 1, 則其左兄弟為則其左兄弟為i-1, 若若 若若 i 為偶數(shù)為偶數(shù), 且且i != n, 則其右兄弟為則其右兄弟為i+1 1 23 4 8 567 910 2121 二叉樹的抽象數(shù)

16、據(jù)類型二叉樹的抽象數(shù)據(jù)類型 template class BinaryTree /對象: 結(jié)點(diǎn)的有限集合, 二叉樹是有序樹 public: BinaryTree ();/構(gòu)造函數(shù) BinaryTree (BinTreeNode *lch, BinTreeNode *rch, T item); /構(gòu)造函數(shù), 以item為根, lch和rch為左、右子 /樹構(gòu)造一棵二叉樹 int Height ();/求樹深度或高度 int Size ();/求樹中結(jié)點(diǎn)個數(shù) 2222 bool IsEmpty ();/判二叉樹空否？ BinTreeNode *Parent (BinTreeNode *t); /求

17、結(jié)點(diǎn) t 的雙親 BinTreeNode *LeftChild (BinTreeNode *t); /求結(jié)點(diǎn) t 的左子女 BinTreeNode *RightChild (BinTreeNode *t); /求結(jié)點(diǎn) t 的右子女 bool Insert (T item);/在樹中插入新元素 bool Remove (T item);/在樹中刪除元素 bool Find (T/判斷item是否在樹中 bool getData (T/取得結(jié)點(diǎn)數(shù)據(jù) 2323 BinTreeNode *getRoot ();/取根 void preOrder (void (*visit) (BinTreeNode

18、*t); /前序遍歷, visit是訪問函數(shù) void inOrder (void (*visit) (BinTreeNode *t); /中序遍歷, visit是訪問函數(shù) void postOrder (void (*visit) (BinTreeNode *t); /后序遍歷, (*visit)是訪問函數(shù) void levelOrder (void (*visit)(BinTreeNode *t); /層次序遍歷, visit是訪問函數(shù) ; 2424 正則二叉樹正則二叉樹 理想平衡二叉樹理想平衡二叉樹 滿的滿的 如果每個結(jié)點(diǎn)的出度恰好等于 2或0，該根樹稱為 正則二叉正則二叉 樹樹，它不存

19、在子樹個數(shù)為1的 結(jié)點(diǎn)。 平衡二叉樹（平衡二叉樹（Balanced Binary TreeBalanced Binary Tree） 又被稱為又被稱為AVLAVL樹（有別于樹（有別于AVLAVL算法），且算法），且 具有以下性質(zhì)：它是一具有以下性質(zhì)：它是一 棵空樹或它的左棵空樹或它的左 右兩個子樹的高度差的絕對值不超過右兩個子樹的高度差的絕對值不超過1 1， 并且左右兩個子樹都是一棵平衡二叉樹并且左右兩個子樹都是一棵平衡二叉樹。 理想平衡二叉樹：理想平衡二叉樹：除最底層外其他各層除最底層外其他各層 都是滿的都是滿的 2525 完全二叉樹 一般二叉樹 的順序表示 的順序表示 二叉樹的順序表示二叉

20、樹的順序表示 1 1 2 3 4 5 6 7 8 9 10 14 1 2 3 4 6 7 8 9 12 14 2 4 8910 567 3 1 23 764 8912 5 10 1113 當(dāng)二叉樹的大小和形態(tài)不發(fā)生劇烈的動當(dāng)二叉樹的大小和形態(tài)不發(fā)生劇烈的動 態(tài)變化時，可以采用數(shù)組方式來存儲。態(tài)變化時，可以采用數(shù)組方式來存儲。 但同時需注意要反映各結(jié)點(diǎn)在二叉樹中但同時需注意要反映各結(jié)點(diǎn)在二叉樹中 的位置及相互關(guān)系，因此必須適當(dāng)安排的位置及相互關(guān)系，因此必須適當(dāng)安排 各結(jié)點(diǎn)的存儲次序。各結(jié)點(diǎn)的存儲次序。 2626 1 3 7 15 31 極端情形極端情形: 只有右單支的二叉樹只有右單支的二叉樹 1

21、3715 31 2727 n二叉樹結(jié)點(diǎn)定義：每個結(jié)點(diǎn)有二叉樹結(jié)點(diǎn)定義：每個結(jié)點(diǎn)有3個數(shù)據(jù)成員，個數(shù)據(jù)成員， data域存儲結(jié)點(diǎn)數(shù)據(jù)，域存儲結(jié)點(diǎn)數(shù)據(jù)，leftChild和和rightChild 分別存放指向左子女和右子女的指針。分別存放指向左子女和右子女的指針。 leftChild data rightChild data leftChildrightChild 二叉鏈表二叉鏈表 二叉樹的鏈表表示（二叉鏈表）二叉樹的鏈表表示（二叉鏈表） 2828 leftChild data parent rightChild parent data leftChildrightChild 三叉鏈表三叉鏈表 二

22、叉樹的鏈表表示（三叉鏈表）二叉樹的鏈表表示（三叉鏈表） n每個結(jié)點(diǎn)增加一個指向雙親的指針每個結(jié)點(diǎn)增加一個指向雙親的指針parent， 使得查找雙親也很方便。使得查找雙親也很方便。 2929 A AA BBB CCCDDD FFFEEE root rootroot 二叉樹 二叉鏈表 三叉鏈表 3030 A B CD FE root data parent leftChild rightChild 0 1 2 3 4 5 A - -1 1 - -1 B 0 2 3 C 1 - -1 - -1 D 1 4 5 E 3 - -1 - -1 F 3 - -1 - -1 3131 二叉樹的類定義二叉樹的類

23、定義 template struct BinTreeNode /二叉樹結(jié)點(diǎn)類定義 T data; /數(shù)據(jù)域 BinTreeNode *leftChild, *rightChild; /左子女、右子女鏈域 BinTreeNode () /構(gòu)造函數(shù) leftChild = NULL; rightChild = NULL; BinTreeNode (T x, BinTreeNode *l = NULL, BinTreeNode *r = NULL) data = x; leftChild = l; rightChild = r; ; 3232 template class BinaryTree /二

24、叉樹類定義 public: BinaryTree () : root (NULL) /構(gòu)造函數(shù) BinaryTree (T value) : RefValue(value), root(NULL) /構(gòu)造函數(shù) BinaryTree (BinaryTree /復(fù)制構(gòu)造函數(shù) BinaryTree () destroy(root); /析構(gòu)函數(shù) bool IsEmpty () return root = NULL; /判二叉樹空否 int Height () return Height(root); /求樹高度 int Size () return Size(root); /求結(jié)點(diǎn)數(shù) 3333 Bi

25、nTreeNode *Parent (BinTreeNode *t) return (root = NULL | root = t) ? NULL : Parent (root, t); /返回雙親結(jié)點(diǎn) BinTreeNode *LeftChild (BinTreeNode *t) return (t != NULL)？t-leftChild : NULL; /返回左子女 BinTreeNode *RightChild (BinTreeNode *t) return (t != NULL)？t-rightChild : NULL; /返回右子女 BinTreeNode *getRoot ()

26、const return root; /取根 3434 void preOrder (void (*visit) (BinTreeNode *t) preOrder (root, visit); /前序遍歷 void inOrder (void (*visit) (BinTreeNode *t) inOrder (root, visit); /中序遍歷 void postOrder (void (*visit) (BinTreeNode *t) postOrder (root, visit); /后序遍歷 void levelOrder (void (*visit)(BinTreeNode *

27、t); /層次序遍歷 int Insert (const T item); /插入新元素 BinTreeNode *Find (T item) const; /搜索 3535 protected: BinTreeNode *root; /二叉樹的根指針 T RefValue; /數(shù)據(jù)輸入停止標(biāo)志 void CreateBinTree (istream /從文件讀入建樹 bool Insert (BinTreeNode * /插入 void destroy (BinTreeNode * /刪除 bool Find (BinTreeNode *subTree, T /查找 3636 BinTree

28、Node *Copy (BinTreeNode *r); /復(fù)制 int Height (BinTreeNode *subTree); /返回樹高度 int Size (BinTreeNode *subTree); /返回結(jié)點(diǎn)數(shù) BinTreeNode *Parent (BinTreeNode * subTree, BinTreeNode *t); /返回父結(jié)點(diǎn) BinTreeNode *Find (BinTreeNode * subTree, T /搜尋x 3737 void Traverse (BinTreeNode *subTree, ostream /前序遍歷輸出 void preOr

29、der (BinTreeNode /前序遍歷 void inOrder (BinTreeNode /中序遍歷 void postOrder (BinTreeNode /后序遍歷 3838 friend istream /重載操作：輸入 friend ostream /重載操作：輸出 ; template BinTreeNode *BinaryTree: Parent (BinTreeNode *subTree, BinTreeNode *t) 部分成員函數(shù)的實(shí)現(xiàn)部分成員函數(shù)的實(shí)現(xiàn) 3939 /私有函數(shù): 從結(jié)點(diǎn) subTree 開始, 搜索結(jié)點(diǎn) t 的雙 /親, 若找到則返回雙親結(jié)點(diǎn)地址, 否

30、則返回NULL if (subTree = NULL) return NULL; if (subTree-leftChild = t | subTree-rightChild = t ) return subTree;/找到, 返回父結(jié)點(diǎn)地址 BinTreeNode *p; if (p = Parent (subTree-leftChild, t) != NULL) return p; /遞歸在左子樹中搜索 else return Parent (subTree-rightChild, t); /遞歸在左子樹中搜索 ; 4040 template void BinaryTree: destro

31、y (BinTreeNode * subTree) /私有函數(shù): 刪除根為subTree的子樹 if (subTree != NULL) destroy (subTree-leftChild); /刪除左子樹 destroy (subTree-rightChild); /刪除右子樹 delete subTree; /刪除根結(jié)點(diǎn) ; 4141 template istream /建立二叉樹 return in; ; 4242 二叉樹遍歷二叉樹遍歷 n二叉樹的遍歷就是按某種次序訪問樹中的結(jié)點(diǎn)，二叉樹的遍歷就是按某種次序訪問樹中的結(jié)點(diǎn)， 要求每個結(jié)點(diǎn)訪問一次且僅訪問一次。要求每個結(jié)點(diǎn)訪問一次且僅訪問

32、一次。 n設(shè)設(shè)訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn)記作記作 V 遍歷根的左子樹遍歷根的左子樹記作記作 L 遍歷根的右子樹遍歷根的右子樹記作記作 R n則可能的遍歷次序有則可能的遍歷次序有 前序前序 VLR 鏡像鏡像 VRL 中序中序 LVR 鏡像鏡像 RVL 后序后序 LRV 鏡像鏡像 RLV 4343 中序遍歷二叉樹算法的框架是：中序遍歷二叉樹算法的框架是： n若二叉樹為空，則空操作；若二叉樹為空，則空操作； n否則否則 u中序遍歷左子樹中序遍歷左子樹 (L)； u訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) (V)； u中序遍歷右子樹中序遍歷右子樹 (R)。 遍歷結(jié)果遍歷結(jié)果 a + b * c - d - e / f 中序遍歷

33、中序遍歷 (Inorder Traversal)(Inorder Traversal) 4444 二叉樹遞歸的中序遍歷算法二叉樹遞歸的中序遍歷算法 template void BinaryTree:InOrder (BinTreeNode * subTree, void (*visit) (BinTreeNode *t) if (subTree != NULL) InOrder (subTree-leftChild, visit); /遍歷左子樹 visit (subTree);/訪問根結(jié)點(diǎn) InOrder (subTree-rightChild, visit); /遍歷右子樹 ; 4545

34、4646 前序遍歷二叉樹算法的框架是：前序遍歷二叉樹算法的框架是： n若二叉樹為空，則空操作；若二叉樹為空，則空操作； n否則否則 u訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) (V)； u前序遍歷左子樹前序遍歷左子樹 (L)； u前序遍歷右子樹前序遍歷右子樹 (R)。 遍歷結(jié)果遍歷結(jié)果 - + a * b - c d / e f 前序遍歷前序遍歷 (Preorder Traversal)(Preorder Traversal) 4747 二叉樹遞歸的前序遍歷算法二叉樹遞歸的前序遍歷算法 template void BinaryTree:PreOrder (BinTreeNode * subTree, void (

35、*visit) (BinTreeNode *t) if (subTree != NULL) visit (subTree);/訪問根結(jié)點(diǎn) PreOrder (subTree-leftChild, visit);/遍歷左子樹 PreOrder (subTree-rightChild, visit);/遍歷右子樹 ; 4848 后序遍歷二叉樹算法的框架是：后序遍歷二叉樹算法的框架是： n若二叉樹為空，則空操作；若二叉樹為空，則空操作； n否則否則 u后序遍歷左子樹后序遍歷左子樹 (L)； u后序遍歷右子樹后序遍歷右子樹 (R)； u訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) (V)。 遍歷結(jié)果遍歷結(jié)果 a b c d

36、- * + e f / - 后序遍歷后序遍歷 (Postorder Traversal)(Postorder Traversal) 4949 二叉樹遞歸的后序遍歷算法二叉樹遞歸的后序遍歷算法 template void BinaryTree:PostOrder (BinTreeNode * subTree, void (*visit) (BinTreeNode *t ) if (subTree != NULL ) PostOrder (subTree-leftChild, visit);/遍歷左子樹 PostOrder (subTree-rightChild, visit);/遍歷右子樹 vi

37、sit (subTree); /訪問根結(jié)點(diǎn) ; 5050 template int BinaryTree:Size (BinTreeNode * subTree) const /私有函數(shù)：利用二叉樹后序遍歷算法計算二叉 /樹的結(jié)點(diǎn)個數(shù) if (subTree = NULL) return 0; /空樹空樹 else return 1+Size (subTree-leftChild) + Size (subTree-rightChild); ; 應(yīng)用二叉樹遍歷的事例應(yīng)用二叉樹遍歷的事例 5151 template int BinaryTree:Height ( BinTreeNode * sub

38、Tree) const /私有函數(shù)：利用二叉樹后序遍歷算法計算二叉二叉 /樹的高度或深度 if (subTree = NULL) return 0;/空樹高度為0 else int i = Height (subTree-leftChild); int j = Height (subTree-rightChild); return (i j) ? j+1 : i+1; ; 5252 利用二叉樹利用二叉樹前序遍歷前序遍歷建立二叉樹建立二叉樹 n以遞歸方式建立二叉樹。以遞歸方式建立二叉樹。 n輸入結(jié)點(diǎn)值的順序必須對應(yīng)二叉樹結(jié)點(diǎn)前序輸入結(jié)點(diǎn)值的順序必須對應(yīng)二叉樹結(jié)點(diǎn)前序 遍歷的順序。并約定以輸入序列

39、中不可能出遍歷的順序。并約定以輸入序列中不可能出 現(xiàn)的值作為空結(jié)點(diǎn)的值以結(jié)束遞歸現(xiàn)的值作為空結(jié)點(diǎn)的值以結(jié)束遞歸, 此值在此值在 RefValue中。例如用中。例如用“”或用或用“-1”表示字表示字 符序列或正整數(shù)序列空結(jié)點(diǎn)。符序列或正整數(shù)序列空結(jié)點(diǎn)。 5353 如圖所示的二叉樹的前序遍歷順序?yàn)槿鐖D所示的二叉樹的前序遍歷順序?yàn)?A B C D E G F A B CD E G F 5454 template void BinaryTree:CreateBinTree (ifstream if ( !in.eof () ) /未讀完, 讀入并建樹 in item; /讀入根結(jié)點(diǎn)的值 if (ite

40、m != RefValue) subTree = new BinTreeNode(item); /建立根結(jié)點(diǎn) if (subTree = NULL) cerr “存儲分配錯!” leftChild); /遞歸建立左子樹 CreateBinTree (in, subTree-rightChild); /遞歸建立右子樹 else subTree = NULL; /封閉指向空子樹的指針封閉指向空子樹的指針 ; 5656 c a bc de d cc 訪問訪問 進(jìn)棧進(jìn)棧 c 左進(jìn)左進(jìn) b 訪問訪問 進(jìn)棧進(jìn)棧 d 左進(jìn)左進(jìn) 空空 退棧退棧 d 訪問訪問 左進(jìn)左進(jìn) 空空 退棧退棧 c 訪問訪問 左進(jìn)左進(jìn)

41、e 訪問訪問 左進(jìn)左進(jìn) 空空 棧空?？?結(jié)束結(jié)束 利用棧的前序遍歷非遞歸算法利用棧的前序遍歷非遞歸算法 5757 利用棧的前序遍歷非遞歸算法利用棧的前序遍歷非遞歸算法 template void BinaryTree: PreOrder (void (*visit) (BinTreeNode *t) ) stackBinTreeNode* S; BinTreeNode *p = root; S.Push (NULL); while (p != NULL) visit(p); /訪問結(jié)點(diǎn) if (p-rightChild != NULL) S.Push (p- rightChild); /預(yù)留右

42、指針在棧中 5858 if (p-leftChild != NULL) p = p-leftChild;/進(jìn)左子樹 else S.Pop(p);/左子樹為空 ; template void BinaryTree: InOrder (void (*visit) (BinTreeNode *t) stackBinTreeNode* S; 利用棧的中序遍歷非遞歸算法利用棧的中序遍歷非遞歸算法 5959 a c d e b aa d aa 左空左空退棧退棧 訪問訪問 左空左空退棧退棧 訪問訪問 退棧退棧 訪問訪問 左空左空 e c 退棧退棧訪問訪問 cc 右空右空 退棧退棧訪問訪問 ?？战Y(jié)束?？战Y(jié)束

43、a bc de 利用棧的中序遍歷非遞歸算法利用棧的中序遍歷非遞歸算法 6060 BinTreeNode *p = root; do while (p != NULL) /遍歷指針向左下移動 S.Push (p); /該子樹沿途結(jié)點(diǎn)進(jìn)棧 p = p-leftChild; if (!S.IsEmpty() /棧不空時退棧 S.Pop (p); visit (p);/退棧, 訪問 p = p-rightChild;/遍歷指針進(jìn)到右子女 while (p != NULL | !S.IsEmpty (); ; 6161 n在后序遍歷過程中所用棧的結(jié)點(diǎn)定義在后序遍歷過程中所用棧的結(jié)點(diǎn)定義 template

44、 struct stkNode BinTreeNode *ptr; /樹結(jié)點(diǎn)指針 enum tag L, R; /退棧標(biāo)記 stkNode (BinTreeNode *N = NULL) : ptr(N), tag(L) /構(gòu)造函數(shù) ; ntag = L, 表示從左子樹退回還要遍歷右子樹表示從左子樹退回還要遍歷右子樹; tag = R，表示從右子樹退回要訪問根結(jié)點(diǎn)。，表示從右子樹退回要訪問根結(jié)點(diǎn)。 ptr tagL,R 利用棧的后序遍歷非遞歸算法利用棧的后序遍歷非遞歸算法 6262 aL bL aL bR aL dL bR aL dR bR aL bR aLaLaR eL cL aR eR c

45、L aR cL aR cR aRaR a bc de 6363 后序遍歷的非遞歸算法后序遍歷的非遞歸算法 template void BinaryTree: PostOrder (void (*visit) (BinTreeNode *t) StackstkNode S; stkNode w; BinTreeNode * p = root; /p是遍歷指針 do while (p != NULL) w.ptr = p; w.tag = L; S.Push (w); p = p-leftChild; int continue1 = 1; /繼續(xù)循環(huán)標(biāo)記, 用于R 6464 while (cont

46、inue1 p = w.ptr; switch (w.tag) /判斷棧頂?shù)膖ag標(biāo)記 case L: w.tag = R; S.Push (w); continue1 = 0; p = p-rightChild; break; case R: visit (p); break; while (!S.IsEmpty ();/繼續(xù)遍歷其他結(jié)點(diǎn) cout endl; ; 6565 n層次序遍歷二叉樹就是從根結(jié)點(diǎn)開始，按層次層次序遍歷二叉樹就是從根結(jié)點(diǎn)開始，按層次 逐層遍歷，如圖：逐層遍歷，如圖： 遍歷順序遍歷順序 a b c d ef 層次序遍歷二叉樹的算法層次序遍歷二叉樹的算法 6666 n這種

47、遍歷需要使用一個這種遍歷需要使用一個先進(jìn)先出的隊(duì)列先進(jìn)先出的隊(duì)列，在，在 處理上一層時，將其下一層的結(jié)點(diǎn)直接進(jìn)到處理上一層時，將其下一層的結(jié)點(diǎn)直接進(jìn)到 隊(duì)列（的隊(duì)尾）。在上一層結(jié)點(diǎn)遍歷完后，隊(duì)列（的隊(duì)尾）。在上一層結(jié)點(diǎn)遍歷完后， 下一層結(jié)點(diǎn)正好處于隊(duì)列的隊(duì)頭，可以繼續(xù)下一層結(jié)點(diǎn)正好處于隊(duì)列的隊(duì)頭，可以繼續(xù) 訪問它們。訪問它們。 n算法是非遞歸的。算法是非遞歸的。 6767 a bc de Qa訪問訪問a, 進(jìn)隊(duì)進(jìn)隊(duì) Qa出隊(duì)出隊(duì) 訪問訪問b, 進(jìn)隊(duì)進(jìn)隊(duì) 訪問訪問c, 進(jìn)隊(duì)進(jìn)隊(duì) bc Qb出隊(duì)出隊(duì) 訪問訪問d, 進(jìn)隊(duì)進(jìn)隊(duì) cd Qc出隊(duì)出隊(duì) 訪問訪問e, 進(jìn)隊(duì)進(jìn)隊(duì) de Qd出隊(duì)出隊(duì)e Qe出隊(duì)

48、出隊(duì) 6868 層次序遍歷的（非遞歸）算法層次序遍歷的（非遞歸）算法 template void BinaryTree: levelOrder (void (*visit) (BinTreeNode *t) if (root = NULL) return; QueueBinTreeNode * Q; BinTreeNode *p = root; visit (p); Q.EnQueue (p); while (!Q.IsEmpty () Q.DeQueue (p); if (p-leftChild != NULL) 6969 visit (p-leftChild); Q.EnQueue (p-

49、leftChild); if (p-rightChild != NULL) visit (p-rightChild); Q.EnQueue (p-rightChild); ; 7070 二叉樹的計數(shù)二叉樹的計數(shù) n二叉樹遍歷的結(jié)果是將一個非線性結(jié)構(gòu)中二叉樹遍歷的結(jié)果是將一個非線性結(jié)構(gòu)中 的數(shù)據(jù)通過訪問排列到一個的數(shù)據(jù)通過訪問排列到一個線性序列線性序列中。中。 n前序序列：前序序列：a b d c e 特點(diǎn)是第一個訪問的特點(diǎn)是第一個訪問的a 一定是樹根，只要左子樹非空，后面緊跟一定是樹根，只要左子樹非空，后面緊跟 的的b 一定是根的左子女，一定是根的左子女， n中序序列：中序序列：b d a e

50、 c 特點(diǎn)是樹特點(diǎn)是樹 根根 a 把整個中序分成兩部分，把整個中序分成兩部分， a 左側(cè)子序列是根的左側(cè)子序列是根的左子樹左子樹上上 的結(jié)點(diǎn)數(shù)據(jù)，右側(cè)子序列是根的結(jié)點(diǎn)數(shù)據(jù)，右側(cè)子序列是根 的右子樹上的結(jié)點(diǎn)數(shù)據(jù)。的右子樹上的結(jié)點(diǎn)數(shù)據(jù)。 a bc de 7171 n由二叉樹的前序序列和中序序列可唯一地確由二叉樹的前序序列和中序序列可唯一地確 定一棵二叉樹。定一棵二叉樹。 n例例, 前序序列前序序列 A B H F D E C K G 和中序和中序 序列序列 H B D F A E K C G , 構(gòu)造二叉樹過構(gòu)造二叉樹過 程如下：程如下： HBDFEKCG A EKCG A B HDF 7272

51、前序序列前序序列 A B H F D E C K G KCG EKCG A B HDF EKCG A B HF D E A B HF D E A B HF D C KG 7373 n如果前序序列固定不變，給出不同的中序序如果前序序列固定不變，給出不同的中序序 列，可得到不同的二叉樹。列，可得到不同的二叉樹。 6 1 2 34 5 7 89 6 1 2 37 5 8 49 7474 n例如例如, 有有 3 個數(shù)據(jù)個數(shù)據(jù) 1, 2, 3 ，可得，可得 5 種不同的種不同的 二叉樹。它們的前序排列均為二叉樹。它們的前序排列均為 123，中序序列，中序序列 可能是可能是 321，231，213，132

52、，123。 n前序序列為前序序列為 123，中序序列為，中序序列為 312 的二叉樹不的二叉樹不 存在。存在。 1 2 3 1 2 3 1 23 1 2 3 1 2 3 7575 有有0個個, 1個個, 2個個, 3個結(jié)點(diǎn)的不同二叉樹如下個結(jié)點(diǎn)的不同二叉樹如下 b0 =1b1 =1b2 =2 b3 =5 b4 =14 7676 ! )!(2 1 1 1 1 2 nn n nn b C n n n 計算具有計算具有n n個結(jié)點(diǎn)的不同二叉樹的棵數(shù)個結(jié)點(diǎn)的不同二叉樹的棵數(shù) 1 1 0 1 n i inin bbb 5 123 456 4 1 13 13 6 3 C b 14 1234 5678 5

53、1 14 14 8 4 C b 7777 線索化二叉樹線索化二叉樹 (Threaded Binary Tree)(Threaded Binary Tree) n又稱為穿線樹。又稱為穿線樹。 n通過二叉樹的遍歷，可將二叉樹中所有結(jié)點(diǎn)通過二叉樹的遍歷，可將二叉樹中所有結(jié)點(diǎn) 的數(shù)據(jù)排列在一個線性序列中，可以找到某的數(shù)據(jù)排列在一個線性序列中，可以找到某 數(shù)據(jù)在這種排列下它的前驅(qū)和后繼。數(shù)據(jù)在這種排列下它的前驅(qū)和后繼。 n希望不必每次都通過遍歷找出這樣的線性序希望不必每次都通過遍歷找出這樣的線性序 列。只要事先做預(yù)處理，列。只要事先做預(yù)處理，將某種遍歷順序下將某種遍歷順序下 的前驅(qū)、后繼關(guān)系記在樹的存儲

54、結(jié)構(gòu)中的前驅(qū)、后繼關(guān)系記在樹的存儲結(jié)構(gòu)中，以，以 后就可以高效地找出某結(jié)點(diǎn)的前驅(qū)、后繼。后就可以高效地找出某結(jié)點(diǎn)的前驅(qū)、后繼。 7878 線索線索 (Thread)(Thread) 增加前驅(qū)增加前驅(qū)Pred指針和后繼指針和后繼Succ指針的二叉樹指針的二叉樹 pred leftChild data rightChild succ a bc de pred pred pred succ succ succ D A E B C root pred pred pred predsucc succ succ succ 7979 n這種設(shè)計的缺點(diǎn)是每個結(jié)點(diǎn)增加兩個指針，這種設(shè)計的缺點(diǎn)是每個結(jié)點(diǎn)增加兩個指

55、針， 當(dāng)結(jié)點(diǎn)數(shù)很大時存儲消耗較大。當(dāng)結(jié)點(diǎn)數(shù)很大時存儲消耗較大。 n改造樹結(jié)點(diǎn)，將改造樹結(jié)點(diǎn)，將 pred 指針和指針和 succ 指針壓縮指針壓縮 到到 leftChild 和和 rightChild 的空閑指針中，并的空閑指針中，并 增設(shè)兩個標(biāo)志增設(shè)兩個標(biāo)志 ltag 和和 rtag，指明指針是指示，指明指針是指示 子女還是前驅(qū)后繼。后者稱為線索。子女還是前驅(qū)后繼。后者稱為線索。 nltag (或或rtag) = 0，表示相應(yīng)指針指示左子女，表示相應(yīng)指針指示左子女 （或右子女結(jié)點(diǎn)）；當(dāng)（或右子女結(jié)點(diǎn)）；當(dāng)ltag (或或rtag) = 1, 表示表示 相應(yīng)指針為前驅(qū)（或后繼）線索。相應(yīng)指針為

56、前驅(qū)（或后繼）線索。 leftChild ltag data rtag rightChild 8080 leftChild ltag data rtag rightChild a bc de pred pred pred succ succ succ D A E B C root pred pred succ succ 00 0011 1111 線索化二叉樹及其鏈表表示線索化二叉樹及其鏈表表示 8181 線索化二叉樹的類定義線索化二叉樹的類定義 template struct ThreadNode /線索二叉樹的結(jié)點(diǎn)類 int ltag, rtag; /線索標(biāo)志 ThreadNode *lef

57、tChild, *rightChild; /線索或子女指針 T data; /結(jié)點(diǎn)數(shù)據(jù) ThreadNode ( const T item) /構(gòu)造函數(shù) : data(item), leftChild (NULL), rightChild (NULL), ltag(0), rtag(0) ; 8282 template class ThreadTree /線索化二叉樹類 protected: ThreadNode *root;/樹的根指針,注:不加頭結(jié)點(diǎn) void createInThread (ThreadNode *current, ThreadNode * /中序遍歷建立線索二叉樹 Th

58、readNode *parent (ThreadNode *t); /尋找結(jié)點(diǎn)t的雙親結(jié)點(diǎn) public: ThreadTree () : root (NULL) /構(gòu)造函數(shù) 8383 void createInThread(); /建立中序線索二叉樹 ThreadNode *First (ThreadNode *current); /尋找中序下第一個結(jié)點(diǎn) ThreadNode *Last (ThreadNode *current); /尋找中序下最后一個結(jié)點(diǎn) ThreadNode *Next (ThreadNode *current); /尋找結(jié)點(diǎn)在中序下的后繼結(jié)點(diǎn) ThreadNode *

59、Prior (ThreadNode *current); /尋找結(jié)點(diǎn)在中序下的前驅(qū)結(jié)點(diǎn) ; 8484 通過中序遍歷建立中序線索化二叉樹通過中序遍歷建立中序線索化二叉樹 template void ThreadTree:createInThread () ThreadNode *pre = NULL; /前驅(qū)結(jié)點(diǎn)指針 if (root != NULL) /非空二叉樹, 線索化 createInThread (root, pre); /中序遍歷線索化二叉樹 pre-rightChild = NULL; pre-rtag = 1; /后處理中序最后一個結(jié)點(diǎn) ; 8585 template void

60、ThreadTree: createInThread (ThreadNode *current, ThreadNode * createInThread (current-leftChild, pre); /遞歸, 左子樹線索化 if (current-leftChild = NULL) /建立當(dāng)前結(jié)點(diǎn)的前驅(qū)線索 current-leftChild = pre; current-ltag = 1; 8686 if (pre != NULL pre-rtag = 1; pre = current; /前驅(qū)跟上,當(dāng)前指針向前遍歷 createInThread (current-rightChild