數(shù)據(jù)結(jié)構(gòu)與算法

1、數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 1數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 2定義定義 一一1、一個(gè)結(jié)點(diǎn)、一個(gè)結(jié)點(diǎn)x組成的集組成的集x是一株樹，這個(gè)結(jié)點(diǎn)是一株樹，這個(gè)結(jié)點(diǎn)x也是這也是這 株樹的根。株樹的根。2、假設(shè)、假設(shè)x是一個(gè)結(jié)點(diǎn)，是一個(gè)結(jié)點(diǎn)，T1，T2，Tk是是k株互不相交的株互不相交的 樹，我們可以構(gòu)造一株新樹：令樹，我們可以構(gòu)造一株新樹：令x為根，并有為根，并有k條邊由條邊由 x指向樹指向樹T1，T2，Tk。這些邊也叫做分支，。這些邊也叫做分支，T1，T2， ，Tk

2、稱作根稱作根x的樹之子樹（的樹之子樹（SubTree）。）。樹是樹是n（0）個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹中：）個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹中： 1、有且僅有特定的稱為根（、有且僅有特定的稱為根（Root）的結(jié)點(diǎn)；）的結(jié)點(diǎn)； 2、當(dāng)、當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為時(shí)，其余結(jié)點(diǎn)可分為m（0）個(gè)互不相交的有限）個(gè)互不相交的有限 集集T1，T2，Tm，其中每一個(gè)集合本身又是一棵樹，其中每一個(gè)集合本身又是一棵樹， 并且稱為根的子樹（并且稱為根的子樹（ SubTree ）。）。定義定義 二二數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 3定義定義 三三

3、 T = （ D，R ）D：具有相同類型的數(shù)據(jù)元素的集合。：具有相同類型的數(shù)據(jù)元素的集合。R：若：若 D 為空集，則稱為空樹；為空集，則稱為空樹； 若若 D 僅含一個(gè)數(shù)據(jù)元素，則僅含一個(gè)數(shù)據(jù)元素，則 R 為空集，否則為空集，否則 R = H ，H 是是 如下的二元關(guān)系：如下的二元關(guān)系：1、在、在 D 中存在唯一的稱為根的數(shù)據(jù)元素中存在唯一的稱為根的數(shù)據(jù)元素 root ，它在關(guān)系，它在關(guān)系 H 下下 無前驅(qū)；無前驅(qū)；2、若、若 D - root ，則存在，則存在D- root 的一個(gè)劃分的一個(gè)劃分D1，D2， Dm（m 0），對(duì)任意），對(duì)任意 j k（1 j，k m）有）有DjDk=， 且對(duì)任意

4、的且對(duì)任意的 i（1 i m），唯一存在數(shù)據(jù)元素），唯一存在數(shù)據(jù)元素 x i Di， 有有 H;3、對(duì)應(yīng)于、對(duì)應(yīng)于 D - root 的劃分，的劃分，H - , , 有唯一的一個(gè)劃分有唯一的一個(gè)劃分H1，H2，Hm （m0）,對(duì)任意對(duì)任意jk（1j，km）有）有HjHk,且對(duì)任意的且對(duì)任意的i （1 i m），），Hi是是Di上的二元關(guān)系，（上的二元關(guān)系，（Di，Hi）是一棵符合）是一棵符合 本定義的樹，稱為根本定義的樹，稱為根root的子樹。的子樹。數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 4ABCDEFGHIJKLM圖一圖一第1層第2

5、層第3層第4層第5層ABCDEFGHIJKLM圖二圖二樹高為5常用術(shù)語(yǔ)：常用術(shù)語(yǔ)：結(jié)點(diǎn)結(jié)點(diǎn)度度葉（終端結(jié)點(diǎn)）葉（終端結(jié)點(diǎn)）非終端結(jié)點(diǎn)非終端結(jié)點(diǎn)分支分支 路長(zhǎng)路長(zhǎng)父親父親 雙親雙親兒子兒子 兄弟兄弟子孫子孫 祖先祖先層層 結(jié)點(diǎn)的高結(jié)點(diǎn)的高樹的高（深度）樹的高（深度）數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 5有序樹有序樹 & & 無序樹無序樹ABCACB森林森林forest： 是是 n 0 株互不相交的樹的集合。株互不相交的樹的集合。定義一定義一 二元樹是有限個(gè)結(jié)點(diǎn)的集合，這個(gè)集合或者是空集，二元樹是有限個(gè)結(jié)點(diǎn)的集合，這個(gè)集

