Как удалить более одного экземпляра числа в BST в C?

Question

Я создаю двоичное дерево поиска в C. У меня есть функции ввода, создания, предзаказа, пост-заказа и в порядке работы.

Однако я не могу понять, почему мой алгоритм удаления работает только для первого экземпляра удаляемого числа. Я понимаю, что сначала мои рекурсивные вызовы должны пересекать дерево назад, что позволяет мне искать дерево и удалять значения, как я их вижу, и исправлять указатели, но по какой-то причине функция только находит первый экземпляр, а затем останавливается. Вот пример:

Если мой вход в предзаказа составляет: 10 5 2 6 8 10 10 15 12 18, и я хочу, чтобы удалить 10

+-----------+------------------+-------------------------+ 
| Type |  Expected  |   Actual   | 
+-----------+------------------+-------------------------+ 
| Preorder | 5 2 6 8 15 12 18 | 5 2 6 8 10 10 15 12 18 | 
| Inorder | 2 5 6 8 12 15 18 | 2 6 8 5 12 15 18  | 
| Postorder | 2 12 18 15 8 6 5 | 8 6 2 12 18 15 5  | 
+-----------+------------------+-------------------------+ 

Совершенно очевидно, что он удаляется только первый экземпляр 10 и затем вернул корень. Как мне найти другие экземпляры и удалить их? Я понимаю структуру дерева после вызова удаления, но я не уверен, почему моя функция удаления не делает то, что я нарисовал на бумаге.

Вот код:

main.C

#include "Header.h" 

int main(int argc, const char * argv[]) { 
    char command[100]; 
    int value=0,input=0; 
    treeNode *new_node, *root; 
    root=NULL; 

    while(scanf("%s", command) > 0){ 
     if(strcmp(command, "insert") == 0){ 
      new_node=create_node(); 
      scanf("%d",&value); 
      new_node->e=value; 
      if(root==NULL){ 
       root=create_node(); 
       root->e=value; 
      }else 
       insert(root, new_node); 
     }else if(strcmp(command, "remove") == 0){ 
      scanf("%d",&input); 
      if(root==NULL) 
       printf("Tree Is Empty\n"); 
      else 
       root=removal(root, input); 
     }else if(strcmp(command, "postorder") == 0){ 
      if(root==NULL) 
       printf("Tree Is Empty\n"); 
      else{ 
       post_order(root); 
       printf("\n"); 
      } 
     }else if(strcmp(command, "preorder") == 0){ 
      if(root==NULL) 
       printf("Tree Is Empty\n"); 
      else{ 
       pre_order(root); 
       printf("\n"); 
      } 
     }else if(strcmp(command, "inorder") == 0){ 
      if(root==NULL) 
       printf("Tree Is Empty\n"); 
      else{ 
       in_order(root); 
       printf("\n"); 
      } 
     }else if(strcmp(command, "calculate") == 0){ 
      calculate(root); 
     } 
     else if(strcmp(command, "clear") == 0){ 
      root=clear_tree(root); 
     } 
    } 
    return 0; 
} 

header.h

#ifndef Header_h 
#define Header_h 

#include "stdheader.h" 

/*stdheader.h is just a header file with the standard headers in it like stdout etc...*/ 

typedef int element; 
typedef struct treeNode treeNode; 

struct treeNode{ 
    element e; 
    element count; 
    struct treeNode* Left; 
    struct treeNode* Right; 
}; 

treeNode* create_node(); 
void insert(treeNode*,treeNode*); 
treeNode* findMin(treeNode*); 
treeNode* removal(treeNode*,element); 
void post_order(treeNode*); 
void pre_order(treeNode*); 
void in_order(treeNode*); 
void calculate(treeNode*); 
int rec_calculate(treeNode*); 
treeNode* clear_tree(treeNode*); 


#endif /* Header_h */ 

function.c

#include "Header.h" 

treeNode* create_node(){ 
    treeNode *t=(treeNode*)malloc(sizeof(treeNode)); 
    t->Left=t->Right=NULL; 
    t->count=1; 
    return t; 
} 

void insert(treeNode* root,treeNode* new_node){ 
    if (new_node->e <= root->e) { 
     if (root->Left == NULL) 
      root->Left = new_node; 
     else 
      insert(root->Left, new_node); 
    } 

    if (new_node->e > root->e) { 
     if (root->Right == NULL) 
      root->Right = new_node; 
     else 
      insert(root->Right, new_node); 
    } 
} 

void in_order(treeNode *temp) { 
    if (temp != NULL) { 
     in_order(temp->Left); 
     printf("%d ", temp->e); 
     in_order(temp->Right); 
    } 
} 

void pre_order(treeNode *temp) { 
    if (temp != NULL) { 
     printf("%d ", temp->e); 
     pre_order(temp->Left); 
     pre_order(temp->Right); 
    } 
} 

