從二叉樹中刪除節點搜索

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); 
...