[理學]數(shù)據(jù)結(jié)構(gòu)7樹形結(jié)構(gòu)-資料下載頁
2025-10-07 21:14本頁面
【正文】 ∧ ?刪除結(jié)點要引起數(shù)據(jù)移動 ?該結(jié)構(gòu)在圖中還將用到 (4) 改進三 ：帶雙親的孩子鏈表 ?結(jié)點由三個域組成 : 數(shù)據(jù)域 、 指向第一個孩子的指針域 和指向雙親的指針域 ?即在孩子表示法中增加一個指向雙親的指針域 (引入雙親存儲結(jié)構(gòu)的理念 ) R A B C D E F G H K 0 1 2 3 4 5 6 7 8 9 data link 0 R 1 A 2 B 3 C 4 D 5 E 6 F 7 G 8 H 9 K 1 2 3 ∧ 4 5 ∧ ∧ 6 ∧ ∧ ∧ 7 8 9 ∧ ∧ ∧ ∧ parent 0 1 1 0 2 0 3 0 4 1 5 1 6 3 7 6 8 6 9 6 ?即可以訪問每個結(jié)點的孩子 ， 也可訪問雙親 。 4. 孩子 、 兄弟鏈存儲結(jié)構(gòu) 孩子兄弟鏈存儲結(jié)構(gòu)是為每個結(jié)點設(shè)計三個域：一是數(shù)據(jù)元素域 、 二是該結(jié)點第一個孩子結(jié)點的指針域 、 三是該結(jié)點下一個兄弟結(jié)點的指針域 。 R A B C D E F G H K Head R A ∧ D B ∧ C F ∧ E ∧ ∧ ∧ G ∧ H ∧ K ∧ ∧ ∧ 結(jié)點描述： typedef struct tnode { ElemType data。 struct tnode *hp。/*指向兄弟 */ struct tnode *vp。/*指向孩子結(jié)點 */ }tnode 樹的應(yīng)用 (補充 ) 例 皇后問題 : 皇后 (NQueens)問題是將 N個棋子擺入一個 N N的矩陣 ， 并且規(guī)定每一行 、 每一列 、 每一從右上到左下 、 從左上到右下的斜線 ， 均只放置一個棋子 ， 不能有重復(fù)的情形發(fā)生 。 以 4 4為例： 矩陣中放入棋子時以數(shù)碼編號 ， 1 (1,1) (2,1) (2,2) (2,3) 2 (2,4) (3,1) (3,2) (3,3) (3,4) 1 2 (3,1) 3 (3,2) (3,3) (3,4) (4,1) (4,2) (4,3) (4,4) 1 (1,1) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4) (3,1) (3,2) (3,3) (3,4) (4,1) (4,2) (4,3) (4,4) (1,2) 2 (2,1) (2,2) (2,3) (2,4) 3 (3,1) (3,2) (3,3) (3,4) 4 (4,1) (4,2) (4,3) (4,4) 1 2 3 4 1 2 3 1 2 例 決策樹 假設(shè)有八枚硬幣分別編號為 a、 b、 c、 d、 e、 f、 g、 h， 在這八枚硬幣中 ， 其中有一枚是假幣 ， 其重量也不同于其他的七枚硬幣 ， 但不知道假幣是比較輕或比較重 。 現(xiàn)在希望能利用一具天平來找出該枚假幣 ， 同時也能準確地測出該假幣比其它的硬幣重或是輕 ， 此外還要求比較的次數(shù)越少越好 。 下圖是八枚硬幣找出其中一枚假幣的決策樹 ， 可表示一連串的決策由此找到問題的答案 。 a+b+c ? d+e+f a+d ? b+e aH eL cH fL bH dL gH hL hH gL bL dH cL fH aL eH g ? a h ? a g ? h b ? a c ? a a ? b a+d ? b+e d ? a a ? c a ? b = = = = = = = = = = = ?a、 b、 c、 d、 e、 f、 g、 h表示八枚硬幣的編號； ?葉結(jié)點 (aH)表示 a硬幣較真硬幣為重 ， (aL)表示 a硬幣較真硬幣為輕； ?a+b+c ? d+e+f 表示兩堆比較重量； a+b+c ? d+e+f a+d ? b+e aH eL cH fL bH dL gH hL hH gL bL dH cL fH aL eH g ? a h ? a g ? h b ? a c ? a a ? b a+d ? b+e d ? a a ? c a ? b = = = = = = = = = = = ?取出八枚硬幣中的六枚 (a,b,c,d,e,f)分成兩堆放至于天平上； ?因為 a+b+c d+e+f 這表示 g,h 為真幣，假幣在前六枚中； ?拿掉 c,f 并將 b,d 互換， 比較得 a+db+e，即確定 c,f為真幣，且 b,d也為真幣即 a或 e為假。否則若 b或 d為假，因為這兩者互換勢必改變重量使 a+d b+e ?用 a 和 d 比較 若 a=d，因 d 為真幣，可得 e 是一枚假幣且較重。 g,h 為真幣 a或 e為假 b或 d 為假 c或 f 為假 g或 h為假 g,h 為真幣 a或 e為假 b或 d為假 作業(yè)： 寫出下面這棵樹的 帶雙親孩子鏈表和孩子、兄弟鏈存儲結(jié)構(gòu)。并回答下述問題： 1. 樹的度和深度； 2. 葉結(jié)點的個數(shù)； 3. 先序遍歷和后序遍歷的順序。 a b k c f d h i j e g l m
教學課件相關(guān)推薦
鄂ICP備17016276號-1