6、合或者是空集，或者是由一個(gè)根結(jié)點(diǎn)和兩株互不相交的二元樹組成，其中一或者是由一個(gè)根結(jié)點(diǎn)和兩株互不相交的二元樹組成，其中一株叫根的做左子樹，另一棵叫做根的右子樹。株叫根的做左子樹，另一棵叫做根的右子樹。4.2.1 二元樹的定義和基本性質(zhì)二元樹的定義和基本性質(zhì)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 64.2.1 二元樹的定義和基本性質(zhì)二元樹的定義和基本性質(zhì)定義二定義二 Binary Tree = ( D , R )D：指數(shù)據(jù)對(duì)象，是由相同類型的數(shù)據(jù)元素組成的集合。：指數(shù)據(jù)對(duì)象，是由相同類型的數(shù)據(jù)元素組成的集合。R：為數(shù)據(jù)元素間的關(guān)系：為數(shù)據(jù)元

7、素間的關(guān)系： 若若D，則，則R= ，稱，稱Binary tree 為空樹；為空樹； 若若D；則；則R=H，H是如下二元關(guān)系：是如下二元關(guān)系：在在D中存在唯一的稱為根的數(shù)據(jù)元素中存在唯一的稱為根的數(shù)據(jù)元素 root，它在關(guān)系，它在關(guān)系H下下 無前驅(qū)；無前驅(qū)；若若D- root ，則存在，則存在D-root=Dl，Dr，且，且DlDr=；若若Dl ，則，則Dl中存在唯一的元素中存在唯一的元素xl，H，且存，且存 在在Dl上的關(guān)系上的關(guān)系HlH；若；若Dr ，則，則Dr中存在唯一的元素中存在唯一的元素 xr，H，且存在，且存在Dr上的關(guān)系上的關(guān)系HrH； H=， ，Hl，Hr；（Dl，Hl）是符合本

8、定義的二元樹，稱為根的左子樹；）是符合本定義的二元樹，稱為根的左子樹； （Dr，Hr）是符合本定義的二元樹，稱為根的右子樹；）是符合本定義的二元樹，稱為根的右子樹；數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 74.2.1 二元樹的定義和基本性質(zhì)二元樹的定義和基本性質(zhì)二元樹的性質(zhì)：二元樹的性質(zhì)：性質(zhì)性質(zhì)1：在二元樹中第：在二元樹中第 i 層的結(jié)點(diǎn)數(shù)最多為層的結(jié)點(diǎn)數(shù)最多為2i-1（i 1）。）。性質(zhì)性質(zhì)2：高度為：高度為k的二元樹其結(jié)點(diǎn)總數(shù)最多為的二元樹其結(jié)點(diǎn)總數(shù)最多為2k1（ k 1）性質(zhì)性質(zhì)3：對(duì)任意的非空二元樹：對(duì)任意的非空二元樹 T ，

9、如果葉結(jié)點(diǎn)的個(gè)數(shù)為，如果葉結(jié)點(diǎn)的個(gè)數(shù)為 n0，而，而 其度為其度為 2 的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為 n2，則：，則： n0 = n2 + 1定義定義 深度為深度為k且有且有2k 1個(gè)結(jié)點(diǎn)的二元樹稱為個(gè)結(jié)點(diǎn)的二元樹稱為滿二元樹滿二元樹。層序編號(hào)：對(duì)滿二元樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)。從根結(jié)點(diǎn)開始，層序編號(hào)：對(duì)滿二元樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)。從根結(jié)點(diǎn)開始， 從上而下，自左至右。從上而下，自左至右。定義定義 深度為深度為 k 的，由的，由n個(gè)結(jié)點(diǎn)的二元樹，當(dāng)且僅當(dāng)其每個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)的二元樹，當(dāng)且僅當(dāng)其每個(gè)結(jié)點(diǎn) 都與深度為都與深度為 k 的滿二元樹中編號(hào)從的滿二元樹中編號(hào)從 1 至至 n 的結(jié)點(diǎn)一一對(duì)的結(jié)點(diǎn)一一對(duì) 應(yīng)，稱

10、之為應(yīng)，稱之為完全二元樹完全二元樹。數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 84.2.1 二元樹的定義和基本性質(zhì)二元樹的定義和基本性質(zhì)二元樹的性質(zhì)二元樹的性質(zhì)(續(xù)續(xù))：性質(zhì)性質(zhì)4 具有具有 n 個(gè)結(jié)點(diǎn)的完全二元樹的深度為個(gè)結(jié)點(diǎn)的完全二元樹的深度為 log2n + 1。性質(zhì)性質(zhì)5 如果對(duì)一棵有如果對(duì)一棵有 n 個(gè)結(jié)點(diǎn)的二元樹的結(jié)點(diǎn)按層序編號(hào)，個(gè)結(jié)點(diǎn)的二元樹的結(jié)點(diǎn)按層序編號(hào)， 則對(duì)任一結(jié)點(diǎn)則對(duì)任一結(jié)點(diǎn) i 有：有： 如果如果 i = 1，則結(jié)點(diǎn)，則結(jié)點(diǎn) i 是二元樹的根，無雙親；如果是二元樹的根，無雙親；如果 i 1 ，則其雙親結(jié)點(diǎn)是，則其

