刪除在二叉搜索樹

所以，當我在二叉搜索樹刪除，我需要有一個像7不同的情況，即刪除在二叉搜索樹

左葉;
Right Leaf;
左小孩只有左小孩。 //i.e要刪除的節點是其父節點的左側子節點，並且只剩下子節點。
左兒童只有正確的孩子。
右孩子只有左孩子。
正確的孩子只有正確的孩子。
要刪除的節點具有兩個孩子，即右和左。

現在，當這段代碼使用if-else它變得非常討厭..是否有任何其他方式做到這一點。

這裏是我的代碼片段

if(current->left==NULL && current->right==NULL && current->key<prev->key) //left leaf 
prev->left=NULL; 
else if(current->left==NULL && current->right==NULL && current->key>prev->key) // right  leaf 
prev->right=NULL; 
else if(current->left!=NULL && current->right==NULL && current->key<prev->key) // left  child with one child 
prev->left=current->left; 
else if(current->left==NULL && current->right!=NULL && current->key<prev->key) 
prev->left=current->right; 
else if(current->left!=NULL && current->right==NULL && current->key>prev->key) 
prev->right=current->left; 
else if(current->left==NULL && current->right!=NULL && current->key>prev->key) 
prev->right=current->left; 
else if(current->left!=NULL && current->right!=NULL) 
{ 
    check=current->right; 
    check1=check; 
    while(check->left!=NULL) 
    { 
    check1=check; 
    check=check->left; 
    } 
    *current=*check; 
    check1->left=NULL; 
}

來源

2011-09-30 Kraken

你可以把它比簡單了很多，簡單地從一個BST刪除節點（二叉搜索樹）時限制自己三種情況：

一沒有孩子的節點（葉）：只是將其刪除 - 沒有什麼特別需要做
一個子節點：將其刪除，並移動子女在其位
一個節點有兩個孩子：與交換，要麼它的順序前任或繼任者，然後將其刪除

wiki page包含一個如何在代碼中查找的例子。

或者在C一個非常簡單的例子：

if (current->left==NULL && current->right==NULL) { 
    /* leaf node */ 
    bst_replace(current, NULL); 
} 
else if (current->left==NULL || current->right==NULL) { 
    /* node with one child */ 
    bst_replace(current, ((current->left) ? current->left : current->right)); 
} 
else { 
    /* node with two children */ 
    Node* successor = bst_next(current); 
    current->data = successor->data; 
    bst_replace(successor, successor->right); 
}

來源

2011-09-30 05:18:08

說我要刪除的節點是左邊的葉子，現在在節點的父級，我需要知道它是左邊的孩子還是右邊的孩子，因爲我必須在該位置放置一個空值。所以不會我需要兩種不同的情況？ – Kraken

@Karan：如果你把它推出來，是的，但是我試圖提出的一點是將這些細節抽象出來，並將實際的刪除侷限於這三種情況。有關示例，請參閱編輯答案。 –

也許我可以遍歷，直到只有父母，然後檢查它的子節點是否是最後一片葉子，然後將其刪除正確嗎？沒有必要到達節點自己刪除它，直到父母會減少約一半的情況下？ – Kraken

刪除NULL指針沒有任何不良影響。所以，你應該可以做到這一點，沒有特殊情況。基本部分就是：

delete current->left; 
delete current->right;

來源

2011-09-30 05:14:41

我真的不明白用於刪除此協議。你似乎沒有一個二進制搜索樹（在樹中沒有排序）。

但只是使代碼簡單。你可以做這樣的事情：

bool b1 = (current->left == NULL); 
bool b2 = (current->right == NULL); 
bool b3 = (current->key > prev->key); 

int decision_case = b1 * 4 + b2 * 2 + b3; 

switch(decision_case) { 
    case 0: // fill in code here 
      break; 
    ... 
    ... 
    case 7: // fill in code here 
      break; 
}

此外，你應該使用刪除避免此內存泄漏。希望有所幫助。

來源

2011-09-30 05:33:42 Navneet

刪除在二叉搜索樹

回答

相關問題