删除二叉树中的节点

Question

删除节点后尝试打印树时出现分段错误。

#include <stdio.h>
#include <stdlib.h>

typedef struct tree {
    int val;
    struct tree *left, *right;
} tree;

void insert (tree **root, int val) {
    tree *new_node, *parrent, *cur;
    new_node = malloc(sizeof(tree));
    new_node->val = val;
    new_node->left = new_node->right = NULL;
    if (!*root)
        *root = new_node;
    else {
        cur = *root;
        while (cur) {
            parrent = cur;
            if (cur->val > val)
                cur = cur->left;
            else
                cur = cur->right;
        }
        if (parrent->val > val)
            parrent->left = new_node;
        else
            parrent->right = new_node;
    }
}

tree *search (tree *root, int val) {
    if (!root)
        return root;
    while (root && root->val != val) {
        if (root->val > val)
            root = root->left;
        else
            root = root->right;
    }
    return root;
}

void delete (tree **node) {
    tree *tmp;
    if (!(*node)->left) {
        tmp = *node;
        *node = (*node)->right;
        free(tmp);
    }
    else if (!(*node)->right) {
        tmp = *node;
        *node = (*node)->left;
        free(tmp);
    }
    else {
        for (tmp = (*node)->left; tmp->right; tmp = tmp->right)
            continue;
        tmp->right = (*node)->right;
        tmp = *node;
        *node = (*node)->left;
        free(tmp);
    }
}

void preorderTraversal (tree *root) {
    if (root) {
        printf("%d\n", root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

int main () {
    tree *root = NULL, *node;
    for (int i = 0; i < 5; i++)
        insert(&root, i);
    preorderTraversal(root);
    node = search(root, 3);
    delete(&node);
    preorderTraversal(root);
    return 0;
}

编译成功，编译器没有显示任何警告。

gcc tree.c -Wall -g -o tree

算法简述：如果一个节点只有一个子节点，我们将该节点的值更改为其子节点的值，这不会破坏树。如果一个节点有两个子节点，我们在左节点的子树中查找最大节点，并将其右值更改为右节点值。然后我们使该节点等于左节点的值，这也不会破坏树。

---

P.S - 算法看起来是正确的，但实现可能是错误的。另外，我不知道如何实现树并选择一致的值，这可能不是一个好主意，但删除操作甚至应该适用于示例。

Answer 1

您的

delete

方法有错误。

考虑以下示例树结构。

             +--------------------+                        
             |    Node: 0x0000    |                        
           +-|       val: 2       |-+                      
           | | l:0x0001 r: 0x0002 | |                      
           v +--------------------+ v                      
+--------------------+   +--------------------+            
|    Node: 0x0001    |   |    Node: 0x0002    |            
|       val: 1       |   |       val: 3       |-+          
|  l: null r: null   |   | l: null r: 0x0003  | |          
+--------------------+   +--------------------+ v          
                                     +--------------------+
                                     |    Node: 0x0003    |
                                     |       val: 4       |
                                     |  l: null r: null   |
                                     +--------------------+

如果你有一个指向节点

0x0002

的指针，并且你调用delete，这将：

1. 测试

   l

   的

   Node 0x0002

   为空，所以会进入第一个

   if

   条件
2. 将

   Node 0x0003

   内的值赋给

   Node 0x0002

   完成这一步后，树将如下所示：

             +--------------------+                        
             |    Node: 0x0000    |                        
           +-|       val: 2       |-+                      
           | | l:0x0001 r: 0x0002 | |                      
           v +--------------------+ v                      
+--------------------+   +--------------------+            
|    Node: 0x0001    |   |    Node: 0x0002    |            
|       val: 1       |   |       val: 4       |            
|  l: null r: null   |   |  l: null r: null   |            
+--------------------+   +--------------------+            
                                     +--------------------+
                                     |    Node: 0x0003    |
                                     |       val: 4       |
                                     |  l: null r: null   |
                                     +--------------------+

注意不再有指向

Node 0x0003

的指针。

3. 拨打

   free

   上的

   Node 0x0002

   。完成这一步后，树将如下所示：

             +--------------------+                        
             |    Node: 0x0000    |                        
           +-|       val: 2       |-+                      
           | | l:0x0001 r: 0x0002 | |                      
           v +--------------------+ |                      
+--------------------+              |                      
|    Node: 0x0001    |              +->                    
|       val: 1       |                                     
|  l: null r: null   |                                     
+--------------------+                                     
                                     +--------------------+
                                     |    Node: 0x0003    |
                                     |       val: 4       |
                                     |  l: null r: null   |
                                     +--------------------+

请注意，

Node 0x0000

指向空白区域，其中

Node 0x0002

（在删除之前）所在的位置。另外，

Node 0x0003

现在已被隔离，并且会泄漏内存。

要解决此问题，正如评论者指出的那样，您需要：

1. 更新已删除节点的父节点以指向新的子节点。这意味着在我们的示例中将

   Node 0x0000

   的 r 值设置为

   0x0003

2. 不是释放已删除的节点，而是释放子节点。在我们的示例中，这意味着在分配后删除

   Node 0x0003

   。