二叉树的删除函数

Question

根据下面的代码，我可以使用什么来创建删除功能？我已经尝试了很多东西，但我一直在努力让它发挥作用。我的主要问题是试图删除一个有左右子节点的节点。对于没有子节点的节点，我可以将其父节点设置为指向 null 并释放该节点。对于一个子节点，只需将父节点设置为指向子节点并释放节点。对于在概念上和代码中都有两个子节点的节点，我将如何处理？

#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 它们来自您之前的位置），您的树仍然是一个有效的二叉搜索树。看看这个例子：

假设您要删除节点 25:

根据二叉搜索树的属性，您已经知道所有子节点都必须大于父节点 (15)，因此使用其中一个而不是 25 是有效的。 ✓
如果您从左子树 (23) 中选择最大的节点，它将大于左侧的任何节点，但也小于右侧的任何节点，因此它非常适合中间位置，可以代替已删除的节点。 ✓
右子树的最小节点（30）也是如此。 ✓

如果选择的节点是叶子，一切都很好，您可以删除它。否则在您选择的节点上执行 delete 操作。

你也可以拿一个look at the Wikipedia article of the binary search tree来实现一个伪代码。

二叉树的删除函数

Delete function for binary tree

c

tree

struct

function