c - C中的二叉搜索树-删除具有左右子树的节点时出错

Question

我的二叉搜索树程序即将完成。但是，我坚持删除:删除具有左右子树的节点。最大的左值在左子树中提升。它有时会起作用，但并不总是按应有的方式起作用。即，如果您将值 23、14、31、7、9 输入到树中并删除 23，则得出的值是 14 14 7 9。请帮忙!

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


typedef struct node { 
    int key; 
    struct node* left;
    struct node* right;
}node;

struct node* root= NULL;
int count=0;
void preOrder(node* temp){

    if (temp!=NULL){
        printf("%d ",temp->key);
        preOrder(temp->left);
        preOrder(temp->right);
    }
}
//for printing
void inOrder(node* temp){

        if (temp!=NULL){
           inOrder(temp->left);
           printf("%d ",temp->key);
           inOrder(temp->right);
        }

}
void printPrompt(void){
    int choice=-1;

    do{
        printf("   Enter <1> Inorder <2> Preorder <3> Return to Menu: ");
        scanf("%d", &choice);

        if(choice!=1 && choice!=2 && choice!=3)  printf("   Error: invalid input! \n\n");
        if(choice==1){
           if(root==NULL) printf("\tError: is empty tree\n");
              else {
                   printf("\tInorder:\t ");
                   inOrder(root);
                   printf("\n\n");
              }
        }
        else if (choice==2){
           struct node* temp=root;
           if(root==NULL) printf("\tError: is empty tree\n");
              else {
                   printf("\tPreorder:\t ");
                   preOrder(root);
                   printf("\n\n");
              }
        }


    }while (choice!=3);
    printf("   <Exit print method>\n\n");

}
//printing complete

//both are similar code- one searches and another finds the node
int contains(node* current, int value){
    if(current==NULL) return 0;
    if (value==current->key) {
        return 1;
    }
    else if(value < current->key) return contains(current->left, value);
    else return contains(current->right, value);
}
node* findParent(node* current, int value){
    if (value == current->key) return NULL; //if only one node in BST, then no parent node
    if (value < current->key) {
        if (current->left == NULL) return NULL; //if value not found, return null
        else if (current->left->key == value) return current;
        else return findParent (current->left, value);
    }
    else {
        if (current->right == NULL) return NULL;
        else if (current->right->key== value) return current;
        else return findParent (current->right, value);
    }
}

node* findNode(node* current, int value){
    if (current == NULL) return NULL;
    if (current->key == value) {
        return current;
    }
    else if (value < current->key)  return findNode (current->left, value);
    else return findNode (current->right, value);
}
//

void del(value){
    struct node* nodeToRemove= findNode(root, value);
    if (nodeToRemove == NULL) printf("\tError: node not found in tree\n");
    else {
       struct node* parent = findParent(root, value);
       if (count == 1 ) {
            root= NULL; 
            printf("\tRemoving the only node in BST\n");
       }
       else if (nodeToRemove->left == NULL && nodeToRemove->right == NULL){
            printf("\tRemoving leaf node in BST\n");
            if (nodeToRemove->key < parent->key) parent->left = NULL;
            else parent->right = NULL;
       }
       else if (nodeToRemove->left== NULL && nodeToRemove->right != NULL){
            printf("\tRemoving node with right subtree but no left subtree\n");
            if (nodeToRemove->key < parent->key) {
                parent->left = nodeToRemove->right;
            }
            else parent->right = nodeToRemove->right;
       }
       else if (nodeToRemove->left!= NULL && nodeToRemove->right == NULL){
            printf("\tRemoving node with left subtree but no right subtree\n");
            if (nodeToRemove->key < parent->key) {
                parent->left = nodeToRemove->left;
            }
            else parent->right = nodeToRemove->left;
       }
       else{
            printf("\tRemoving node with both left subtree and right subtree\n");
            struct node* nodeLargestLeft = nodeToRemove -> left;
                while (nodeLargestLeft -> right != NULL) nodeLargestLeft= nodeLargestLeft->right;
            findParent(root, nodeLargestLeft->key)->right=NULL;
            nodeToRemove->key=nodeLargestLeft->key;
       }   
   }

            printf("\tResult: ");
            preOrder(root);
            printf("\n");  
            count= count-1;
}

void deletePrompt(void){
    int value=-1;
    do{
        printf("   Delete key or press -1 to return to menu:  ");
        scanf("%d", &value);
        if(value>0){
           if(root==NULL) printf("\tError: is empty tree\n");
             else del(value);

        }
         else if (value<=0) printf("\tError: key not positive\n");
    }while (value!=-1); 
    printf("   <Exit delete method>\n\n");
}

