【资料结构】树的操作 -引线,堆积,二元搜寻树

上篇连结:树的定义与追踪

引线树

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.二元搜寻树是进行搜寻、插入、删除最好的资料结构。
  

范例

实作:二元搜寻树的建立、搜寻、插入、删除
【资料结构】二元搜寻树:添加节点
【资料结构】二元搜寻树:删除节点

待补