C中二叉树的删除函数

Question

我正在为二叉树编写基本函数，一切似乎都可以编译运行，但是当我尝试使用我的删除函数时，它什么也没做。

执行后我得到了相同的数字序列，所以我想弄清楚删除函数有什么问题，它在逻辑上是否正确？

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

typedef struct treeNode
{
   int data;
   struct treeNode *left;
   struct treeNode *right;
}treeNode;

treeNode *Insert(treeNode *node, int data)
{
    if(node == NULL)
    {
    treeNode *temp;
    temp = malloc(sizeof(treeNode));
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
    }

    if(data > (node->data))
    {
    node->right = Insert(node->right, data);
    }

    else if(data < (node->data))
    {
    node->left = Insert(node->left, data);
    }
return node;
}

treeNode *Delete(treeNode *node, int data)
{
   if(node == NULL)
   {
    printf("element not found\n");
   }

   else if(data < node->data)
   {
    node->left = Delete(node->left, data);
   }

  else if(data > node->data)
  {
    node->right = Delete(node->right, data);
  }
return node;
}

treeNode *Find(treeNode *node, int data)
{
   if(node == NULL)
   {
    return NULL;
   }

   if(data > node->data)
   {
    return Find(node->right, data);
   }

   else if(data < node->data)
   {
    return Find(node->left, data);
   }

   else
   {
    return node;
   }
}

void Print(treeNode *node)
{
   if(node == NULL)
   {
    return;
   }
   Print(node->left);
   printf("%d", node->data);
   Print(node->right);
}

int main()
{
  treeNode *root = NULL;

  root = Insert(root, 5);
  root = Insert(root, 8);
  root = Insert(root, 6);
  root = Insert(root, 4);
  root = Insert(root, 3);
  root = Insert(root, 9);
  root = Insert(root, 10);
  root = Insert(root, 19);

  Print(root);
  printf("\n");

  root = Delete(root, 5);
  root = Delete(root, 8);

  Print(root);
  printf("\n");

  treeNode *temp;

  temp = Find(root, 8);
   if(temp == NULL)
   {
    printf("Element 8 not found\n");
   }
   else
   {
    printf("Element 8 found\n");
   }

  temp = Find(root, 5);
  if(temp == NULL)
  {
    printf("element 5 not found\n");
  }
  else
  {
    printf("element 5 found\n");
  }
}

Answer 1

基本上我只是用自己替换节点，但这可以通过用右子树中的最小元素或左子树中的最大元素替换删除的节点来解决。

有效的函数：

treeNode * Delete(treeNode *node, int data)
{
    treeNode *temp;
    if(node==NULL)
      {
        printf("Element Not Found");
      }
    else if(data < node->data)
      {
        node->left = Delete(node->left, data);
      }
    else if(data > node->data)
      {
        node->right = Delete(node->right, data);
      }
    else
      {
    /* Now We can delete this node and replace with either minimum element 
               in the right sub tree or maximum element in the left subtree*/
        if(node->right && node->left)
          {
        /* Here we will replace with minimum element in the right sub tree */
            temp = FindMin(node->right);
            node -> data = temp->data; 
    /* As we replaced it with some other node, we have to delete that node */
            node -> right = Delete(node->right,temp->data);
          }
        else
           {
        /* If there is only one or zero children then we can directly 
                       remove it from the tree and connect its parent to its child */
            temp = node;
             if(node->left == NULL)
                    node = node->right;
             else if(node->right == NULL)
                    node = node->left;
            free(temp); /* temp is longer required */ 
            }
    }
    return node;

}

C中二叉树的删除函数

Delete function in Binary Tree in C

c

tree

binary-tree