11、雙親結(jié)點(diǎn)是 i / 2 ； 如果如果 2 i n，則結(jié)點(diǎn)，則結(jié)點(diǎn) i 無左孩子結(jié)點(diǎn)，否則其左孩子無左孩子結(jié)點(diǎn)，否則其左孩子 結(jié)點(diǎn)是結(jié)點(diǎn)是 2 i ； 如果如果 2 i + 1 n，則結(jié)點(diǎn)，則結(jié)點(diǎn) i 無右孩子結(jié)點(diǎn)，否則其右無右孩子結(jié)點(diǎn)，否則其右 孩子結(jié)點(diǎn)是孩子結(jié)點(diǎn)是 2 i + 1。數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 94.2.1 二元樹的定義和基本性質(zhì)二元樹的定義和基本性質(zhì)二元樹的遍歷二元樹的遍歷DLR遍歷：根據(jù)原則，按照一定的順序訪問遍歷：根據(jù)原則，按照一定的順序訪問 二元樹中的每一個(gè)結(jié)點(diǎn)，使每個(gè)二元樹中的每一個(gè)結(jié)點(diǎn)，使每個(gè) 結(jié)

12、點(diǎn)只能被訪問一次。結(jié)點(diǎn)只能被訪問一次。 根（根（D）、左孩子（）、左孩子（L）和右孩子（）和右孩子（R）三個(gè)結(jié)點(diǎn)可能出現(xiàn)）三個(gè)結(jié)點(diǎn)可能出現(xiàn)的順序有：的順序有： DLR DRL LDR LRD RLD RDL原則：左孩子結(jié)點(diǎn)一定原則：左孩子結(jié)點(diǎn)一定 要在右孩子結(jié)點(diǎn)要在右孩子結(jié)點(diǎn) 之前訪問。之前訪問。要討論的三種操作分別為：要討論的三種操作分別為：先根順序先根順序DLR， 中根順序中根順序LDR， 后根順序后根順序LRD數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 10二元樹的遍歷二元樹的遍歷先根順序遍歷二元樹：先根順序遍歷二元樹： 若二元樹非空

13、則：若二元樹非空則： 訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)； 先根順序遍歷左子樹；先根順序遍歷左子樹； 先根順序遍歷右子樹；先根順序遍歷右子樹； ； 中根順序遍歷二元樹：中根順序遍歷二元樹： 若二元樹非空則：若二元樹非空則： 中根順序遍歷左子樹；中根順序遍歷左子樹； 訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)； 中根順序遍歷右子樹；中根順序遍歷右子樹； ； 后根順序遍歷二元樹：后根順序遍歷二元樹： 若二元樹非空則：若二元樹非空則： 后根順序遍歷左子樹；后根順序遍歷左子樹； 后根順序遍歷右子樹；后根順序遍歷右子樹； 訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)； ； 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slid

14、e. 4 - 114.2.2 抽象數(shù)據(jù)型二元樹抽象數(shù)據(jù)型二元樹操作： EMPTY ( BT ) ; ISEMPTY ( BT ) ; CREATEBT ( V, LT , RT ) ; LCHILD ( BT ) ; RCHILD ( BT ) ; DATA ( BT ) ;例例1-1：寫一個(gè)遞歸函數(shù)，按：寫一個(gè)遞歸函數(shù)，按 先根先根順序列出二元樹順序列出二元樹 中每個(gè)結(jié)點(diǎn)的中每個(gè)結(jié)點(diǎn)的DATA 域之值。域之值。Void PREORDER ( BT )BTREE BT ; if ( ! ISEMPTY ( BT ) ) visit ( DATA ( BT ) ) ; PREORDER ( LC

15、HILD ( BT ) ) ; PREORDER ( RCHILD ( BT ) ) ; 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 12例例1-2：寫一個(gè)遞歸函數(shù)，按：寫一個(gè)遞歸函數(shù)，按 中根中根順序列出二元樹順序列出二元樹 中每個(gè)結(jié)點(diǎn)的中每個(gè)結(jié)點(diǎn)的DATA 域之值。域之值。Void INORDER ( BT )BTREE BT ; if ( ! ISEMPTY ( BT ) ) INORDER ( LCHILD ( BT ) ) ; visit ( DATA ( BT ) ) ; INORDER ( RCHILD ( BT ) ) ;

