二叉樹的刪除功能

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作爲僞代碼實現。