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