程序员人生 网站导航

二叉树删除详解

栏目:php教程时间:2014-12-22 09:03:10

2叉查找树的删除进程:

假定要删除树T中的某节点z,此时对如何删除z要分3种情况斟酌:

1.      z无子女:此时直接删除z便可

//z无子女 TREE-DELETE0(T,z) { if(z == left[p[z]]) left[p[z]] = NULL; else right[p[z]] = NULL; p[z] = NULL; }

2.      z有1个子女:用其子节点代替自己便可

//z只有1个子女 TREE-DELETE1(T,z) { //y为z的子女 if(left[z] !=NULL) y = left[z]; else y = right[z]; //用y代替z并将z删除 if(z == left[p[z]]) p[y] = left[p[z]]; else p[y] = right[p[z]]; p[z] = NULL; }

3.      z有两个子女:删除z的后继y(y不会有左子女,删除T中的y对应情况1或2),再用y的内容代替z的内容

//z有两个子女(这里实际上是删除y) TREE-DELETE2(T,z) { y = TREE-SUCCESSOR(z); x = right[y]; //z的后继y无子女 if(x == NULL) TREE-DELETE0(T,y); else TREE-DELETE1(T,y); key[z] = key[y]; }

删除2叉查找树的总进程:

TREE-DELETE(T,z) { if(z == root[T]) {root[T] = NULL;return;} bool bleftEmpty = (left[z] == NULL); bool brightEmpty = (right[z] == NULL); //左右均不为空 if(!bleftEmpty && !brightEmpty ) TREE-DELETE2(T,z); //左右均为空 else if(bleftEmpty && brightEmpty) TREE-DELETE0(T,z); //只有1个子女 else TREE-DELETE1(T,z); }

可简写为:

1.肯定y为要删除的节点:若z无子女则y为z;若z唯一1个子女则y为该子女;若z有两个子女则y为z的后继

if(left[z] == NULL || right[z] == NULL) y = z; else y = TREE-SUCCESSOR(z);
2.将x置为y的非空子女,若y无子女,则x置为空。若z无子女,则y为z,此时x为空;z有1个子女,y为z,此时x为z的子女;z有两个子女,y为z 的后继且由2叉查找树性质知y最多只有1个孩子,x为y的子女(可能为空)。综上,x要末为y的唯1的非空子女,要末为空。

if(left[y] != NULL) x = left[y]; else x = right[y];
3.通过修改p[y]和x的指针删除y。

if(x != NULL) p[x] = p[y]; if(p[y] == NULL) root[T] = x; else if(y == left[p[y]]) left[p[y]] = x; else right[p[y]] = x;
4.如果z有两个子女,则z的后继是要被删除的节点,应将y中的内容复制置z:

if(y != z) key[z] = key[y];
即:

TREE-DELETE(T,z) { //肯定y为要删除的节点 if(left[z] == NULL || right[z] == NULL) y = z; else y = TREE-SUCCESSOR(z); if(left[y] != NULL) x = left[y]; else x = right[y]; if(x != NULL) p[x] = p[y]; if(p[y] == NULL) root[T] = x; else if(y == left[p[y]]) left[p[y]] = x; else right[p[y]] = x; if(y != z) key[z] = key[y]; }


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