樹和二叉樹的存儲(chǔ)結(jié)構(gòu)ppt課件

1、10086510線性結(jié)構(gòu)線性結(jié)構(gòu)樹結(jié)構(gòu)樹結(jié)構(gòu)存在唯一的沒(méi)有前驅(qū)存在唯一的沒(méi)有前驅(qū)的的 首元素首元素 存在唯一的沒(méi)有前驅(qū)的存在唯一的沒(méi)有前驅(qū)的 根結(jié)點(diǎn)根結(jié)點(diǎn) 存在唯一的沒(méi)有后繼存在唯一的沒(méi)有后繼的的 尾元素尾元素 存在多個(gè)沒(méi)有后繼的存在多個(gè)沒(méi)有后繼的 葉子葉子 其余元素均存在唯一其余元素均存在唯一的的 前驅(qū)元素前驅(qū)元素 和唯一和唯一的的 后繼元素后繼元素 其余結(jié)點(diǎn)均存在唯一的其余結(jié)點(diǎn)均存在唯一的 前驅(qū)前驅(qū)( (雙親雙親) )結(jié)點(diǎn)結(jié)點(diǎn) 和多和多個(gè)個(gè) 后繼后繼( (孩子孩子) )結(jié)點(diǎn)結(jié)點(diǎn) q 二叉樹的定義二叉樹的定義q 是是n(n=0)n(n=0)個(gè)結(jié)點(diǎn)的有限集，其子樹分為互不相交的兩個(gè)個(gè)結(jié)點(diǎn)的有限

2、集，其子樹分為互不相交的兩個(gè)集合，分別稱為左子樹和右子樹，左子樹和右子樹也是二集合，分別稱為左子樹和右子樹，左子樹和右子樹也是二叉樹。叉樹。ABCDEIJGH根結(jié)點(diǎn)根結(jié)點(diǎn)左子樹左子樹右子樹右子樹v二叉樹不是樹的特例。二叉樹不是樹的特例。v特點(diǎn)特點(diǎn)v每個(gè)結(jié)點(diǎn)至多有二棵子樹每個(gè)結(jié)點(diǎn)至多有二棵子樹( (即不存在度大于即不存在度大于2 2的結(jié)點(diǎn)的結(jié)點(diǎn)) )；v二叉樹的子樹有左、右之分，且其次序不能任意顛倒。二叉樹的子樹有左、右之分，且其次序不能任意顛倒。v基本形態(tài)基本形態(tài)AABABABC空二空二叉樹叉樹只有根結(jié)點(diǎn)只有根結(jié)點(diǎn)的二叉樹的二叉樹右子樹右子樹為空為空左子左子樹為樹為空空左、右子樹左、右子樹均非

3、空均非空斜樹斜樹1 .所有結(jié)點(diǎn)都只有左所有結(jié)點(diǎn)都只有左子樹的二叉樹稱為左子樹的二叉樹稱為左斜樹；斜樹；2 .所有結(jié)點(diǎn)都只有右所有結(jié)點(diǎn)都只有右子樹的二叉樹稱為右子樹的二叉樹稱為右斜樹；斜樹；3.左斜樹和右斜樹統(tǒng)左斜樹和右斜樹統(tǒng)稱為斜樹。稱為斜樹。1. 在斜樹中，每一層只有一個(gè)結(jié)點(diǎn)；在斜樹中，每一層只有一個(gè)結(jié)點(diǎn)；2.斜樹的結(jié)點(diǎn)個(gè)數(shù)與其深度相同。斜樹的結(jié)點(diǎn)個(gè)數(shù)與其深度相同。 幾種特殊形式的二叉樹幾種特殊形式的二叉樹斜樹的特點(diǎn)：斜樹的特點(diǎn)：ABCABCq 滿二叉樹滿二叉樹q 深度為深度為k k且有且有2k-12k-1個(gè)結(jié)點(diǎn)的二叉樹。個(gè)結(jié)點(diǎn)的二叉樹。q 特點(diǎn)特點(diǎn)q 每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)；每一層

