iT邦幫忙

1

【資料結構】樹的操作 -引線,堆積,二元搜尋樹

c

上篇連結:樹的定義與追蹤

引線樹

n個樹葉中,會產生n+1個多餘的NULL空間浪費,因此建立有用的引線。  

規則

以中序追蹤建立陣列

引線節點左邊接中序左空間,右邊接中序右空間

無連接之引線向上根結點接(下圖範例先以999表示)

表示法與追蹤

在結構左右分別建立儲存TF的空間,T為引線,F為小孩
threaded_pointer insucc(threaded_pointer tree){
  threaded_pointer temp;
  temp = tree->right_child;
  if (!tree->right_thread)
    while (!temp->left_thread) 
      temp = temp->left_child;
  return temp;
}
void tinorder(threaded_pointer tree){
   /*引線二元樹 之中序追蹤  */
    threaded_pointer temp = tree;
    for ( ; ; ) {
        temp = insucc(temp);            
        if (temp==tree) break;
        printf(“%3c”, temp->data);
    }
}

插入及演算法

要求:插入一新節點成為節點 parent 的右小孩(right child )
  1. 右子樹為空:
  2. 右子樹不為空:

    【資料結構】引線的練習實作

堆積樹

規則

最大樹:樹的每個節點都不小於其子樹。

最小樹:樹的每個節點都不大於其子樹。

最大堆積樹/最小堆疊樹:為最大最小樹的完全二元樹。

時間複雜度

插入及演算法

void insert_max_heap(element item, int *n){
  int i;
  if (HEAP_FULL(*n)) {
    fprintf(stderr, “堆積已滿\n”);
    exit(1);
  } 
  i = ++(*n);
  while ((i != 1) && (item.key > heap[i/2].key)){heap[i] = heap[i/2];}
  heap[i]= item;
}

刪除及演算法


【資料結構】堆積樹(陣列法) 未完成

二元搜尋樹

說明

  • 1.根結點中的兩邊固定一邊大另一邊小。
  • 2.下方節點當作新的根結點,繼續符合一邊大一邊小的規則。
  • 3.無重複值。
  • 4.二元搜尋樹是進行搜尋、插入、刪除最好的資料結構。

範例

實作:二元搜尋樹的建立、搜尋、插入、刪除
【資料結構】二元搜尋樹:添加節點
【資料結構】二元搜尋樹:刪除節點

待補


尚未有邦友留言

立即登入留言