16、例例1-3：寫一個(gè)遞歸函數(shù)，按：寫一個(gè)遞歸函數(shù)，按 后根后根順序列出二元樹順序列出二元樹 中每個(gè)結(jié)點(diǎn)的中每個(gè)結(jié)點(diǎn)的DATA 域之值。域之值。Void POSTORDER ( BT )BTREE BT ; if ( ! ISEMPTY ( BT ) ) POSTORDER ( LCHILD ( BT ) ) ; POSTORDER ( RCHILD ( BT ) ) ; visit ( DATA ( BT ) ) ; 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 13ABCDEFGHIJKLM例二元樹的遍歷的非二元樹的遍歷的非遞歸過程遞歸過程先

17、序： A B D J H E C F I G K L M中序： J DH B E A F I C G L K M后序： J H D E B I F L M K G C AVoid INORDER ( BT )BTREE BT ; if ( ! ISEMPTY ( BT ) ) INORDER ( LCHILD ( BT ) ) ; visit ( DATA ( BT ) ) ; INORDER ( RCHILD ( BT ) ) ; No. 指針指針BT棧棧輸出輸出1A #2B #A3D #AB4J #ABD5#ABDJ J6#ABD D7H #AB8#ABH H9#AB B10 E #A11

18、#AE E12 #A A13 C #14 F #C15 #CF F16 I #C17 #CI I18 #C C19 G #20 #G G21 K #22 L #K23 #KL L24 #K K25 M #26 #M M27 #結(jié)束結(jié)束算法算法:Loop: if (BT 非空) 進(jìn)棧; 左一步; else 退棧; 右一步;數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu): 設(shè)棧S: 用以保留 當(dāng)前結(jié)點(diǎn);數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 14二元樹的遍歷的二元樹的遍歷的非遞歸過程非遞歸過程Void NINORDER( BT )BTREE BT; STACK S ;

19、BTREE T ; MAKENULL( S ) ; T = BT ; while ( !ISEMPTY( T ) | EMPTY ( S ) ) if ( !ISEMPTY ( T ) ) PUSH( T ,S ); T = T LCHILD ( T ) ; else T = TOP ( S ) ; POP ( S ) ; visit( DATA( T ) ) ; T = T RCHILD ( T ) ; 進(jìn)棧; 左走一步退棧; 右走一步數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 15先序遍歷非遞歸算法算法算法:Loop: if (BT 非

20、空) 輸出; 進(jìn)棧; 左一步; else 退棧; 右一步;中序遍歷非遞歸算法算法算法:Loop: if (BT 非空) 進(jìn)棧; 左一步; else 退棧; 輸出; 右一步;先序遍歷非遞歸算法算法算法:Loop: if (BT 非空) 進(jìn)棧; 左一步; else 當(dāng)棧頂指針 所指結(jié)點(diǎn)的 右子樹不存 在或已訪問, 退棧并訪問; 否則右一步; ;數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 164.2.3 二元樹的表示二元樹的表示 a、完全（或滿）二元樹、完全（或滿）二元樹根據(jù)性質(zhì)根據(jù)性質(zhì)5，如已知某結(jié)點(diǎn)的層序編號(hào)，如已知某結(jié)點(diǎn)的層序編號(hào)i,則可求

21、得該結(jié)點(diǎn)的則可求得該結(jié)點(diǎn)的雙親結(jié)點(diǎn)、左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)。雙親結(jié)點(diǎn)、左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)。ABCDEFGIHJA B C D E F G1 2 3 4 5 6 7 8 9 10H IJ采用一維數(shù)組，按層序順序依次存儲(chǔ)二元樹采用一維數(shù)組，按層序順序依次存儲(chǔ)二元樹的每一個(gè)結(jié)點(diǎn)。如下圖所示：的每一個(gè)結(jié)點(diǎn)。如下圖所示：數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 17b、一般二元樹、一般二元樹A B C $ E $ G1 2 3 4 5 6 7 8 9 10$ $ J根據(jù)性質(zhì)根據(jù)性質(zhì)5，如已知某結(jié)點(diǎn)的層序編號(hào)，如已知某結(jié)點(diǎn)的層序編號(hào)i,則可求得該

22、結(jié)點(diǎn)的則可求得該結(jié)點(diǎn)的雙親結(jié)點(diǎn)、左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)，然后檢測(cè)其值是否雙親結(jié)點(diǎn)、左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)，然后檢測(cè)其值是否為虛設(shè)的特殊結(jié)點(diǎn)為虛設(shè)的特殊結(jié)點(diǎn)$。通過虛設(shè)部分結(jié)點(diǎn)，使其變成相應(yīng)的完全二元樹。通過虛設(shè)部分結(jié)點(diǎn)，使其變成相應(yīng)的完全二元樹。ABC$E$G$JABCEGJ數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 18 A B C D E F G H I J lchildrchilddataStruct node Struct node *lchild ; Struct node *rchild ; datatype data ; ;T

