【正文】 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)? 鏈結表示法 ? 優(yōu)點：插入與刪除一個節(jié)點相當容易 ? 缺點：很難找到該節(jié)點的父節(jié)點 (parent) ? 解決方式：在節(jié)點的結構上增加一欄 PARENT， 指向其父節(jié)點的位置 typedef struct node *tree_pointer。 }。 } void preorder(Node type *tree) { if (tree != NULL){ printf(“%d”, treedata)。 postorder(treerlink)。 return。 ptrllink = ptrrlink = NULL。 if(strcmp(ptrname, nodename) 0) node = nodellink。 } } /* 搜尋 target所在節(jié)點 */ struct student *search(char target[]) { struct student *node。 else /* target大於目前節(jié)點，往右搜尋 */ node = noderlink。 return。n39。 } /* 尋找刪除非樹葉節(jié)點的替代節(jié)點 */ struct student *replace(struct student *node) { struct student *re_node。)。 else /* 當替代節(jié)點為樹葉節(jié)點的狀況 */ connect(re_node, 39。 nodescore = re_nodescore。 while(re_node != NULL amp。 } /* 搜尋左子樹替代節(jié)點 */ struct student *search_re_l(struct student *node) { struct student *re_node。 re_noderlink != NULL) re_node = re_noderlink。 /* 搜尋父節(jié)點 */ /* 節(jié)點為父節(jié)點左子樹的狀況 */ if(strcmp(nodename, parentname) 0) if(link == 39。l39。r39。) /* link為 l */ parentrlink = nodellink。 while(parent != NULL) { if(strcmp(nodename, parentname) 0) if(strcmp(nodename, parentllinkname) == 0) return parent。 } return NULL。 noderbit = node_parentrbit。 node_parentrbit = 1。 nodelchild = node_parentlchild。 node_parentlchild = node。 } } 加入新節(jié)點於某節(jié)點的左方 ? 引線二元樹的刪除 1324pr evthispr ev rch il d = thisrch il d。132… if ( ptrlbit == 0 amp。 } /*刪除左節(jié)點 */ else if ( ptrnumber ptr_parentnumber ) { ptr_parentlchild = ptrlchild。 } free(ptr)。 ptr_predrchild = ptrrchild。 } else /*刪除一分支度節(jié)點 */ { if ( ptr_parent == root ) /*刪除第一節(jié)點 */ { if ( ptrlbit == 1 ) { ptr_pred = inpred(ptr)。 rootlchild = ptrrchild。 } } 刪除節(jié)點於非樹葉節(jié)點的左右方 45 堆積 ? 堆積 (heap) ? 定義：堆積是一棵二元樹，其樹根的鍵值大於子樹的鍵值，且必須符合完整二元樹 ? 不管左子樹和右子樹的大小順序 (與二元搜尋樹最大的差異 ) ? Heap可用於排序上，簡稱 Heap Sort ? 在一堆雜亂無章的資料中，利用 heap sort將它由小至大或由大至小排序皆可 ? 首先，將一堆資料利用完整二元樹將其建立起來，再將它調整為 Heap， 爾後再依題意用 Stack(由大到小 )或 Queue(由小至大 )輔助之 ? Heap的調整 ? 由上而下 ? 從樹根開始到 ，分別與其子節(jié)點相比，若前者大則不用交換。 } else { printf(\n Please enter login ID number: )。 /* 建立堆積 */ printf( Login successfully!!\n)。 else exchange(amp。 } } void exchange(int *id1, int *id2) /* 交換傳來之 ID1及 ID2儲存之資料 */ { int id_temp。 } 50 堆積 (續(xù) ) ? Heap的刪除 4010203015刪除304020201540202010調整 刪除40102020換 201015void delete_f(void) { int id_temp, del_index。 scanf(%d, amp。 else { removes(del_index)。 c_index = MAX。 heap_tree[last_index] = 0。 else /* 替代資料小於其 CHILDEN NODE， 則往下調整 */ adjust_d(heap_tree, index_temp, last_index1)。 /* 當比較資料之 INDEX不大於最後一筆資料之 INDEX， 則繼續(xù)比較 */ while(index_temp = index2) {if((index_temp index2) amp。 else { temp[index_temp/2] = temp[index_temp