4、上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)；q 所有的分支結(jié)點(diǎn)的度數(shù)都為所有的分支結(jié)點(diǎn)的度數(shù)都為2 2；q 葉子結(jié)點(diǎn)都在同一層次上。葉子結(jié)點(diǎn)都在同一層次上。123114589121367101415q 完全二叉樹完全二叉樹q 若對(duì)滿二叉樹的結(jié)點(diǎn)從上到下從左至右進(jìn)行編號(hào)，則深度若對(duì)滿二叉樹的結(jié)點(diǎn)從上到下從左至右進(jìn)行編號(hào)，則深度為為k k且有且有n n個(gè)結(jié)點(diǎn)的二叉樹稱為完全二叉樹，當(dāng)且僅當(dāng)其每個(gè)結(jié)點(diǎn)的二叉樹稱為完全二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為一個(gè)結(jié)點(diǎn)都與深度為k k的滿二叉樹的編號(hào)從的滿二叉樹的編號(hào)從1 1到到n n一一對(duì)應(yīng)時(shí)。一一對(duì)應(yīng)時(shí)。q 特點(diǎn)特點(diǎn)q 葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)；葉子結(jié)點(diǎn)只可

5、能在層次最大的兩層上出現(xiàn)；q 前前k-1k-1層中的結(jié)點(diǎn)都是層中的結(jié)點(diǎn)都是“滿的，且第滿的，且第 k k 層的結(jié)點(diǎn)都集中在層的結(jié)點(diǎn)都集中在左邊。左邊。1231145891267101234567123456思索：滿二叉樹與完全二叉樹的關(guān)系？思索：滿二叉樹與完全二叉樹的關(guān)系？在滿二叉樹中，從最后在滿二叉樹中，從最后一個(gè)結(jié)點(diǎn)開始，連續(xù)去一個(gè)結(jié)點(diǎn)開始，連續(xù)去掉任意多個(gè)結(jié)點(diǎn)，即是掉任意多個(gè)結(jié)點(diǎn)，即是一棵完全二叉樹。一棵完全二叉樹。A1523467910BCDEFGHIJK11L12M13N14O158CDEFGHIJ不是完全二叉樹，結(jié)點(diǎn)不是完全二叉樹，結(jié)點(diǎn)10與滿二叉樹中的結(jié)

6、點(diǎn)與滿二叉樹中的結(jié)點(diǎn)10不是同一個(gè)結(jié)點(diǎn)不是同一個(gè)結(jié)點(diǎn)q 性質(zhì)性質(zhì)1：在二叉樹的第：在二叉樹的第 i 層至多有層至多有 2i-1 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) ( i1)。q 性質(zhì)性質(zhì)2：深度為：深度為 k 的二叉樹至多有的二叉樹至多有 2k-1 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。q 性質(zhì)性質(zhì)3：對(duì)于任何一棵二叉樹：對(duì)于任何一棵二叉樹T，若其終端結(jié)點(diǎn)，若其終端結(jié)點(diǎn)(葉子葉子)數(shù)為數(shù)為 n0 ，度為，度為1的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n1，度為，度為2的結(jié)點(diǎn)數(shù)的結(jié)點(diǎn)數(shù)n2， 則則n0= n2+1。q 性質(zhì)性質(zhì)4 4：具有：具有n n個(gè)結(jié)點(diǎn)的完全二叉樹的深度是個(gè)結(jié)點(diǎn)的完全二叉樹的深度是log2nlog2n +1+1。q 性質(zhì)性質(zhì)5 5：如果

7、對(duì)一棵有：如果對(duì)一棵有n n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序 編號(hào)，則對(duì)任一結(jié)點(diǎn)編號(hào)，則對(duì)任一結(jié)點(diǎn)i(1i(1i in)n)，有：，有：q 如果如果i=1i=1，則結(jié)點(diǎn)，則結(jié)點(diǎn)i i是二叉樹的根，無(wú)雙親；如果是二叉樹的根，無(wú)雙親；如果i1i1，則，則其雙親是其雙親是i/2i/2 ；q 如果如果2in2in，則結(jié)點(diǎn)，則結(jié)點(diǎn)i i無(wú)左孩子；如果無(wú)左孩子；如果2i2in n，則其左孩子是，則其左孩子是2i2i；q 如果如果2i+1n2i+1n，則結(jié)點(diǎn)，則結(jié)點(diǎn)i i無(wú)右孩子；如果無(wú)右孩子；如果2i+12i+1n n，則其右孩，則其右孩子是子是2i+12i+1。q 順序存儲(chǔ)結(jié)