23、ypedef struct node * BTREE ;ABCDEFGIJH例: ( P102 )BTREE CREATEBT(v , ltree , rtree )datatype v ; BTREE ltree , rtree ; BTREE root ; root = new node ; root data = v ; root lchild = ltree ; root rchild = rtree ; return root ; 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 19證明：證明：n 個(gè)結(jié)點(diǎn)的二元樹中，共有個(gè)結(jié)點(diǎn)的二元樹

24、中，共有 n+1 個(gè)空鏈接域。個(gè)空鏈接域。證：設(shè)其空鏈域數(shù)為證：設(shè)其空鏈域數(shù)為 x 分支數(shù)分支數(shù) B入入 = n 1 B出出=2 n x B入入 = B出出 n 1 = 2n x 得出得出 x = n 1 ABCDEFGHIJKLM結(jié)點(diǎn)總數(shù)：結(jié)點(diǎn)總數(shù)：13空鏈域的個(gè)數(shù)：空鏈域的個(gè)數(shù)：14數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 20按先序序列建立二元樹的左右鏈結(jié)構(gòu)按先序序列建立二元樹的左右鏈結(jié)構(gòu).如由圖所示二元樹如由圖所示二元樹,輸入輸入: ABDH#I#E#CF#J#G#其中其中:#表示空表示空ABCDEFGIJHStatus Crea

25、teBtree( BTREE &T ) cin ch ; if ( ch = ) T = NULL ; else if ( !(T = new BTREE ) ) exit ; T data = ch ; CreateBtree ( T lchild ) ; CreateBtree ( T rchild ) ; return OK ; 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 21一棵二元樹的先序、中序和后序序列分別如下，其中一部分未顯示出來，試求出空格處的內(nèi)容，并畫出該二元樹。 先序：_B_F_ICEH_G 中序：D_KFIA_

26、EJC_ 后序：_K_FBHJ_G_A 先序：ABDFKICEHJG 中序：DBKFIAHEJCG 后序：DKIFBHJEGCA ABCDEFGHIJK數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 22二元樹中序序列為：ABCEFGHD，后序序列為：ABFHGEDC畫出此二元樹ABCDEFGH數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 23完全二元樹的某結(jié)點(diǎn)若無左孩子結(jié)點(diǎn)，則它必是葉結(jié)點(diǎn)？前序遍歷和中序遍歷相同的二元樹？前序遍歷和后序遍歷相同的二元樹？中序遍歷和后序遍歷相同的二元樹？試舉出

27、：數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 24一棵有124個(gè)葉子結(jié)點(diǎn)的完全二元樹，最多有 ？ 個(gè)結(jié)點(diǎn)。n0=n2+1n=n0+n1+n2n=n1+2n0-1但在完全二元樹中，n1不是 0 就是 1只有n1=1時(shí)，n 取最大值為2n0數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 25證明任一棵滿二元樹證明任一棵滿二元樹T T中的分支數(shù)中的分支數(shù)B B滿足滿足: : B B=2(n=2(n0 0-1) -1) ，其中，其中 n n0 0為葉子結(jié)點(diǎn)數(shù)為葉子結(jié)點(diǎn)數(shù)證明：滿二元樹中不存在度為1的

28、節(jié)點(diǎn)，設(shè)度為2的結(jié)點(diǎn)數(shù)為n2則： n=n0+n2又： n=B+1所以有： B=n0+n2-1 , 而 n0=n2+1, n2=n0-1 B=n0+n0-1-1=2(n0-1)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 26具有具有n個(gè)結(jié)點(diǎn)的滿二元樹，其葉子結(jié)點(diǎn)的個(gè)數(shù)為多少？個(gè)結(jié)點(diǎn)的滿二元樹，其葉子結(jié)點(diǎn)的個(gè)數(shù)為多少？具有具有n個(gè)結(jié)點(diǎn)的完全二元樹，其葉子結(jié)點(diǎn)的個(gè)數(shù)為多少？個(gè)結(jié)點(diǎn)的完全二元樹，其葉子結(jié)點(diǎn)的個(gè)數(shù)為多少？方法一：設(shè)滿二元樹的高度為， 則根據(jù)二元樹的性質(zhì)，葉子結(jié)點(diǎn)數(shù)為2h-1 二元樹總結(jié)點(diǎn)數(shù)n=2h-1 可導(dǎo)出:h-1=(n+1)/2方

