二叉樹刪除詳解
來源：程序員人生 發布時間：2014-12-22 09:03:10 閱讀次數：2849次
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];
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
