datastructureinc树状结构

datastructureinc树状结构内容摘要：

[]) { struct student *del_node。 if((del_node = search(name)) == NULL) /* 找不到資料則顯示錯誤 */ { printf(Student %s not found!\n, name)。 return。 } /* 節點不為樹葉節點的狀況 */ if(del_nodellink != NULL || del_noderlink != NULL) del_node = replace(del_node)。 else /* 節點為樹葉節點的狀況 */ if(del_node == root) root = NULL。 else connect(del_node, 39。 n39。 )。 free(del_node)。 /* 釋放記憶體 */ printf(Data of student %s deleted!\n, name)。 } /* 尋找刪除非樹葉節點的替代節點 */ struct student *replace(struct student *node) { struct student *re_node。 /* 當右子樹找不到替代節點，會搜尋左子樹是否存在替代節點 */ if((re_node = search_re_r(noderlink)) == NULL) re_node = search_re_l(nodellink)。 if(re_noderlink != NULL) /* 當替代節點有右子樹存在的狀況 */ connect(re_node, 39。 r39。 )。 else if(re_nodellink != NULL) /* 當替代節點有左子樹存在的狀況 */ connect(re_node, 39。 l39。 )。 else /* 當替代節點為樹葉節點的狀況 */ connect(re_node, 39。 n39。 )。 strcpy(nodename, re_nodename)。 nodescore = re_nodescore。 return re_node。 } /* 搜尋右子樹替代節點 */ 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。 } /* 搜尋左子樹替代節點 */ 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。 } /* 調整二元搜尋樹的鏈結， link為 r表示處理右鏈結，為 l表處理左鏈結， 為 m則將鏈結指向 NULL */ void connect(struct student *node, char link) { struct student *parent。 parent = search_p(node)。 /* 搜尋父節點 */ /* 節點為父節點左子樹的狀況 */ 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 /* 節點為父節點右子樹的狀況 */ if(link == 39。 r39。 ) /* link為 r */ parentrlink = noderlink。 else if(link == 39。 l39。 ) /* link為 l */ parentrlink = nodellink。 else /* link為 m */ parentrlink = NULL。 } /* 搜尋 node的父節點 */ 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 二元搜尋樹 (續 )  利用二元搜尋樹來排序一組資料  步驟：  先將輸入資料置於一個 queue中  以第一個資料當做二元樹的樹根  以後的資料與樹根比較，若小於則成為樹根之左子樹，若大於則為其右子樹，如此一直遞迴式的進行  建立完畢後再以中序法追蹤  若要由小而大排序，則將結果直接輸出。 若是由大而小，則先將結果置於 stack中，以後再相反輸出 35 引線二元樹  引線二元樹 (threaded binary tree)  一般二元樹中有一半以上的 link field是 null link，為便利儲存及節省 link欄位的浪費，將空的 link換成一種叫引線 (thread)的指標  引線二元樹的資料結構 LB IT R B ITR LINKDATALL INK1. 當 LBIT=1時， LLINK是正常指標 2. 當 LBIT=0時， LLINK是引線 3. 當 RBIT=1時， RLINK是正常指標 4。