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

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

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

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

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

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

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

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

9、如果葉結點的個數為，如果葉結點的個數為 n0，而，而 其度為其度為 2 的結點數為的結點數為 n2，則：，則： n0 = n2 + 1定義定義 深度為深度為k且有且有2k 1個結點的二元樹稱為個結點的二元樹稱為滿二元樹滿二元樹。層序編號：對滿二元樹的結點進行連續編號。從根結點開始，層序編號：對滿二元樹的結點進行連續編號。從根結點開始， 從上而下，自左至右。從上而下，自左至右。定義定義 深度為深度為 k 的，由的，由n個結點的二元樹，當且僅當其每個結點個結點的二元樹，當且僅當其每個結點 都與深度為都與深度為 k 的滿二元樹中編號從的滿二元樹中編號從 1 至至 n 的結點一一對的結點一一對 應，稱

10、之為應，稱之為完全二元樹完全二元樹。數據結構與算法數據結構與算法國家示范性軟件學院 http:/ 2006 秋 Slide. 4 - 84.2.1 二元樹的定義和基本性質二元樹的定義和基本性質二元樹的性質二元樹的性質(續續)：性質性質4 具有具有 n 個結點的完全二元樹的深度為個結點的完全二元樹的深度為 log2n + 1。性質性質5 如果對一棵有如果對一棵有 n 個結點的二元樹的結點按層序編號，個結點的二元樹的結點按層序編號， 則對任一結點則對任一結點 i 有：有： 如果如果 i = 1，則結點，則結點 i 是二元樹的根，無雙親；如果是二元樹的根，無雙親；如果 i 1 ，則其雙親結點是，則其

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

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

13、則：若二元樹非空則： 訪問根結點；訪問根結點； 先根順序遍歷左子樹；先根順序遍歷左子樹； 先根順序遍歷右子樹；先根順序遍歷右子樹； ； 中根順序遍歷二元樹：中根順序遍歷二元樹： 若二元樹非空則：若二元樹非空則： 中根順序遍歷左子樹；中根順序遍歷左子樹； 訪問根結點；訪問根結點； 中根順序遍歷右子樹；中根順序遍歷右子樹； ； 后根順序遍歷二元樹：后根順序遍歷二元樹： 若二元樹非空則：若二元樹非空則： 后根順序遍歷左子樹；后根順序遍歷左子樹； 后根順序遍歷右子樹；后根順序遍歷右子樹； 訪問根結點；訪問根結點； ； 數據結構與算法數據結構與算法國家示范性軟件學院 http:/ 2006 秋 Slid

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

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

16、例例1-3：寫一個遞歸函數，按：寫一個遞歸函數，按 后根后根順序列出二元樹順序列出二元樹 中每個結點的中每個結點的DATA 域之值。域之值。Void POSTORDER ( BT )BTREE BT ; if ( ! ISEMPTY ( BT ) ) POSTORDER ( LCHILD ( BT ) ) ; POSTORDER ( RCHILD ( BT ) ) ; visit ( DATA ( BT ) ) ; 數據結構與算法數據結構與算法國家示范性軟件學院 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 #結束結束算法算法:Loop: if (BT 非空) 進棧; 左一步; else 退棧; 右一步;數據結構數據結構: 設棧S: 用以保留 當前結點;數據結構與算法數據結構與算法國家示范性軟件學院 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 ) ; 進棧; 左走一步退棧; 右走一步數據結構與算法數據結構與算法國家示范性軟件學院 http:/ 2006 秋 Slide. 4 - 15先序遍歷非遞歸算法算法算法:Loop: if (BT 非

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

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

