Функция удаления для двоичного дерева

Question

Учитывая приведенный ниже код, что я могу использовать для создания функции удаления? Я пробовал несколько вещей, и я все время пытаюсь заставить его работать. Моя основная проблема заключается в попытке удалить узел с левым и правым дочерними элементами. Для узла, у которого нет дочерних элементов, я могу просто установить его родительский объект на нуль и освободить узел. Для одного ребенка просто установите родительский указатель на дочерний элемент и освободите узел. Как я могу сделать это для узла с двумя детьми как концептуально, так и в моем коде?

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

struct bin_tree { 
    int data; 
    struct bin_tree * right, * left; 
} bin_tree; 
typedef struct bin_tree node; 
void help()//help 
{ 
    printf("Options:\n"); 
    printf(" # -Put in any number to add it to the tree if not already there\n"); 
    printf(" s # -Put in s and a number to search the tree for the number\n"); 
    printf(" d # -Delete the number from the tree\n"); 
    printf(" p -Put in p to print the tree\n"); 
    printf(" ? -At any time you can press ? to display the help message\n"); 
    printf(" Q -If you decide the leave the realm of the tree then you can press Q to quit this program\n"); 

} 

int max(int a,int b)//max tree length 
{ 
    if(a>b) 
    return a; 
    else 
    return b; 
} 

int height(node* tree)//height 
{ 
    if(tree != NULL) 
    return(1 + max(height(tree->left),height(tree->right))); 
    else 
    return 0; 
} 

void insert(node ** tree, int val)//insert 
{ 
    node *temp = NULL; 
    if(!(*tree)) 
    { 
    temp = (node *)malloc(sizeof(node)); 
    temp->left = temp->right = NULL; 
    temp->data = val; 
    *tree = temp; 
    return; 
    } 

    if(val < (*tree)->data) 
    { 
    insert(&(*tree)->left, val); 
    } 
    else if(val > (*tree)->data) 
    { 
    insert(&(*tree)->right, val); 
    } 
} 
void print(node * tree)//print 
{ 
    if (tree) 
    { 
    print(tree->left); 
    printf("[%d] ",tree->data); 
    print(tree->right); 
    } 
} 
node* search(node ** tree, int val) 
{//search 
    if(!(*tree)) 
    { 
    return NULL; 
    } 
    if(val < (*tree)->data) 
    { 
    search(&((*tree)->left), val); 
    } 
    else if(val > (*tree)->data) 
    { 
    search(&((*tree)->right), val); 
    } 
    else if(val == (*tree)->data) 
    { 
    return *tree; 
    } 
} 

void main() 
{ 
    node *root; 
    node *tmp; 
    int no; 
    char ch, buff[500]; 

    root = NULL; 
    printf("Options:\n"); 
    printf(" # -Put in any intiger to add it to the tree if not already there\n"); 
    printf(" s # -Put in s and a number to search the tree for the number\n"); 
    printf(" d # -Delete the number from the tree\n"); 
    printf(" p -Print the tree\n"); 
    printf(" ? -At any time you can press ? to display the help message\n"); 
    printf(" Q -If you decide the leave the realm of the tree then you can press Q to quit this program\n"); 
    while(1){ 
    printf(">"); 
    fgets(buff,499,stdin); //grabs input from user 
    if(sscanf(buff,"%i",&no)==1){//decides if just a number 
     tmp = search(&root, no);//looks for number in the tree 
     if (tmp) 
     { 
     printf("Node already in tree!\n", tmp->data); 
     } 
     else 
     { 
     insert(&root, no);//if not in tree insert it 
     } 
    } 
    else if(sscanf(buff,"%c %i",&ch,&no)>=1)//checks if character 
    { 
     switch(ch) 
     { 
     case 's'://search for number 
     { 
      tmp = search(&root, no); 
      if (tmp) 
      { 
      printf("Node found=%d\n", tmp->data); 
      } 
      else 
      { 
      printf("Node not found in tree.\n"); 
      } 
      break; 
     } 
     case 'd': 
      tmp = search(&root, no); 
      if (tmp) 
      { 
      //Call delete function 
      printf("Node %i deleted", no); 
      break; 
      } 
      else 
      { 
      printf("Node not found in tree.\n"); 
      break; 
      } 
     case 'Q'://quit 
      exit(0); 
     case 'p'://print tree 
      printf("\n\n"); 
      print(root); 
      printf("\nHeight= %i\n\n",height(root)); 
      break; 
     case '?'://display help 
      help(); 
      break; 
     default://idiot >.> 
      printf("Invalid input!\n\n"); 
      help(); 
      break; 
     } 
    } 
    } 
    return; 
} 

Answer 1

Либо самый большой из узлов влево, либо самый маленький из узлов справа займет свое место!

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

15 
/\ 
    … 25 
    /\ 
    20 30 
     \ 
     23 

Предположим, вы хотите удалить узел 25:

• По свойствам двоичного дерева поиска, вы уже знаете, что все дети должны быть больше, чем родитель (15), поэтому использование одного из них вместо 25 действительно. ✓
• Если вы выберете самый большой узел из левого поддерева (23), он будет больше, чем любой из узлов слева, но он также будет меньше любого из узлов справа, поэтому он прекрасно подойдет в середине и может заменить место удаленного узла. ✓
• То же самое верно для наименьшего узла из правой поддерева (30). ✓

В случае, если выбранный узел является листом, все в порядке, и вы можете его удалить. В противном случае выполните операцию delete на выбранном вами узле.

Вы также можете взять look at the Wikipedia article of the binary search tree для реализации псевдокода.