从二叉树中删除节点搜索

Question

我想我的代码中有多个错误用于从BST中删除一个节点。我无法弄清楚什么！这是我的代码。提前致谢！我发现

void del(int val){ 
    help = root; 
    f = help; 
    while (help){ 
     if(help->data==val) break; 
     f = help; 
     if (val > help-> data) help = help->right; 
     else help = help->left; 
    } if(help->data != val) printf("\nElement not found!"); 
    else{ 
     printf("Element found!"); 
     target = help; 
     if(val>f->data){ 
      if(target->right && !target->left) {f->right = target->right; f = target->right;} 
      else {f->right = target->left; f = target->left;} 
     } else{ 
      if(target->right && !target->left) {f->left = target->right; f = target->right;} 
      else {f->left = target->left; f = target->left;} 
     } 
     while(help ->right) help = help->right; 
     if(help->left) help = help->left; 
     f->right = help; 
     free(target); 
    } 
} 

Answer 1

的一个错误是，如果一个人要删除左树中的节点，那么最后几行可能无法正常工作，因为它们不是对称的。所以，让我们说，树的根目录为6，左边的孩子为4，右边的孩子为8.现在，你想删除4.因此，当你在第一个while子句中找到节点后， “if（val> f-> data）{”的else子句。此时，f将指向6，target和help将指向4.现在，您将f的左侧设置为target的右侧，所以6的左侧将指向NULL，f本身将指向NULL。到现在为止还挺好！但是，一旦你进入while循环，因为帮助没有正确的节点，帮助将继续指向6.最后，你做出正确的节点f（btw，此时f已经为NULL）来帮助和你会最终崩溃！

while (help->right) 
    help = help->right; 

if (help->left) 
     help = help->left; 

f->right = help; 

另一个错误是，您不更新根指针，因此最终会删除根节点。

一种更简单的方法是将其分成三种情况。我为这三种情况提供了代码。对这三种情况分别使用一个样本树，然后对其进行调试/测试。首先，如果找到的节点（您的文件while循环正在执行）没有子节点，则将其删除并将其父项设置为NULL，然后完成操作。这是第一种情况的一个粗略的一切：

/* If the node has no children */ 
    if (!help->left && !help->right) { 
     printf("Deleting a leaf node \n"); 
     f = help->parent; 
     if (f) { 
      if (value > f->value) 
       f->right = NULL; 
      else 
       f->left = NULL; 
     } 
     /* If deleting the root itself */ 
     if (f->value == root) { 
      root = NULL; 
     } 
     free(help); 
     return 0; 
    } 

其次，如果发现节点具有唯一的孩子（左或右），然后拼接出来，并找到节点的孩子成为了兴田孩子父节点。这是第二种情况：

/* If the node has only one child node */ 
    if ((help->left && !help->right) 
     || (!help->left && help->right)) { 
     printf("Deleting a node with only one child \n"); 
     f = help->parent; 

     if (help->left) { 
      child_node = help->left; 
     } else { 
      child_node = help->right; 
     } 

     if (f) { 
      if (value > f->value) { 
       f->right = child_node; 
      } else { 
       f->left = child_node; 
      } 
     } else { 
      /* This must be the root */ 
      root = child_node; 
     } 
     free(help); 
     return 0; 
    } 

第三种情况是有难度的 - 在这里找到的节点具有两个子节点。在这种情况下，您需要找到节点的后继节点，然后将找到的节点的值替换为后继节点，然后删除后继节点。这里是第三种情况：

/* If the node has both children */ 
    if (help->left && help->right) { 
     successor_found = find_successor(help, help->data); 
     printf("Deleting a node with both children \n"); 
     if (successor_found) { 
      successor_value = successor_found->value; 
      del(successor_found->value); 
      help->value = successor_value; 
     } 
     return 0; 
    } 

而且，在这里被发现的代码接班人：

binary_node_t *node find_successor(binary_node_t *node, int value) { 

    binary_node_t *node_found; 

    if (!node) {return NULL; } 

    node_found = node; 
    old_data = node->data; 

    /* If the node has a right sub-tree, get the min from the right sub-tree */ 
    if (node->right != NULL) { 
     node = node->right; 
     while (node) { 
      node_found = node; 
      node = node->left; 
     } 
     return node_found; 
    } 

    /* If no right sub-tree, get the min from one of its ancestors */ 
    while (node && node->data <= old_data) { 
     node = node->parent; 
    } 
    return (node); 
} 

Answer 2

typedef struct xxx { 
     struct xxx *left; 
     struct xxx *right; 
     int data; 
     } ; 
#define NULL (void*)0 
#define FREE(p) (void)(p) 

void treeDeleteNode1 (struct xxx **tree, int data) 
{ 
    struct xxx *del,*sub; 

     /* Find the place where node should be */ 
    for (  ; del = *tree; tree = (data < del->data) ? &del->left : &del->right) { 
     if (del->data == data) break; 
     } 
     /* not found: nothing to do */ 
    if (!*tree) return; 

     /* When we get here, `*tree` points to the pointer that points to the node_to_be_deleted 
     ** If any of its subtrees is NULL, the other will become the new root 
     ** ,replacing the deleted node.. 
     */ 
    if (!del->left) { *tree = del->right; FREE(del); return; } 
    if (!del->right) { *tree = del->left; FREE(del); return; } 

     /* Both subtrees non-empty: 
     ** Pick one (the left) subchain , save it, and set it to NULL */ 
    sub = del->left; 
    del->left = NULL; 

     /* Find leftmost subtree of right subtree of 'tree' */ 
    for (tree = &del->right; *tree; tree = &(*tree)->left) {;} 
     /* and put the remainder there */ 
    *tree = sub; 
    FREE(del); 
} 

被称为像：

... 
struct xxx *root; 
... 
treeDeleteNode1(&root, 42); 
...