22、結點的則可求得該結點的雙親結點、左孩子結點和右孩子結點，然后檢測其值是否雙親結點、左孩子結點和右孩子結點，然后檢測其值是否為虛設的特殊結點為虛設的特殊結點$。通過虛設部分結點，使其變成相應的完全二元樹。通過虛設部分結點，使其變成相應的完全二元樹。ABC$E$G$JABCEGJ數據結構與算法數據結構與算法國家示范性軟件學院 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 ; 數據結構與算法數據結構與算法國家示范性軟件學院 http:/ 2006 秋 Slide. 4 - 19證明：證明：n 個結點的二元樹中，共有個結點的二元樹

24、中，共有 n+1 個空鏈接域。個空鏈接域。證：設其空鏈域數為證：設其空鏈域數為 x 分支數分支數 B入入 = n 1 B出出=2 n x B入入 = B出出 n 1 = 2n x 得出得出 x = n 1 ABCDEFGHIJKLM結點總數：結點總數：13空鏈域的個數：空鏈域的個數：14數據結構與算法數據結構與算法國家示范性軟件學院 http:/ 2006 秋 Slide. 4 - 20按先序序列建立二元樹的左右鏈結構按先序序列建立二元樹的左右鏈結構.如由圖所示二元樹如由圖所示二元樹,輸入輸入: 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 ; 數據結構與算法數據結構與算法國家示范性軟件學院 http:/ 2006 秋 Slide. 4 - 21一棵二元樹的先序、中序和后序序列分別如下，其中一部分未顯示出來，試求出空格處的內容，并畫出該二元樹。 先序：_B_F_ICEH_G 中序：D_KFIA_

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

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

28、節點，設度為2的結點數為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)數據結構與算法數據結構與算法國家示范性軟件學院 http:/ 2006 秋 Slide. 4 - 26具有具有n個結點的滿二元樹，其葉子結點的個數為多少？個結點的滿二元樹，其葉子結點的個數為多少？具有具有n個結點的完全二元樹，其葉子結點的個數為多少？個結點的完全二元樹，其葉子結點的個數為多少？方法一：設滿二元樹的高度為， 則根據二元樹的性質，葉子結點數為2h-1 二元樹總結點數n=2h-1 可導出:h-1=(n+1)/2方

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

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

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

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

33、ad-ltag = 0 ; head-rtag = 1 ;數據結構與算法數據結構與算法國家示范性軟件學院 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) 當p-rtag = 0時，p-rchild 既為所求（線索）。 (2) 當p-rtag = 1時，p$為p的右子樹的最左結點。數據結構與算法數據結構與算法國家示范性軟件學院

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) 當p-ltag = 0時，p-lchild 既為所求（線索）。 (2) 當p-ltag = 1時，$p為p的左子樹的最右結點。p$pp$p數據結構與算法數據結構與算法國家示范性軟件學院 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 ;數據結構與算法數據結構與算法國家示范性軟件學院 http:/ 2006 秋 Slide. 4 - 34 而在線索樹中結點的插入與刪除則不同，因為要同時考而在線索樹中結點的插入與刪除則不同，因為要同時考慮修正線索的操作。慮修正線索的操作。 在二元樹中一般不討論結點的插入與刪除

36、，原因是其插在二元樹中一般不討論結點的插入與刪除，原因是其插入與刪除的操作與線性表相同，所不同的是需要詳細說明操入與刪除的操作與線性表相同，所不同的是需要詳細說明操作的具體要求。作的具體要求。例：將結點例：將結點 p 插入作為結點插入作為結點 S 的右孩子結點。的右孩子結點。 （1）若）若S的右子樹為空，插入比較簡單的右子樹為空，插入比較簡單; （2）若）若S的右子樹非空，則的右子樹非空，則 p 插入后插入后 原來原來 S 的右子樹的右子樹 作為作為 p 的右子樹的右子樹數據結構與算法數據結構與算法國家示范性軟件學院 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 ; 數據結構與算法數據結構與算法國家示范性軟件學院 http:/ 2006 秋 Slide. 4 - 364.2.4 二元樹的復制二元樹的復制二元樹的相似與等價二元樹的相似與等價兩株二元樹具有兩株二元樹具有指：指： （1）它們都是空的）它們都是空的 ； （2）它們都是非空的，且