8、構(gòu)順序存儲(chǔ)結(jié)構(gòu)q 用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹中的數(shù)據(jù)元素。用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹中的數(shù)據(jù)元素。q 完全二叉樹，只要從根起按層序存儲(chǔ)即可。將完全二叉樹完全二叉樹，只要從根起按層序存儲(chǔ)即可。將完全二叉樹上編號(hào)為上編號(hào)為 i i 的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組中下標(biāo)為的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組中下標(biāo)為 i-1 i-1 的的分量中。分量中。q 一般的二叉樹，可對(duì)照完全二叉樹的編號(hào)進(jìn)行相應(yīng)的存儲(chǔ)，一般的二叉樹，可對(duì)照完全二叉樹的編號(hào)進(jìn)行相應(yīng)的存儲(chǔ)，但在沒(méi)有結(jié)點(diǎn)的分量中需填充空白字符但在沒(méi)有結(jié)點(diǎn)的分量中需填充空白字符( (例如填充例如填充0)0)。q 順序存儲(chǔ)表示順序存儲(chǔ)表示#define M

9、AX_TREE_SIZE 100 #define MAX_TREE_SIZE 100 /最最大結(jié)點(diǎn)數(shù)大結(jié)點(diǎn)數(shù)TypedefTypedefTElemType SqBiTreeMAX_TREE_SIZE; TElemType SqBiTreeMAX_TREE_SIZE; /0/0號(hào)根結(jié)點(diǎn)號(hào)根結(jié)點(diǎn)SqBiTree bt;SqBiTree bt;FBAGEDCHIJKL例如：例如： bt3的雙親為的雙親為3/2=1，即，即在在bt1中；中； 其左孩子在其左孩子在bt2i=bt6中；中； 其右孩子在其右孩子在bt2i+1=bt7中。中。如何反映結(jié)點(diǎn)之如何反映結(jié)點(diǎn)之間的邏輯關(guān)系？間的邏輯關(guān)系？A1B2C3

10、D4E5F6G7H8I9J10K11L12& 完全二叉樹的順序表示完全二叉樹的順序表示 一般二叉樹也按完全二叉樹形式存儲(chǔ)，只有增添一些并不一般二叉樹也按完全二叉樹形式存儲(chǔ)，只有增添一些并不存在的空結(jié)點(diǎn)存在的空結(jié)點(diǎn)(用用表示，表示， 表示該處沒(méi)有元素存在，僅僅為了表示該處沒(méi)有元素存在，僅僅為了好理解好理解)，使之成為一棵完全二叉樹的形式，然后再用一維數(shù)組，使之成為一棵完全二叉樹的形式，然后再用一維數(shù)組順序存儲(chǔ)。順序存儲(chǔ)。A1B2C3D45E6F7G8H910111213I14J15EBAFDCGHIJ例如對(duì)于例如對(duì)于B結(jié)點(diǎn)而言：結(jié)點(diǎn)而言： bt2的雙親為的雙親為1/2=1，即在，即在bt