void post_order(treeNode *temp) { 
    if (temp != NULL) { 
     post_order(temp->Left); 
     post_order(temp->Right); 
     printf("%d ", temp->e); 
    } 
} 

treeNode* findMin(treeNode* node) 
{ 
    treeNode* current = node; 

    while (current->Left != NULL) 
     current = current->Left; 

    return current; 
} 

treeNode* removal(treeNode* root, element e) 
{ 
    if (root == NULL) 
     return root; 

    if (e < root->e) 
     root->Left = removal(root->Left, e); 

    else if (e > root->e) 
     root->Right = removal(root->Right, e); 

    else 
    { 
     if (root->Left == NULL) 
     { 
      treeNode *temp = root->Right; 
      free(root); 
      return temp; 
     } 
     else if (root->Right == NULL) 
     { 
      treeNode *temp = root->Left; 
      free(root); 
      return temp; 
     } 
     treeNode* temp = root->Left; 
     root->e = temp->e; 
     root->Left = removal(root->Left, temp->e); 
    } 
    return root; 
} 

void calculate(treeNode *root){ 
    int value; 
    if (root == NULL){ 
     printf("Tree Is Empty\n"); 
    } 
    else if(root->Left==NULL&&root->Right==NULL) 
     printf("%d\n",root->e); 

    else{ 
     value=rec_calculate(root); 
     printf("%d\n",value); 
    } 
} 

int rec_calculate(treeNode *root){ 
    int A=0,B=0; 

    if (root == NULL) 
     return 0; 
    if(root->Left==NULL&&root->Right==NULL) 
     return root->e; 
    A=rec_calculate(root->Left); 
    B=rec_calculate(root->Right); 
    return (root->e)*(A-B); 
} 

treeNode* clear_tree(treeNode* root) 
{ 
     if(root) { 
      clear_tree(root->Left); 
      root->Left=NULL; 
      clear_tree(root->Right); 
      root->Right=NULL; 
      root=NULL; 
      free(root); 
     } 
    return root; 
    } 

Answer 1

Есть две ошибки здесь, как ложь в этом блоке вашего removal функция:

treeNode* temp = root->Left; 
root->e = temp->e; 
root->Left = removal(root->Left, temp->e); 

Вы удаляете старое значение root->Left, но по-прежнему могут быть повторяющиеся значения в левом поддереве. Вам понадобится второй вызов removal, который удаляет элемент, который был первоначально найден.

Кроме того, может быть неправильный элемент замены root->Left. Wikipedia описывает BST делеция таким образом:

Удаление узла с двумя детьми: вызвать узел должен быть удален N. Не удаляйте N. Вместо этого выберите либо его упорядоченную узел преемника или его упорядоченную предшественника узла , R. Скопируйте значение R в N, а затем рекурсивно вызовите delete на R, пока не достигнете одного из первых двух случаев. Если вы выберете наследодатель узла в порядке, так как правое вспомогательное дерево не является NIL (наш текущий случай имеет узел с двумя дочерними элементами), то его последователем в очереди является узел с наименьшим значением в его правом поддереве, который будет иметь максимум 1 поддерево, поэтому его удаление упадет в одном из первых двух случаев.

Обратите внимание, что узел-предшественник в порядке не только левого дочернего элемента, но и самый правый лист левого дочернего элемента. Поэтому вам нужно найти этот узел и использовать его значение вместо того, чтобы просто захватить значение левого ребенка.

Следующий список показывает рабочий removal функции и вспомогательные функции, чтобы найти предшественника элемент:

element predecessor(treeNode* root) 
{ 
    // Note: This function should only be called for 
    //  a root that has a non-null left sub-tree. 
    treeNode* n = root->Left; 
    while(n->Right != NULL) 
    { 
     n = n->Right; 
    } 
    return n->e; 
} 

treeNode* removal(treeNode* root, element e) 
{ 
    if (root == NULL) 
    { 
     return NULL; 
    } 

    if (e < root->e) 
    { 
     root->Left = removal(root->Left, e); 
     return root; 
    } 
    else if (e > root->e) 
    { 
     root->Right = removal(root->Right, e); 
     return root; 
    } 
    else 
    { 
     if (root->Left == NULL) 
     { 
      treeNode *temp = root->Right; 
      free(root); 
      return temp; 
     } 
     else if (root->Right == NULL) 
     { 
      treeNode *temp = removal(root->Left, e); 
      free(root); 
      return temp; 
     } 
     else 
     { 
      // Remove duplicate values first! 
      root->Left = removal(root->Left, e); 
      element replacement_e = predecessor(root); 
      root->e = replacement_e; 
      root->Left = removal(root->Left, replacement_e); 
      return root; 
     } 
    } 
}