【正文】 ? 將圖形化的樹狀結(jié)構(gòu)寫成一個(gè)串列 ? Ex. 將 (A(B(E(J), F(K, L)), C(G), D(H(M, N), I)) ? 左子 右弟表示法 ? 每一個(gè)節(jié)點(diǎn)需要兩個(gè)鏈結(jié) (或指標(biāo) )欄位，左欄位連結(jié)子節(jié)點(diǎn)，右欄位連結(jié)兄弟節(jié)點(diǎn) ? 左子 右弟 (left childright sibling)表示法 dat a l i nk 1 l i nk 2 ... l i nk ndataleft c hild right sibling6 樹狀結(jié)構(gòu) ─ 表示法 (續(xù) ) ? 每一個(gè)節(jié)點(diǎn)僅有一個(gè)最左 (left most)子節(jié)點(diǎn)及一個(gè)近右 (closest right)兄弟節(jié)點(diǎn) ? 子節(jié)點(diǎn)及兄弟節(jié)點(diǎn)在樹中的順序並不重要 ANMLKJIHGFEDCB7 樹狀結(jié)構(gòu) ─ 表示法 (續(xù) ) ? 以分支度為 2的樹表示 ? 將左子 右弟表示法的樹狀結(jié)構(gòu)順時(shí)鐘方向旋轉(zhuǎn) 45度即可 ANMLKJIHGFEDCB8 二元樹 ? 二元樹 (binary tree) ? 二元樹是由節(jié)點(diǎn)所組成的有限集合，這個(gè)集合若不是空集合就是由樹根及分別是右子樹(right subtree)及左子樹 (left subtree) ? 特點(diǎn) (與其他一般樹的不同 )： ? 二元樹的節(jié)點(diǎn)個(gè)數(shù)可以是零 (一般樹一定要有一個(gè)節(jié)點(diǎn) ) ? 二元樹有排列順序的關(guān)係 (一般樹則沒(méi)有 ) ? 二元樹中每一節(jié)點(diǎn)的分支度至多為 2 (一般樹無(wú)限制 ) 9 二元樹 (續(xù) ) ADCBAKJGFECBIHDAKJECBIHDONGMLF左斜樹 (left skewed tree) 完整二元樹 (plete binary tree) 滿枝二元樹 (fully binary tree) 10 二元樹 (續(xù) ) ? 特性： ? 一棵二元樹在第 i階度的最多節(jié)點(diǎn)數(shù)為 2i1， i=1 ? 一棵階度 (或深度 )為 k的二元樹， 2k1， k=1 ? 一棵二元樹，若 n0表示所有的樹葉節(jié)點(diǎn)， n2表示所有分支度為 2的節(jié)點(diǎn)， n0=n2+1 ? 表示法 ? 一維陣列表示法 ? 優(yōu)點(diǎn)：處理容易，若為滿枝二元樹，則相當(dāng)節(jié)省空間 ? 缺點(diǎn)：若為歪斜樹，則相當(dāng)浪費(fèi)空間；一般而言，較鏈結(jié)串列表示法浪費(fèi)空間 11 二元樹 (續(xù) ) A B C D1stl evel2ndl evel3rdl evel4t hl evel(1) (15 )(14 )(13 )(12 )(11 )(10 )(9)(8)(7)(6)(5)(4)(3)(2)A B C D E F G H I J K1stl evel2ndl evel3rdl evel4t hl evel(1) (15 )(14 )(13 )(12 )(11 )(10 )(9)(8)(7)(6)(5)(4)(3)(2)A B C D E F G H I J K L M N O1stl evel2ndl evel3rdl evel4t hl evel(1) (15 )(14 )(13 )(12 )(11 )(10 )(9)(8)(7)(6)(5)(4)(3)(2)? 鏈結(jié)表示法 ? 優(yōu)點(diǎn)：插入與刪除一個(gè)節(jié)點(diǎn)相當(dāng)容易 ? 缺點(diǎn)：很難找到該節(jié)點(diǎn)的父節(jié)點(diǎn) (parent) ? 解決方式：在節(jié)點(diǎn)的結(jié)構(gòu)上增加一欄 PARENT， 指向其父節(jié)點(diǎn)的位置 typedef struct node *tree_pointer。 } void preorder(Node type *tree) { if (tree != NULL){ printf(“%d”, treedata)。 return。 if(strcmp(ptrname, nodename) 0) node = nodellink。 else /* target大於目前節(jié)點(diǎn)，往右搜尋 */ node = noderlink。n39。)。 nodescore = re_nodescore。 } /* 搜尋左子樹替代節(jié)點(diǎn) */ struct student *search_re_l(struct student *node) { struct student *re_node。 /* 搜尋父節(jié)點(diǎn) */ /* 節(jié)點(diǎn)為父節(jié)點(diǎn)左子樹的狀況 */ if(strcmp(nodename, parentname) 0) if(link == 39。r39。 while(parent != NULL) { if(strcmp(nodename, parentname) 0) if(strcmp(nodename, parentllinkname) == 0) return parent。 noderbit = node_parentrbit。 nodelchild = node_parentlchild。 } } 加入新節(jié)點(diǎn)於某節(jié)點(diǎn)的左方 ? 引線二元樹的刪除 1324pr evthispr ev rch il d = thisrch il d。 } /*刪除左節(jié)點(diǎn) */ else if ( ptrnumber ptr_parentnumber ) { ptr_parentlchild = ptrlchild。 ptr_predrchild = ptrrchild。 rootlchild = ptrrchild。 } else { printf(\n Please enter login ID number: )。 else exchange(amp。 } 50 堆積 (續(xù) ) ? Heap的刪除 4010203015刪除304020201540202010調(diào)整 刪除40102020換 201015void delete_f(void) { int id_temp, del_index。 else { removes(del_index)。 heap_tree[last_index] = 0。 /* 當(dāng)比較資料之 INDEX不大於最後一筆資料之 INDEX， 則繼續(xù)比較 */ while(index_temp = index2) {if((index_temp index2) am