[理學(xué)]數(shù)據(jù)結(jié)構(gòu)7樹(shù)形結(jié)構(gòu)-在線瀏覽
2024-12-03 21:14本頁(yè)面
【正文】 。 A B C D E F G H I J K L M 例如： A 到 L 的路徑： A(ki)?B(ki1)?E(ki2)?L(kj) 也可以表示為： (A,B,E,J) 路徑長(zhǎng)度： 3， 有以下兩種計(jì)算方法 結(jié)點(diǎn)數(shù) – 1 分支數(shù) ⒋ 孩子結(jié)點(diǎn) 、 雙親結(jié)點(diǎn)和兄弟結(jié)點(diǎn)： 在一棵樹(shù)中 ， 每個(gè)結(jié)點(diǎn)的后繼 ， 被稱作該結(jié)點(diǎn)的 孩子結(jié)點(diǎn) (或子女結(jié)點(diǎn) )。 具有同一雙親的孩子結(jié)點(diǎn)互為 兄弟結(jié)點(diǎn) 。 ⒌ 結(jié)點(diǎn)的層次和樹(shù)的高度 樹(shù)中的每個(gè)結(jié)點(diǎn)都處在一定的層次上 。 一個(gè)結(jié)點(diǎn)所在的層次為其雙親結(jié)點(diǎn)所在的層次加 1。 ⒍ 有序樹(shù)和無(wú)序樹(shù)： 若樹(shù)中各結(jié)點(diǎn)的子樹(shù)是按照一定的次序從左向右安排的 ， 且相對(duì)次序是不能隨意變換的 ， 則稱為 有序樹(shù) ， 否則稱為 無(wú)序樹(shù) 。 ⒎ 森林： n (n＞ 0) 個(gè)互不相交的樹(shù)的集合稱為森林 。 反之 ， 只要給 n 棵獨(dú)立的樹(shù)加上一個(gè)結(jié)點(diǎn) ， 并把這 n 棵樹(shù)作為該結(jié)點(diǎn)的子樹(shù) ， 則森林就變成了樹(shù) 。 證明： 根據(jù)樹(shù)的定義 ， 在一棵樹(shù)中除樹(shù)根結(jié)點(diǎn)外 ， 每個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)結(jié)點(diǎn) 。 A B C D E F G H I J K L M ?除樹(shù)根結(jié)點(diǎn)外 ， 每個(gè)結(jié)點(diǎn)與指向它的一個(gè)分支一一對(duì)應(yīng) 。 性質(zhì) 2： 度為 m 的樹(shù)中第 i 層上至多有 mi1個(gè) 結(jié)點(diǎn) ， i≥ 1。 假設(shè)對(duì)于第 (i1)層 (i＞ 1)命題成立 ， 即度為 m 的樹(shù)中第 (i1)層上至多有mi2個(gè)結(jié)點(diǎn) 。 性質(zhì) 3： 高度為 h 的 m 次樹(shù)至多有 個(gè)結(jié)點(diǎn) 。 例如高度為 3的滿 2次樹(shù) (每個(gè)結(jié)點(diǎn)的度最大為 2)， 總結(jié)點(diǎn)數(shù) = (231)/(21)=7 1 2 3 4 5 6 7 性質(zhì) 4： 具有 n 個(gè)結(jié)點(diǎn)的 m 次樹(shù)的最小高度為 ?logm(n(m1)+1)?。 樹(shù)的基本運(yùn)算 由于樹(shù)是非線性結(jié)構(gòu) ， 結(jié)點(diǎn)之間的關(guān)系較線性結(jié)構(gòu)復(fù)雜得多 ， 所以樹(shù)的運(yùn)算較以前討論過(guò)的各種線性數(shù)據(jù)結(jié)構(gòu)的運(yùn)算要復(fù)雜許多 。 樹(shù)的遍歷運(yùn)算是指按某種方式訪問(wèn)樹(shù)中的每一個(gè)結(jié)點(diǎn) ， 且每一個(gè)結(jié)點(diǎn)只被訪問(wèn)一次 。 注意 ， 下面的先根遍歷和后根遍歷算法都是遞歸的 。 例 ：求該樹(shù)的先序遍歷次序 。 R A B C D E F G H K R ?按照從左到右的次序先根遍歷子樹(shù) A、 B、 C ?遍歷每個(gè)子樹(shù)時(shí)又要按照原則 (1)和 (2)進(jìn)行 即遍歷 B之前應(yīng)完成 A的遍歷 。 ?遇到 R時(shí)不訪問(wèn) ， 要待到其所有子樹(shù)全部訪問(wèn)完畢 (左至右 )， 即準(zhǔn)備訪問(wèn) A； ?處理 A時(shí)遵守同樣的規(guī)則 。 ?先根遍歷： A,B,E,K,L,F,C,G,D,H,M,I,J ?后根遍歷： K,L,E,F,B,G,C,M,H,I,J,D,A 樹(shù)的存儲(chǔ)結(jié)構(gòu) 樹(shù)的存儲(chǔ)既要求保存結(jié)點(diǎn)的數(shù)據(jù)元素本身 ， 又要存儲(chǔ)結(jié)點(diǎn)之間的邏輯關(guān)系 。 例 ： A B C D E F G H I J K L M A:{B,C,D} B:{E,F} C:{G} D:{H,I,J} E:{K,L} H:{M} 該樹(shù)有 13個(gè)結(jié)點(diǎn)即數(shù)組有 13行 ， 樹(shù)的度為 3所以數(shù)組要有 4列 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 A B C D E F G H I J K L M 1 2 3 (子樹(shù)根的地址 ) 4 5 6 7 8 9 10 11 12 特點(diǎn)：查找任一結(jié)點(diǎn)的孩子結(jié)點(diǎn)非常方便 ， 查找父結(jié)點(diǎn)麻煩 解決方法：增加一列存儲(chǔ)父結(jié)點(diǎn)的地址 5 1 0 0 0 1 1 2 3 3 3 4 4 7 2. 雙親存儲(chǔ)結(jié)構(gòu) 這種存儲(chǔ)結(jié)構(gòu)是一種順序存儲(chǔ)結(jié)構(gòu) ， 用一組連續(xù)空間存儲(chǔ)樹(shù)的所有結(jié)點(diǎn) ， 同時(shí)在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)偽指針 (下標(biāo) )指示其雙親結(jié)點(diǎn)的位置 。 結(jié)點(diǎn)描述： define MAXTREESIZE 100 typedef struct PTNode { TElemType data。 }PTNode。 int n。 R A B C D E F G H K 0 1 2 3 4 5 6 7 8 9 數(shù)組下標(biāo) 結(jié)點(diǎn)的數(shù)據(jù)域 雙親位置 0 R 1 1 A 0 2 B 0 3 C 0 4 D 1 5 E 1 6 F 3 7 G 6 8 H 6 9 K 6 ?存儲(chǔ)結(jié)構(gòu)的討論： 現(xiàn)有另一棵樹(shù)： W X Y Z 10 W 1 11 X 10 12 Y 10 13 Z 10 多棵樹(shù)可共享存儲(chǔ)空間 適用查找父結(jié)點(diǎn) ， 不適用查找孩子結(jié)點(diǎn) 面向?qū)ο蠹夹g(shù)中等價(jià)類的應(yīng)用與該存儲(chǔ)摸式的思路一致 如果樹(shù)合并： 0 1R A B C D E F
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1