作者Nozaki (NA)
看板C_and_CPP
標題[問題] 二元搜尋樹-刪除節點的演算法
時間Wed Aug 31 20:42:12 2011
在二元搜尋樹裡 我看不懂要刪除的節點左右還有節點的情況下的演算法
也就是其中的這段:
else{
tempNode=nodePtr->right;
while(tempNode->left)
tempNode=tempNode->left;
tempNode->left=nodePtr->left;
tempNode=nodePtr;
nodePtr=nodePtr->right;
delete tempNode;
}
完整的演算法如下： 可以幫忙說明一下嗎orz 已經想了一個晚上了還是不懂
謝謝!
void BinaryTree::deleteNode(int num,TreeNode *&nodePtr)
{
TreeNode *tempNode;
if(num<nodePtr->data)
deleteNode(num,nodePtr->left);
else if (num>nodePtr->data)
deleteNode(num,nodePtr->right);
else{
if(nodePtr==NULL)
cout<<"NUll node can not be deleted";
else if(nodePtr->right==NULL)
{
nodePtr=nodePtr->left;
}
else if(nodePtr->left==NULL)
{
nodePtr=nodePtr->right;
}
else{
tempNode=nodePtr->right;
while(tempNode->left)
tempNode=tempNode->left;
tempNode->left=nodePtr->left;
tempNode=nodePtr;
nodePtr=nodePtr->right;
delete tempNode;
}
showPreOrder(root);
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 68.70.61.100
推 ericinttu:你知道 binary search tree 是怎麼排資料的嗎? 08/31 20:45
推 suhorng:當左右子樹都存在時，選右子樹的最左邊節點來替代被刪除的 08/31 20:46
→ suhorng:節點，可以保證大小順序不被破壞。 08/31 20:46
→ suhorng:不過有沒有漏? 08/31 20:48
推 flere:當你只是要交作業具有BST的效果,然後刪除真的做不出來 08/31 21:15
→ flere:有一個好方法就是多加一個計數器欄位,輸入的時候就+1 08/31 21:15
→ flere:或是看情況是維持1還是+1,刪除的時候就-1或是變0 08/31 21:16
→ flere:輸出的時候只要輸出>0的部分就好,不過前提是 08/31 21:16
→ flere:你如果是一個很大的程式需要好的時間速度的話,就不能這樣搞 08/31 21:16
→ flere:刪除太多點然後輸出還每次經過會太慢,如果只是作業.... 08/31 21:17
→ firejox:這樣刪除 高度會變耶... 08/31 21:56
→ flere:高度會一直增加,不過不是AVL要旋轉的話倒是可以使用 08/31 22:05
→ firejox:調整一下刪除的方式就可以 避免了 08/31 22:08
→ asilzheng:右邊的比該節點大 左邊的比該節點小 右枝的最左邊 08/31 22:53
→ asilzheng:即是比他大的中最小者 拿來取代原本的節點不會破壞結構 08/31 22:54
→ asilzheng:不過 原本指向右子樹最左邊的那個節點 要改指為null吧? 08/31 22:55
→ firejox:要先free完再null 08/31 23:10
→ firejox:但是假如沒有balance的話就還要在判斷 08/31 23:18
推 gsrr:我也看不懂 :) , 這有寫錯吧. 09/01 00:17
→ Nozaki:謝謝大家 我再參透一下... 09/01 20:58