[電腦基礎(chǔ)知識]第7章樹(編輯修改稿)
2025-02-15 15:32 本頁面
【文章內(nèi)容簡介】 (T) 12 Delete(t) 13 Height(t) 14 Size(t) 二叉樹的實現(xiàn) ? 實現(xiàn)方法： 將二叉樹的所有結(jié)點，按照一定的次序依次存儲到一組連續(xù)的存儲單元中。 對于完全二叉樹，可采用 “ 以編號為地址 ” 的策略將結(jié)點存入作為順序存儲結(jié)構(gòu)的 一維數(shù)組 。 ? 具體實現(xiàn)如下： 將一棵具有 n個結(jié)點的完全二叉樹，從樹根起，自上層到下層，逐層從左到右給所有結(jié)點編號，其中每個結(jié)點的編號作為結(jié)點的名稱。 將編號為 i的結(jié)點存入一維數(shù)組的第 i個單元 ，這樣，就能得到一個足以反映整個二叉樹結(jié)構(gòu)的線性序列。 bt: 0 1 2 3 4 5 6 7 8 9 10 11 12 結(jié)點 A B C D E F G H I J K L 完全二叉樹 a b c d e f g h i j k l (1) 順序存儲結(jié)構(gòu) 1 2 3 4 5 6 7 8 9 10 11 12 性質(zhì) 5：如果對一棵有 n個結(jié)點的完全二叉樹的結(jié)點按層序編號，則對任一結(jié)點 i（ 1=i=n),有： （ 1）如果 i＝ 1，則結(jié)點 i無雙親，是二叉樹的根；如果 i1，則其雙親是結(jié)點 [i/2]。 （ 2）結(jié)點 i的左兒子結(jié)點為 2i，結(jié)點 i的右兒子結(jié)點為 2i+1。 （ 3）當 i為奇數(shù)且不為 1時，結(jié)點 i的左兄弟結(jié)點為 i1,當 i為偶數(shù)時，結(jié)點 i的右兄弟結(jié)點為 i+1。 [i/2] i i+1 2i+1 2(i+1) 2i+3 i+1 2(i+1) 2i+3 i 2i 2i+1 圖 完全二叉樹中結(jié)點 i和 i+1 (a)i和 i+1結(jié)點在同一層 (b)i和 i+1結(jié)點不在同一層 2i 如圖所示為完全二叉樹上結(jié)點及其左右子樹在結(jié)點之間的關(guān)系。 由上述關(guān)系可知， 完全 二叉樹中結(jié)點的層次關(guān)系足以反映結(jié)點之間的邏輯關(guān)系。在這種存儲結(jié)構(gòu)中，借助二叉樹的性質(zhì)，可以比較方便地實現(xiàn)二叉樹的各種基本運算。因此，對 完全 二叉樹而言，順序存儲結(jié)構(gòu)既簡單又節(jié)省存儲空間。 T[16] 11 A B c F E D ● ● ● ● ● ● ● ● ● 1 2 4 8 9 10 5 6 3 7 12 13 14 15 (1) 順序存儲結(jié)構(gòu) 0 0 0 0 F E 0 0 0 D C 0 B A 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 一般二叉樹 缺點 : 對于一般的二叉樹而言，存儲空間造成極大的浪費。在最壞情況下，一個高度為 k且只有 k+1個結(jié)點的右單枝樹卻需要 2k+11個結(jié)點的存儲空間。 例如，只有 3個結(jié)點的右單枝樹 : 2. 二叉樹的結(jié)點度表示法 這種表示法將二叉樹中所有結(jié)點依其后序列表排列，并在每個結(jié)點中附加一個 0~3之間的整數(shù)，以表示結(jié)點的狀態(tài)。 （ 鏈式存儲結(jié)構(gòu)（二叉鏈表結(jié)構(gòu)）） ? 每個結(jié)點由數(shù)據(jù)域、左指針域和右指針域組成。 left element right A E C B D F A ^ D B ^ C ^ ^ E ^ ^ F ^ 二叉樹的二叉鏈表存儲結(jié)構(gòu)類型描述 Typedef struct btnode *btlink。 struct btnode { TreeItem element。 btlink left。 btlink right。 } Btnode。 left element right left element right left element right 課堂練習 ? 分別畫出下圖所示二叉樹的二叉鏈表、二叉樹的結(jié)點度表示法和順序存儲結(jié)構(gòu)示意圖。 B E A F D C ? 已知一棵二叉樹的先序序列和中序序列分別為 A B D G H E C F I J 及 G D H B E A C I J F，請畫出這棵二叉樹 。 G B C A D E F I J H ? 用指針實現(xiàn)的抽象數(shù)據(jù)類型二叉樹結(jié)構(gòu)定義為： typedef struct binarytree *BinaryTree。 typedef struct binarytree{ btlink root。 }BTree。 btlink NewBNode( ) { btlink p。 if((p=malloc(sizeof(Btnode)))==0) Error(“Exhausted memory.”)。 else return p。 } ? 創(chuàng)建一棵空二叉樹 BinaryTree BinaryInit( ) { BinaryTree T=malloc(sizeof *T)。 Troot=0。 return T。 } ? 抽象數(shù)據(jù)類型二叉樹的基本運算 返回根結(jié)點標號 int BinaryEmpty(BinaryTree T) { return Troot==0。 } TreeItem Root(BinaryTree T) { if(BinaryEmpty(T)) Error(“Tree is empty”) return Trootel
教學課件相關(guān)推薦
鄂ICP備17016276號-1