11、1中中(為為A)； 其左孩子在其左孩子在bt2i=bt4中中(為為D)； 其右孩子在其右孩子在bt2i+1=bt5中中(為為 )。& 一般二叉樹的順序表示一般二叉樹的順序表示 這種存儲(chǔ)結(jié)構(gòu)適合于完全二叉樹和滿二叉樹，既不浪這種存儲(chǔ)結(jié)構(gòu)適合于完全二叉樹和滿二叉樹，既不浪費(fèi)存儲(chǔ)空間，又能很快確定結(jié)點(diǎn)的存放位置、以及結(jié)點(diǎn)的費(fèi)存儲(chǔ)空間，又能很快確定結(jié)點(diǎn)的存放位置、以及結(jié)點(diǎn)的雙親和左右孩子的存放位置，但對(duì)一般二叉樹，可能造成雙親和左右孩子的存放位置，但對(duì)一般二叉樹，可能造成存儲(chǔ)空間的浪費(fèi)。存儲(chǔ)空間的浪費(fèi)。 例如，深度為例如，深度為k，且只有，且只有k個(gè)結(jié)點(diǎn)的右單枝樹個(gè)結(jié)點(diǎn)的右單枝樹(每個(gè)非葉每個(gè)

12、非葉結(jié)點(diǎn)只有右孩子結(jié)點(diǎn)只有右孩子)，也需，也需2k-1個(gè)個(gè)單元，即有單元，即有(2k-1)- k個(gè)單元個(gè)單元被浪費(fèi)。被浪費(fèi)。12k& 順序存儲(chǔ)的優(yōu)缺點(diǎn)順序存儲(chǔ)的優(yōu)缺點(diǎn)12345101167891211 1210987654321 1 2 3 4 5 6 7 8 9 10 11 12沒(méi)有浪費(fèi)沒(méi)有浪費(fèi)abcdefggf0000edcba 1 2 3 4 5 6 7 8 9 10 11浪費(fèi)浪費(fèi)4個(gè)個(gè)00004000300020112341 2 3 4 5 6 7 8 9 10 11 12 13 14 15浪費(fèi)浪費(fèi)11個(gè)個(gè)順序存儲(chǔ)結(jié)構(gòu)適用于滿二叉樹和完全二叉樹的存儲(chǔ)。順序存儲(chǔ)結(jié)構(gòu)適用于滿二叉樹

13、和完全二叉樹的存儲(chǔ)。 所謂鏈?zhǔn)酱鎯?chǔ)是指，用鏈表來(lái)表示一棵二叉樹，即用鏈來(lái)所謂鏈?zhǔn)酱鎯?chǔ)是指，用鏈表來(lái)表示一棵二叉樹，即用鏈來(lái)指示著元素的邏輯關(guān)系。通常采用二叉鏈表來(lái)存儲(chǔ)。指示著元素的邏輯關(guān)系。通常采用二叉鏈表來(lái)存儲(chǔ)。 鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，除了數(shù)據(jù)域外，還有兩個(gè)鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，除了數(shù)據(jù)域外，還有兩個(gè)指針域，分別用來(lái)給出該結(jié)點(diǎn)左右孩子所在的結(jié)點(diǎn)的存儲(chǔ)地指針域，分別用來(lái)給出該結(jié)點(diǎn)左右孩子所在的結(jié)點(diǎn)的存儲(chǔ)地址。其定義如下：址。其定義如下： typedef struct BiTNode ElemType data; struct BiTNode *lchild,*rchild; BiT

14、Node,*BiTree;& 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) D A B C E F Tlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)BADCEF& 二叉鏈表二叉鏈表 A B C D E F G三叉鏈表圖示三叉鏈表圖示BACDEFG& 三叉鏈表三叉鏈表lchild data結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)parent rchildq 二叉鏈表二叉鏈表q 結(jié)點(diǎn)除包括元素自身的信息外，還包括指向其左、右子結(jié)點(diǎn)除包括元素自身的信息外，還包括指向其左、右子樹的指針。即結(jié)點(diǎn)要包括數(shù)據(jù)域，左子樹指針域和右子樹的指針。即結(jié)點(diǎn)要包括數(shù)據(jù)域，左子樹指針域和右子樹指針域。樹指針域。v 二叉鏈表的存儲(chǔ)表示二叉鏈

15、表的存儲(chǔ)表示typedef struct BiTNodetypedef struct BiTNodeTElemType data;TElemType data;struct BiTNode struct BiTNode * *lchild, lchild, * *rchild;rchild;BiTNode ,BiTNode ,* *Bitree; Bitree; lchilddatarchild試用二叉鏈表的方法創(chuàng)建二叉樹試用二叉鏈表的方法創(chuàng)建二叉樹ABCDEFG AB C D E F G在在n n個(gè)結(jié)點(diǎn)的二叉鏈表中，有個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1n+1個(gè)空指針域。個(gè)空指針域。q 三叉鏈表三叉鏈表q 結(jié)點(diǎn)包括數(shù)據(jù)域，左子樹指針域、雙親域和右子樹結(jié)點(diǎn)包括數(shù)據(jù)域，左子樹指針域、雙親域和右子樹指針域。指針域。lchilddataparentrchildv三叉