缺失的二叉搜索树 [英] Deletion in binary search tree

问题描述

所以，当我在二叉搜索树删除，我需要有一个像7不同的情况即

1. 左叶;


2. 右键叶;


3. 左子，只留孩子。 //i.e要删除的节点是它的左孩子的父母和已经只剩下孩子。


4. 左孩子只有右孩子。


5. 右键孩子，只留孩子。


6. 右键孩子才对孩子。


7. 节点被删除有两个孩子，即左，右。

现在，当这个code使用的if-else 它得到pretty讨厌的..有这样做的任何其他方式。

下面是我的code段

 如果（电流 - ＆GT;左== NULL和放大器;＆放大器;电流 - ＆GT;右== NULL和放大器;＆放大器;电流 - ＆GT;键＆LT; preV-＆GT密钥）//左叶
preV-GT＆;左= NULL;
否则，如果（电流 - ＆GT;左== NULL和放大器;＆放大器;电流 - ＆GT;右== NULL和放大器;＆放大器;电流 - ＆GT;密钥GT; preV-GT和密钥）//右叶
preV-GT＆右= NULL;
否则，如果（电流 - ＆GT;左= NULL＆放大器;！＆放大器;电流 - ＆GT;右== NULL和放大器;＆放大器;电流 - ＆GT;键＆LT; preV-＆GT;键）//左子与一个孩子
preV-GT＆;左=电流 - ＆GT;左;
否则，如果（电流 - ＆GT;左== NULL和放大器;＆安培; CURRENT-＆GT;右= NULL＆放大器;！＆放大器;电流 - ＆GT;密钥LT; preV-GT和密钥）
preV-GT＆;左=电流 - ＆GT;的权利;
否则，如果（电流 - ＆GT;左= NULL＆放大器;！＆放大器;电流 - ＆GT;右== NULL和放大器;＆放大器;电流 - ＆GT;密钥GT; preV-GT和密钥）
preV-GT＆右=电流 - ＆GT;左;
否则，如果（电流 - ＆GT;左== NULL和放大器;＆安培; CURRENT-＆GT;右= NULL＆放大器;！＆放大器;电流 - ＆GT;密钥GT; preV-GT和密钥）
preV-GT＆右=电流 - ＆GT;左;
否则，如果（电流 - ＆GT;左= NULL＆放大器;！＆放大器;电流 - ＆GT;！右= NULL）
{
    检查=电流 - ＆GT;的权利;
    CHECK1 =检查;
    而（入住＆GT;！左= NULL）
    {
    CHECK1 =检查;
    检查=入住＆GT;左;
    }
    *电流= *检查;
    check1-＆GT;左= NULL;
}
 

解决方案

您可以把它比简单了很多，只需从BST（二叉搜索树）删除节点时限制自己三种情况：

1. 没有孩子的节点（叶）：只是将其删除 - 没有什么特别需要做的事情


2. 有一个孩子节点：删除和移动子在自己的位置


3. 有两个孩子的节点：要么用它在顺序predecessor或继任者交换，然后将其删除

借助维基页面包含这怎么会看在code为例

或者在C一个非常基本的例子：

 如果（电流 - ＆GT;左== NULL和放大器;＆放大器;电流 - ＆GT;右== NULL）{
    / *叶节点* /
    bst_replace（电流，NULL）;
}
否则，如果（电流 - ＆GT;左== NULL ||电流 - ＆GT;右== NULL）{
    / *有一个子节点* /
    bst_replace（电流，（（电流 - ＆GT;左）电流 - ＆GT;左：电流 - ＆GT;右））;
}
其他{
    / *有两个孩子节点* /
    节点*继任= bst_next（电流）;
    电流 - ＆GT;数据= successor-＆GT;数据;
    bst_replace（继任者，successor-＆GT;右）;
}
 

So when I delete in binary search tree, do I need to have like 7 different cases i.e.

1. Left Leaf;
2. Right Leaf;
3. Left child with only left child. //i.e the node to be deleted is the left child of it's parent and it has only left child.
4. Left Child with only right child.
5. Right child with only left child.
6. Right child with only right child.
7. Node to be deleted has both the children i.e. right and left.

Now when this code is using if-else it gets pretty nasty.. is there any other way of doing this.

Here is my code snippet

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;
}

解决方案

You can keep it a lot simpler than that, and simply restrict yourself to three cases when deleting a node from a BST (binary search tree) :

1. a node without children (a leaf) : just remove it - nothing special needs to be done
2. a node with one child : remove it, and move the child in its place
3. a node with two children : swap it with either its in-order predecessor or successor, and then remove it

The wiki page contains an example of how this could look in code.

Or as a very basic example in 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);
}

这篇关于缺失的二叉搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！