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

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

引线树

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 )

右子树为空:
右子树不为空:

【资料结构】引线的练习实作

堆积树

规则

最大树:树的每个节点都不小于其子树。

最小树:树的每个节点都不大于其子树。

最大堆积树/最小堆叠树:为最大最小树的完全二元树。

时间複杂度

插入及演算法

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

範例

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

待补