datastructureinc樹狀結(jié)構(gòu)(編輯修改稿)
2024-11-04 21:45 本頁面
【文章內(nèi)容簡介】 []) { struct student *del_node。 if((del_node = search(name)) == NULL) /* 找不到資料則顯示錯誤 */ { printf(Student %s not found!\n, name)。 return。 } /* 節(jié)點不為樹葉節(jié)點的狀況 */ if(del_nodellink != NULL || del_noderlink != NULL) del_node = replace(del_node)。 else /* 節(jié)點為樹葉節(jié)點的狀況 */ if(del_node == root) root = NULL。 else connect(del_node, 39。n39。)。 free(del_node)。 /* 釋放記憶體 */ printf(Data of student %s deleted!\n, name)。 } /* 尋找刪除非樹葉節(jié)點的替代節(jié)點 */ struct student *replace(struct student *node) { struct student *re_node。 /* 當(dāng)右子樹找不到替代節(jié)點，會搜尋左子樹是否存在替代節(jié)點 */ if((re_node = search_re_r(noderlink)) == NULL) re_node = search_re_l(nodellink)。 if(re_noderlink != NULL) /* 當(dāng)替代節(jié)點有右子樹存在的狀況 */ connect(re_node, 39。r39。)。 else if(re_nodellink != NULL) /* 當(dāng)替代節(jié)點有左子樹存在的狀況 */ connect(re_node, 39。l39。)。 else /* 當(dāng)替代節(jié)點為樹葉節(jié)點的狀況 */ connect(re_node, 39。n39。)。 strcpy(nodename, re_nodename)。 nodescore = re_nodescore。 return re_node。 } /* 搜尋右子樹替代節(jié)點 */ struct student *search_re_r(struct student *node) { struct student *re_node。 re_node = node。 while(re_node != NULL amp。amp。 re_nodellink != NULL) re_node = re_nodellink。 return re_node。 } /* 搜尋左子樹替代節(jié)點 */ struct student *search_re_l(struct student *node) { struct student *re_node。 re_node = node。 while(re_node != NULL amp。amp。 re_noderlink != NULL) re_node = re_noderlink。 return re_node。 } /* 調(diào)整二元搜尋樹的鏈結(jié)， link為 r表示處理右鏈結(jié)，為 l表處理左鏈結(jié)， 為 m則將鏈結(jié)指向 NULL */ void connect(struct student *node, char link) { struct student *parent。 parent = search_p(node)。 /* 搜尋父節(jié)點 */ /* 節(jié)點為父節(jié)點左子樹的狀況 */ if(strcmp(nodename, parentname) 0) if(link == 39。r39。) /* link為 r */ parentllink = noderlink。 else if(link == 39。l39。) /* link為 l */ parentllink = nodellink。 else /* link為 m */ parentllink = NULL。 else /* 節(jié)點為父節(jié)點右子樹的狀況 */ if(link == 39。r39。) /* link為 r */ parentrlink = noderlink。 else if(link == 39。l39。) /* link為 l */ parentrlink = nodellink。 else /* link為 m */ parentrlink = NULL。 } /* 搜尋 node的父節(jié)點 */ struct student *search_p(struct student *node) { struct student *parent。 parent = root。 while(parent != NULL) { if(strcmp(nodename, parentname) 0) if(strcmp(nodename, parentllinkname) == 0) return parent。 else parent = parentllink。 else if(strcmp(nodename, parentrlinkname) == 0) return parent。 else parent = parentrlink。 } return NULL。 } 34 二元搜尋樹 (續(xù) ) ? 利用二元搜尋樹來排序一組資料 ? 步驟： ? 先將輸入資料置於一個 queue中 ? 以第一個資料當(dāng)做二元樹的樹根 ? 以後的資料與樹根比較，若小於則成為樹根之左子樹，若大於則為其右子樹，如此一直遞迴式的進行 ? 建立完畢後再以中序法追蹤 ? 若要由小而大排序，則將結(jié)果直接輸出。若是由大而小，則先將結(jié)果置於 stack中，以後再相反輸出 35 引線二元樹 ? 引線二元樹 (threaded binary tree) ? 一般二元樹中有一半以上的 link field是 null link，為便利儲存及節(jié)省 link欄位的浪費，將空的 link換成一種叫引線 (thread)的指標(biāo) ? 引線二元樹的資料結(jié)構(gòu) LB IT R B ITR LINKDATALL INK1. 當(dāng) LBIT=1時， LLINK是正常指標(biāo) 2. 當(dāng) LBIT=0時， LLINK是引線 3. 當(dāng) RBIT=1時， RLINK是正常指標(biāo) 4
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1