38、左右子樹分別具有相同結構。）它們都是非空的，且左右子樹分別具有相同結構。 相似且相應結點包含相同信息的二元樹稱為相似且相應結點包含相同信息的二元樹稱為二元樹。二元樹?！靶螤钚螤睢毕嘞嗤瑪祿Y構與算法數據結構與算法國家示范性軟件學院 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 */數據結構與算法數據結構與算法國家示范性軟件學院 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 */數據結構與算法數據結構與算法國家示范性軟件學院 http:/ 2006 秋 Slide. 4 - 394.3.1 抽象數據型樹抽象數據型樹PARENT( n , T ) 求結點 n 的雙親LEFTMOST-CHILD( n , T ) 返回結點

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

42、遍歷先跟順序遍歷Tk ;T1T2TknT中根順序中根順序 中根順序遍歷中根順序遍歷T1 ; 訪問根結點訪問根結點 ； 中根順序遍歷中根順序遍歷T2 ; 中根順序遍歷中根順序遍歷Tk ;后根順序后根順序 后根順序遍歷后根順序遍歷T1 ; 后根順序遍歷后根順序遍歷T2 ; 后根順序遍歷后根順序遍歷Tk ; 訪問根結點訪問根結點 ；數據結構與算法數據結構與算法國家示范性軟件學院 http:/ 2006 秋 Slide. 4 - 41例：假設樹的類型為例：假設樹的類型為TREE，結點的類型為，結點的類型為node ，數據項的，數據項的 類型為類型為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 ) ; 數據結構與算法數據結構與算法國家示范性軟件學院 http:/ 2006 秋 Slide. 4 - 42樹的結點依次編號為樹的結點依次編號為1，2，3， ，n；設數組；設數組AiAi =j 若結點若結點 i 的父親是的父親是 j

44、0 若結點若結點 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 ;面向特定的操作，設計合適的存儲結構數據結構與算法數據結構與算法國家示范性軟件學院 http:/ 2006 秋 Slide. 4 - 43ABCDEFG0 1 2 3 4 5 6 7 8 9HIT011122344123456789ABCDEFG HI樹

45、的雙親表示法的改進方案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數據結構與算法數據結構與算法國家示范性軟件學院 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 ; ;數據結構與算法數據結構與算法國家示范性軟件學院 http:/ 2006 秋 Slide. 4 - 45RABCDEFGKHRABCDEFGKHRABCDEFGKH類型：typedef struct CSNode ElemType data; struct CSNode *firstchild ,

47、 *nextsibling ; ;遍歷先序 RADEBCFGHK RADEBCFGHK中序 DAERBGFHKC DEABGHKFCR后續 DEABGHKFCR EDKHGFCBAR樹二叉樹數據結構與算法數據結構與算法國家示范性軟件學院 http:/ 2006 秋 Slide. 4 - 46森林轉換為二元樹：森林轉換為二元樹：1、先將森林中每棵樹、先將森林中每棵樹 轉換成二元樹轉換成二元樹2、二元樹的樹根連接起來、二元樹的樹根連接起來數據結構與算法數據結構與算法國家示范性軟件學院 http:/ 2006 秋 Slide. 4 - 47路徑長度路徑長度增長樹增長樹內結點內結點外結點外結點內結點路

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

49、稱為。數據結構與算法數據結構與算法國家示范性軟件學院 http:/ 2006 秋 Slide. 4 - 49例：輸入一批學生成績，將百分制轉換成五級分制。并且已知：例：輸入一批學生成績，將百分制轉換成五級分制。并且已知： 分數分數 0-59 60-69 70-79 80-89 90-100比例數比例數 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個分數個分數31500次次22000次次以以5，15，40，30，10為權為權構造哈夫曼樹如圖構造哈