29、法二：結(jié)點(diǎn)總數(shù)：n=n0+n1+n2 但對(duì)滿二元樹，除有n0=n2+1外，還有n1=0 故有： n=n0+n0-1 n0=(n+1)/2數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 27設(shè)高為設(shè)高為h的二元樹只有度為的二元樹只有度為0和度為和度為2的結(jié)點(diǎn)，則此類二元樹的結(jié)點(diǎn)，則此類二元樹的結(jié)點(diǎn)樹至少為的結(jié)點(diǎn)樹至少為 ，至多為，至多為 。答案： 2h-1 和 2h-1數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 281、在、在n個(gè)結(jié)點(diǎn)的二元樹左右鏈表示中，有個(gè)結(jié)點(diǎn)的二元樹左右鏈表示中，有n+1

30、個(gè)空鏈域。個(gè)空鏈域。 如何利用如何利用n+1個(gè)空鏈域，使二元樹的操作更加方便。個(gè)空鏈域，使二元樹的操作更加方便。2、在二元樹左右鏈表示中，為求某個(gè)結(jié)點(diǎn)的（中序）前、在二元樹左右鏈表示中，為求某個(gè)結(jié)點(diǎn)的（中序）前 驅(qū)驅(qū) $P 或（中序）后繼或（中序）后繼 p$，每次都要從樹根開始進(jìn)行，每次都要從樹根開始進(jìn)行 查找，很不方便。查找，很不方便。若結(jié)點(diǎn)若結(jié)點(diǎn)p有左孩子，則有左孩子，則p-lchild指向其左孩子結(jié)點(diǎn)，指向其左孩子結(jié)點(diǎn)，否則令其指向其（中序）前驅(qū)。否則令其指向其（中序）前驅(qū)。若結(jié)點(diǎn)若結(jié)點(diǎn)p有右孩子，則有右孩子，則p-rchild指向其右孩子結(jié)點(diǎn)，指向其右孩子結(jié)點(diǎn)，否則令其指向其（中序）后

31、繼。否則令其指向其（中序）后繼。數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 29lchildltagrchildrtagdata結(jié)點(diǎn)類型結(jié)點(diǎn)類型 NodeStruct LNode Elementtype data ;Struct LNode *lchild , *rchild ; int ltag , rtag ; P-ltag =p-lchild 指向左孩子指向左孩子0 p-lchild 指向（中序）前驅(qū)指向（中序）前驅(qū)P-rtag =p-rchild 指向右孩子指向右孩子0 p-lchild 指向（中序）后繼指向（中序）后繼討論：為方便

32、操作利用了討論：為方便操作利用了 n+1 個(gè)結(jié)點(diǎn)，但為實(shí)現(xiàn)操作卻個(gè)結(jié)點(diǎn)，但為實(shí)現(xiàn)操作卻 多用了多用了 2n 個(gè)標(biāo)志位。個(gè)標(biāo)志位。Typdef Struct LNode * THTREE;數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 30類似線性鏈表，為每個(gè)線索樹增加一個(gè)頭結(jié)點(diǎn)。并設(shè)： head-lchild = T (二元樹的根) ; head-rchild = head ; head-ltag = 1 ; head-rtag = 1 ;當(dāng)線索樹為空時(shí)： head-lchild = head ; head-rchild = head ; he

33、ad-ltag = 0 ; head-rtag = 1 ;數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 31THTREE INNEXT( THTREE p)THTREE p ; THTREE Q ; Q=p-rchild ; if (p-rtag = = 1 ) while(Q-ltag = = 1) Q = Q-lchild ; return ( Q ) ;分析：(1) 當(dāng)p-rtag = 0時(shí)，p-rchild 既為所求（線索）。 (2) 當(dāng)p-rtag = 1時(shí)，p$為p的右子樹的最左結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院

34、 http:/ 2006 秋 Slide. 4 - 32 INPRE( p) p ; Q ; Q=p-lchild ; if (p-ltag = = 1 ) while(Q-rtag = = 1) Q = Q-rchild ; return ( Q ) ;分析：(1) 當(dāng)p-ltag = 0時(shí)，p-lchild 既為所求（線索）。 (2) 當(dāng)p-ltag = 1時(shí)，$p為p的左子樹的最右結(jié)點(diǎn)。p$pp$p數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 33Void THINORDER( HEAD) temp ; temp = HEAD ; do

35、 temp = INNEXT ( temp ) ; if ( temp != HEAD ) visit ( temp - data ) ; while ( temp != HEAD ) ; head-lchild = T head-rchild = head ; head-ltag = 1 ; head-rtag = 1 ;數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 34 而在線索樹中結(jié)點(diǎn)的插入與刪除則不同，因?yàn)橐瑫r(shí)考而在線索樹中結(jié)點(diǎn)的插入與刪除則不同，因?yàn)橐瑫r(shí)考慮修正線索的操作。慮修正線索的操作。 在二元樹中一般不討論結(jié)點(diǎn)的插入與刪除