void searchPrompt(void){
    int value=-1;
    do{
        printf("   Search key or press -1 to return to menu: ");
        scanf("%d", &value);
        if(value>0){
            if (root==NULL) printf("\tError: tree is empty\n"); 
            else {
                if(contains(root, value)) printf("\tKey %d is found\n",value);
                else printf("\tKey %d is not found\n",value);
            }
        }
        else if (value<=0) printf("\tError: key not positive\n");
    }while (value!=-1);
    printf("   <Exit search method>\n\n");
}
//for search




//for insertion
void insertNode(node* current, int value){        
        if(value< current->key){
            if (current->left == NULL) {
                current->left=(node*) malloc(sizeof(node));
                current->left->key = value;
                current->left->left = NULL;
                current->left->right = NULL;
                printf("\tSuccess! Value inserted: %d\n", current->left->key);

            }
            else {
                insertNode(current->left, value);
            }
        }
        else {
            if (current->right == NULL) {
                current->right=(node*) malloc(sizeof(node));
                current->right->key = value;
                current->right->left = NULL;
                current->right->right = NULL;
                printf("\tSuccess! Value inserted: %d\n", current->right->key);
            }
            else {
                insertNode(current->right, value);
            }
        }
}//end insert

void insert(int value){

    if(root==NULL){  //empty tree
        root =(node*) malloc(sizeof(node));

        root->key= value;
        printf("\tPrint root here: %d\n", value);
        root->left= NULL;
        root->right=NULL;
        printf("\tSuccess! Value inserted: %d\n", root->key);
    }
    else {
        insertNode(root, value);
    }        
        printf("\tResult: ");
        preOrder(root);
        printf("\n");
}

void insertPrompt(void){
    int value=-1;
    do{
        printf("   Insert value or press -1 to return to menu:  ");
        scanf("%d", &value);
        if(value>0){
            insert(value);
            count= count+1;
            printf("\tCount: %d\n", count);
        }
        else if (value<=0)printf("\tError: key not positive\n");
    }while (value!=-1);
    printf("   <Exit insert method>\n\n");

}

int menuPrompt(void){
    int choice=-1;
    do{
        printf("Enter <1> Search <2> Insert <3> Delete <4> Print Tree <5> Quit: ");
        scanf("%d", &choice);
        if(choice>5 || choice<1) printf("Error: invalid input! \n\n");
    }  while(choice>5 || choice<1);
    return choice;

}


int main(int argc, char *argv[]){
   int choice=-1;
   int value=-1;


    while(choice!=5){

   choice=menuPrompt();

   switch(choice){
    case 1:
         searchPrompt();
         break;
    case 2:
         insertPrompt();
         break;
    case 3:
         deletePrompt();
         break;
    case 4:
         printPrompt();
         break;    
    case 5:
         printf("<Exit program> \n");
         break;
   }//end switch

}

  system("PAUSE");  
  return 0;
}

Answer 1

您对具有两个子树的节点的删除算法略有错误。你正确地做的是:

求左子树的最大值(或右子树的最小值):

struct node* nodeLargestLeft = nodeToRemove -> left;
while (nodeLargestLeft -> right != NULL)
    nodeLargestLeft= nodeLargestLeft->right;

• 将要移除的节点的值替换为上面找到的节点的值

  nodeToRemove->key=nodeLargestLeft->key;

您尝试从示例树中删除 23

      23
     /  \
   14    31
  /
 7
  \ 
   9

它在左子树中有 14 个最大值，现在看起来像这样:

      14
     /  \
   14    31
  /
 7
  \ 
   9

但是现在，您不能只删除最大节点(即您的根节点)的父节点的右子树。在您提到的示例中，这将是整个二叉树的右子树!

findParent(root, nodeLargestLeft->key)->right=NULL; // wrong

相反，您必须对重复节点(第二层中的节点 14)执行定期删除程序。因为它是左子树中具有最大值的节点，所以它不能有右子树。所以只有两种情况:要么左子树也为空，这种情况下该节点可以被丢弃，要么它被填充，这种情况下左子树的根节点替换该节点。

在你的例子中，第二种情况发生了，你的树应该看起来像这样:

      14
     /  \
    7    31
     \ 
      9

只要进行最少的侵入性更改，此过程就可以工作:

printf("\tRemoving node with both left subtree and right subtree\n");
struct node* nodeLargestLeft = nodeToRemove->left;
parent = findParent(root, nodeLargestLeft->key);
while (nodeLargestLeft -> right != NULL) {
    parent = nodeLargestLeft;
    nodeLargestLeft= nodeLargestLeft->right;
}
nodeToRemove->key=nodeLargestLeft->key;
parent->left = nodeLargestLeft->left;

你的代码还有其他几个问题，例如

• 当删除只有左子树或右子树的根节点时，parent 是一个NULL 指针，导致 parent->key 出现段错误
• 重复处理不一致
• 许多代码路径可以合并为一个，消除冗余并增强代码可读性
• 对 findParent 的调用看起来很难看，最好在遍历树或为每个节点维护父指针时跟踪父节点。