作者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