datastructureinc樹狀結(jié)構(gòu)-文庫吧
2025-08-26 21:45 本頁面
【正文】 inorder(treerlink)。 } void preorder(Node type *tree) { if (tree != NULL){ printf(“%d”, treedata)。 preorder(treellink)。 preorder(treerlink)。 } void postorder(Node type *tree) { if (tree != NULL){ postorder(treellink)。 postorder(treerlink)。 printf(“%d”, treedata)。 } ABCDEF GHIJABCDEF GHIAB CD EF GH I? 將一般的樹轉(zhuǎn)化為二元樹的方法 ? 一般採用左子右弟的表示法，將樹化為二元樹，其步驟如下： ? 將節(jié)點的所有兄弟節(jié)點連接在一起 ? 把所有不是連接到最左子點的子節(jié)點鏈結(jié)刪除 ? 順時針旋轉(zhuǎn) 45度 ANMLKJIHGFEDCBANMLKJIHGFEDCB? 將樹林轉(zhuǎn)化為二元樹的方法 ? 步驟： ? 先將樹林中的每棵樹化為二元樹 (不旋轉(zhuǎn) 45度 ) ? 把所有二元樹利用樹根節(jié)點全部鏈結(jié)在一起 ? 順時針旋轉(zhuǎn) 45度 IHADCB F GEIHADCB F GEIHADCB F GEIHADCBFGE18 二元樹 (續(xù) ) ? 算術(shù)式的二元樹表示法 ? 轉(zhuǎn)換規(guī)則： ? 考慮運算子的優(yōu)先權(quán) (priority)與結(jié)合性(associativity)適當?shù)挠枰跃幪? ? 由編號大至小依序處理，最大的為樹根，然後分成兩邊，再依次找各邊最大的為子樹樹根，直到所有的運算子皆處理完畢 (一 )依 運算順序在各運算子下編號A + B * C D * E(二 )由 編號大的依序處理CBD*E+A *(a) (b )(c)(d )+D*E+20 二元樹 (續(xù) ) ? 唯一二元樹的決定 ? 給予一對 inorder及 preorder可以構(gòu)建出一個唯一的二元樹 ? 給予一對 inorder及 postorder可以構(gòu)建出一個唯一的二元樹 ? 給予一對 preorder及 postorder則不能構(gòu)建出一個唯一的二元樹 ? 參考 pp. 670~673 21 二元搜尋樹 ? 二元搜尋樹 (binary search tree) ? 定義：二元搜尋樹為一二元樹，可以是空集合，假使不是空集合，則樹中的每一節(jié)點均含有一鍵值 (key value)， 而且具有下列特性： ? 在左子樹的所有節(jié)點之鍵值均小於樹根的鍵值 ? 在右子樹的所有節(jié)點之鍵值均大於樹根的鍵值 ? 左子樹和右子樹亦是二元搜尋樹 ? 每個鍵值都不一樣 ? 當依序給定輸入值 (input sequence)， 我們可以建造一個二元搜尋樹，若使用中序追蹤此樹，可得到由小到大的排序結(jié)果 22 二元搜尋樹 (續(xù) ) ? 二元搜尋樹的加入 ? 當某節(jié)點欲加入時，只要逐一比對，依據(jù)鍵值的大小往右或往左，即可找到適當位置 5045654030 605045654030 60485045654030 604890加入 48 加入 90 /* 處理二元搜尋樹，將新增資料加入至二元搜尋樹中 */ void access(char name[], int score) { struct student *node, *prev。 if(search(name) != NULL) /* 資料已存在則顯示錯誤 */ { printf(Student %s has existed!\n, name)。 return。 } ptr = (struct student *) malloc(sizeof(struct student))。 strcpy(ptrname, name)。 ptrscore = score。 ptrllink = ptrrlink = NULL。 if(root == NULL) /* 當根節(jié)點為 NULL的狀況 */ root = ptr。 else /* 當根節(jié)點不為 NULL的狀況 */ { node = root。 while(node != NULL) /* 搜尋資料插入點 */ { prev = node。 if(strcmp(ptrname, nodename) 0) node = nodellink。 else node = noderlink。 } if(strcmp(ptrname, prevname) 0) prevllink = ptr。 else prevrlink = ptr。 } } /* 搜尋 target所在節(jié)點 */ struct student *search(char target[]) { struct student *node。 node = root。 while(node != NULL) { if(strcmp(target, nodename) == 0) return node。 else /* target小於目前節(jié)點，往左搜尋 */ if(strcmp(target, nodename) 0) node = nodellink。 else /* target大於目前節(jié)點，往右搜尋 */ node = noderlink。 } return node。 } 26 二元搜尋樹 (續(xù) ) ? 二元搜尋樹的刪除 ? 若刪除的是樹葉節(jié)點，則直接刪除之 ? 若刪除的不是樹葉節(jié)點，則在 左子樹找一最大的節(jié)點 或在 右子樹找一最小的節(jié)點 ，取代將被刪除的節(jié)點 27 二元搜尋樹 (續(xù) ) 5045654030 60456540306045654030 60取右子樹最小的節(jié)點 取左子樹最大的節(jié)點 /* 將資料從二元搜尋樹中移除 */ void removing(char name
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1