36、，原因是其插在二元樹中一般不討論結(jié)點(diǎn)的插入與刪除，原因是其插入與刪除的操作與線性表相同，所不同的是需要詳細(xì)說明操入與刪除的操作與線性表相同，所不同的是需要詳細(xì)說明操作的具體要求。作的具體要求。例：將結(jié)點(diǎn)例：將結(jié)點(diǎn) p 插入作為結(jié)點(diǎn)插入作為結(jié)點(diǎn) S 的右孩子結(jié)點(diǎn)。的右孩子結(jié)點(diǎn)。 （1）若）若S的右子樹為空，插入比較簡(jiǎn)單的右子樹為空，插入比較簡(jiǎn)單; （2）若）若S的右子樹非空，則的右子樹非空，則 p 插入后插入后 原來原來 S 的右子樹的右子樹 作為作為 p 的右子樹的右子樹數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 35Void RINSER

37、T ( S , R ) W ; R-rchild = S-rchild ; R-rtag = S-rtag ; R-lchild = S ; R-ltag = 0 ; S-rchild = R ; S-rtag = 1 ; if ( R-rtag = 1 ) w = INNEXT( R ) ; w-lchild = R ; 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 364.2.4 二元樹的復(fù)制二元樹的復(fù)制二元樹的相似與等價(jià)二元樹的相似與等價(jià)兩株二元樹具有兩株二元樹具有指：指： （1）它們都是空的）它們都是空的 ； （2）它們都是非空的，且

38、左右子樹分別具有相同結(jié)構(gòu)。）它們都是非空的，且左右子樹分別具有相同結(jié)構(gòu)。 相似且相應(yīng)結(jié)點(diǎn)包含相同信息的二元樹稱為相似且相應(yīng)結(jié)點(diǎn)包含相同信息的二元樹稱為二元樹。二元樹?！靶螤钚螤睢毕嘞嗤瑪?shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 37int EQUAL( firstbt , secondbt )BTREE firstbt , secondbt ; int x ; x = 0 ; if ( ISEMPTY(firstbt) & ISEMPTY(secondbt) ) x = 1 ; else if ( !ISEMPTY( firstb

39、t ) & ! ISEMPTY( secondbt ) ) if ( DATA( firstbt ) = DATA( secondbt ) ) if ( EQUAL( LCHILD( firstbt ) , LCHILD( secondbt ) ) ) x= EQUAL( RCHILD( firstbt ) , RCHILD( secondbt) ) return( x ) ; /* EQUAL */數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 38 COPY( oldtree ) temp ; if ( oldtree != NUL

40、L ) temp = new Node ; temp - lchild = COPY( oldtree-lchild ) ; temp - rchild = COPY( oldtree-rchild ) ; temp - data = oldtree-data ; return ( temp ); return ( NULL ) ; /* COPY */數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 394.3.1 抽象數(shù)據(jù)型樹抽象數(shù)據(jù)型樹PARENT( n , T ) 求結(jié)點(diǎn) n 的雙親LEFTMOST-CHILD( n , T ) 返回結(jié)點(diǎn)

41、 n 的最左兒子RIGHT-SIBLING( n , T ) 返回結(jié)點(diǎn) n 的右兄弟DATA( n , T ) 返回結(jié)點(diǎn) n 的信息CREATE k (v , T1 , T2 , , Tk ) , k = 1 , 2 , 建立data域v的根結(jié)點(diǎn)r , 有k株子樹T1 , T2 , , Tk 且自左至右排列；返回r。ROOT( T ) 返回樹T的根結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 40樹的三種遍歷樹的三種遍歷先根順序先根順序 訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) ； 先根順序遍歷先根順序遍歷T1 ; 先根順序遍歷先根順序遍歷T2 ; 先跟順序

42、遍歷先跟順序遍歷Tk ;T1T2TknT中根順序中根順序 中根順序遍歷中根順序遍歷T1 ; 訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) ； 中根順序遍歷中根順序遍歷T2 ; 中根順序遍歷中根順序遍歷Tk ;后根順序后根順序 后根順序遍歷后根順序遍歷T1 ; 后根順序遍歷后根順序遍歷T2 ; 后根順序遍歷后根順序遍歷Tk ; 訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) ；數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 41例：假設(shè)樹的類型為例：假設(shè)樹的類型為TREE，結(jié)點(diǎn)的類型為，結(jié)點(diǎn)的類型為node ，數(shù)據(jù)項(xiàng)的，數(shù)據(jù)項(xiàng)的 類型為類型為elementtype，用遞歸方法給出樹的先根遍歷如下

