0

我一直在尝试在 C 中实现一个函数，该函数删除二叉树中的一个节点，该二叉树应该（理论上）处理三种所有情况，即：

  • 节点是一片叶子
  • 节点有一个孩子
  • 节点有两个孩子

有没有办法在不单独检查每个案例的情况下处理整个删除功能？正如下面的评论者指出的那样，我确实检查了很多案例，也许整个问题可以通过检查一个基本案例来递归解决。

我对删除树中具有父节点且本身是两个子节点的父节点的节点特别感兴趣。

下面的两个答案都很有用，但我认为它们并不能完全解决问题。

这是我所拥有的：

typedef struct Node
{
    int key;
    int data;
    struct Node *left;
    struct Node *right;
    struct Node *parent;
} Node;

/* functions that take care of inserting and finding a node and also traversing and freeing the tree */
...

void delete(Node *root, int key)
{
    Node *target = find(root, key); // find will return the node to be deleted

    Node *parent = target->parent; // parent of node to be deleted

    // no children
    if (target->left == NULL && target->right == NULL)
    {
        // is it a right child
        if (target->key > parent->key)
            parent->right = NULL;
        // must be a left child
        else
            parent->left = NULL;

        free(target);
    }

    // one child
    else if ((target->left == NULL && target->right != NULL) || (target->left != NULL && target->right == NULL))
    {
        // here we swap the target and the child of that target, then delete the target
        Node *child = (target->left == NULL) ? target->right : target->left;
        child->parent = parent;
        if (parent->left == target) parent->left = child;
        else if (parent->right == target) parent->right = child;
        free(target);
    }
    // two children
      else
    {

        // find the largest node in the left subtree, this will be the node
        // that will take the place of the node to be deleted
        Node *toBeRepl = max(target->left);

        // assign the data of the second largest node
        target->key   = toBeRepl->key;
        target->data  = toBeRepl->data;

        // if new node immediately to the left of target 
        if (toBeRepl == target->left)
        {   
            target->left  = toBeRepl->left;
            Node *newLeft = target->left;
            if (newLeft != NULL) newLeft->parent = target;
        }
        else
        {
            delete(target->left, toBeRepl->key);
            // Node *replParent = toBeRepl->parent;
            // replParent->right = NULL;
        }
}

非常感谢您的反馈。

编辑：为了澄清，我试图删除一个特定的节点而不触及它的子树（如果有的话）。它们应该保持完整（我已经通过交换要删除的节点的值和（根据情况）其子树的节点之一来处理这一点）。

编辑：我将以下维基百科文章用作参考： http
://en.wikipedia.org/wiki/Binary_search_tree#Deletion 这是我想到在有两个孩子的情况下交换节点值的地方，尤其是引用：

将要删除的节点称为 N。不要删除 N。而是选择其有序后继节点或有序前驱节点 R。将 N 的值替换为 R 的值，然后删除 R。

对于上述情况，C++ 中有一些有趣的代码，但是我不确定交换究竟是如何发生的：

else    //2 children
{
        temp = ptr->RightChild;
        Node<T> *parent = nullptr;

        while(temp->LeftChild!=nullptr)
        {
                parent = temp;
                temp = temp->LeftChild;
        }
        ptr->data = temp->data;
        if (parent!=nullptr)
                Delete(temp,temp->data);
        else
                Delete(ptr->rightChild,ptr->RightChild->data);
}

有人可以解释一下那部分发生了什么吗？我假设递归与用户评论的方法相似。

4

3 回答 3

1

我会使用递归来做到这一点，假设您null在树的末尾找到 null 将是“返回”或返回条件。

一种可能的算法是：

Node* delete(Node *aNode){
  if(aNode->right != NULL)
     delete(aNode->right);
  if(aNode->left != NULL)
     delete(aNode->left);
  //Here you're sure that the actual node is the last one
  //So free it! 
  free(aNode);
  //and, for the father to know that you're now empty, must return null
  return NULL;

}

当然，它有一些错误，但这是主要思想。这个实现就像dfs。希望这可以帮助。

[编辑] 节点 *aNode 已修复。忘了星星，我的错。

于 2012-12-28T17:12:39.043 回答
1

我在代码中看不到任何“不雅”，这种格式和注释代码很难获得。但是，是的，您可以将删除函数中的 if-else 结构减少到一种情况。如果您查看有关删除操作的最抽象概念，您会注意到所有情况基本上都归结为最后一种情况（删除具有两个子节点的节点）。

您只需在其中添加几行。就像在 toBeRepl = max(left-sub-tree) 之后一样，检查它是否为 NULL，如果是则 toBeRepl = min(right-sub-tree)。

因此，案例 1（无子节点）：假设您的max()方法已正确实现，它将NULL作为左子树上最右边的元素返回，右子树上也是如此min()。用 toBeRepl 替换您的目标，您将删除您的节点。

案例 2（一个孩子）：如果max()确实返回NULL，min()则不会，反之亦然。所以你会有一个非 NULL toBeRepl。再次用这个新的替换你的目标toBeRepl，你就完成了。

案例3（两个孩子）：同案例2，只是你可以确定max()不会回来NULL。

因此，您的整个delete()函数将归结为最后一条else语句（有一些更改）。类似的东西：

Node *toBeRepl = max(target->left);
if toBeRepl is NULL
{
  toBeRepl = min(target->right);
}

if toBeRepl is not NULL
{
  target->key = tobeRepl->key;
  target->data = toBeRepl->data;

  deallocate(toBeRepl); // deallocate would be a free(ptr) followed by setting ptr to NULL
}
else
{
  deallocate(target);
}
于 2012-12-28T18:06:41.980 回答
0

我很久以前完成了这个，我认为为遇到同样问题的人添加一个示例答案会很好（考虑到这个问题已经积累了 400 多个视图）：

/* two children */
else
{
    /* find the largest node in the left subtree (the source), this will be the node
     * that will take the place of the node to be deleted */
    Node* source = max(target->left);

    /* assign the data of that node to the one we originally intended to delete */
    target->key   = source->key;
    target->data  = source->data;

    /* delete the source */
    delete(target->left, source->key);
}

维基百科有一篇很棒的文章启发了这段代码。

于 2013-06-24T13:55:08.013 回答