作者yantchen (球童Yanting)
看板NTUE-CS101
標題[課業] BST殺人卡關看這
時間Tue Dec 29 23:33:03 2009
請回想一下鏈結串列
a>b>c>null
如果要砍 c 的時候 不是直接 delete c; 就好
這樣等下 b 會以為他後面還有人 印出來的時候硬去找 c 他就會跟你說要不要回報了
砍 b 也是 直接砍 b
a 會找不到 c
所以
請記得
如果 串列 / 樹 裡面
要砍節點
1. 如果他沒有小孩
請先通知他父親 "你絕後了" 再殺了他
2. 如果他有一個小孩
請先把他小孩交給他父親 再殺了他
3. 如果他有兩個小孩
他不能死 必須找左邊最大的 或是右邊最小的 頂替他
找父親怎麼做?
再找這個節點的時候 順便記錄他父親是誰
void del(int val)
{
treenode *me = root, *father = NULL, *child = NULL;
while(me!=NULL)
{
if(val==me->value) break;
else if(val<me->value) { father=me; me=me->left; } // 找他順便紀錄父親
else if(val>me->value) { father=me; me=me->right; } // 找他順便紀錄父親
}
if(me==NULL) { cout<<"沒這個人 殺不到勒"; return; }
if(me->left==NULL&&me->right==NULL) // 沒有小孩
{
if(me==root) {
root==NULL;
}
else {
if(father->left==me) father->left=NULL; // 告訴他爸他絕後了
if(father->right==me)father->right=NULL;
}
delete me; // 然後再殺他
}
else if(me->left==NULL&&me->right!=NULL) // 右邊有小孩
{
if(me==root){
root=root->right;
}
else{
if(father->left==me) father->left=me->right; // 小孩交給他爸
if(father->right==me)father->right=me->right;
}
}
else if(me->left!=NULL&&me->right==NULL) // 左邊有小孩
{
if(me==root){
root=root->left;
}
else{
if(father->left==me) father->left=me->left; // 小孩交給他爸
if(father->right==me)father->right=me->left;
}
}
else // 萬惡的兩個小孩
{
child=me->left; // 找左邊最大的
father=me; // 這裡的father 是左邊最大的人的父親
while(child->right!=NULL)
{
father=child;
child=child->right;
}
if(child->left!=NULL) father->right=child->left;
me->value=child->value; // 你的小孩跟位子 要找左邊最大的來頂替
// 左邊最大的人頂替你了 所以變成那個人死
if(father->left == child) father->left = NULL;
if(father->right == child) father->right = NULL;
delete child;
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 120.127.36.183
1F：推 didi12252001:挖靠 這個不推不行了!!!! 12/29 23:51
2F：推 rockmyangel:好可怕!殺小孩xd這篇像是懸疑推理 ~~ 12/30 00:36