43、：，用遞歸方法給出樹的先根遍歷如下：Void PREORDER( n , T )Node n ; TREE T ; node c ; visit( DATA( T ) ) ; c = LEFTMOST-CHILD( n , T ) ; while ( c != NULL ) PREORDER( c , T ) ; c = RIGHT-SIBLING( c , T ) ; 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 42樹的結(jié)點(diǎn)依次編號(hào)為樹的結(jié)點(diǎn)依次編號(hào)為1，2，3， ，n；設(shè)數(shù)組；設(shè)數(shù)組AiAi =j 若結(jié)點(diǎn)若結(jié)點(diǎn) i 的父親是的父親是 j

44、0 若結(jié)點(diǎn)若結(jié)點(diǎn) i 是根是根12345678901112230 1 2 3 4 5 6 7 8 9 44A123456789一般有：PARENT(i) = AiStruct node int parent ; char data ; ;Typdef node TREE11;TREE T ;T7.parent = 5 ;T7.data = 1 ;面向特定的操作，設(shè)計(jì)合適的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 43ABCDEFG0 1 2 3 4 5 6 7 8 9HIT011122344123456789ABCDEFG HI樹

45、的雙親表示法的改進(jìn)方案Typedef int node ;Typedef node TREEmaxnodes ;node LEFTMOST-CHILD( n , T )node n ; TREE T ; node I ; for ( i = n + 1 ; i = maxnodes 1 ; i+ ) if ( Ti = n ) return( i ) ; i 為最左孩子 return( 0 ) ; n是葉子LEFTMOST-CHILD數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 44RABCDEFGKHtypedef struct CTNod

46、e int child ; struct CTNode *next ; * ;typedef struct Telementtype data ; ChildPtr firstchild ; ;typedef struct CTBox nodesMAX_TREE_SIZE ; int n , r ; ;數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 45RABCDEFGKHRABCDEFGKHRABCDEFGKH類型：typedef struct CSNode ElemType data; struct CSNode *firstchild ,

47、 *nextsibling ; ;遍歷先序 RADEBCFGHK RADEBCFGHK中序 DAERBGFHKC DEABGHKFCR后續(xù) DEABGHKFCR EDKHGFCBAR樹二叉樹數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 46森林轉(zhuǎn)換為二元樹：森林轉(zhuǎn)換為二元樹：1、先將森林中每棵樹、先將森林中每棵樹 轉(zhuǎn)換成二元樹轉(zhuǎn)換成二元樹2、二元樹的樹根連接起來、二元樹的樹根連接起來數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 47路徑長(zhǎng)度路徑長(zhǎng)度增長(zhǎng)樹增長(zhǎng)樹內(nèi)結(jié)點(diǎn)內(nèi)結(jié)點(diǎn)外結(jié)點(diǎn)外結(jié)點(diǎn)內(nèi)結(jié)點(diǎn)路

48、徑長(zhǎng)度內(nèi)結(jié)點(diǎn)路徑長(zhǎng)度 I = 21+32+13 = 11外結(jié)點(diǎn)路徑長(zhǎng)度外結(jié)點(diǎn)路徑長(zhǎng)度 E = 12+53+24 = 25114232341111423(a)(b)(c)設(shè)：設(shè)： w i = 2 , 3 , 4 , 11 求：求：wj l j（加權(quán)路長(zhǎng)）（加權(quán)路長(zhǎng)）（a）111422333=34（b）213243113=53（c）221123242=40數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 48給定實(shí)數(shù)給定實(shí)數(shù)w=w1,w2,wm，構(gòu)造以，構(gòu)造以 wi 為權(quán)的增長(zhǎng)樹，其中為權(quán)的增長(zhǎng)樹，其中wili 最小的一棵最小的一棵 二元樹稱為二元樹

49、稱為。數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法國(guó)家示范性軟件學(xué)院 http:/ 2006 秋 Slide. 4 - 49例：輸入一批學(xué)生成績(jī)，將百分制轉(zhuǎn)換成五級(jí)分制。并且已知：例：輸入一批學(xué)生成績(jī)，將百分制轉(zhuǎn)換成五級(jí)分制。并且已知： 分?jǐn)?shù)分?jǐn)?shù) 0-59 60-69 70-79 80-89 90-100比例數(shù)比例數(shù) 0.05 0.15 0.40 0.30 0.10If (a60) b=“fail”Else if (a70) b=“pass” else if (a80) b=“general” else if(a90) b=“good” else b=“excellent”如圖（如圖（a）所示）所示10000個(gè)分?jǐn)?shù)個(gè)分?jǐn)?shù)31500次次22000次次以以5，15，40，30，10為權(quán)為權(quán)構(gòu)造哈夫曼樹如圖構(gòu)造哈