了解 C 语言中二叉树实现的功能

Question

我在使用删除函数从二叉树中删除节点时遇到问题。这是我的第一个树程序，我发现书籍和互联网页面的删除功能非常令人困惑。我为此编写了一些代码，但它不会删除节点。我将感谢您的帮助。

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

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

node *root=NULL;

node *getnode();
//void insert(node **tree, int val);
void insert(node *tree, int val, node *parent);
void inorder(node *tree);
void preorder(node *tree);
void postorder(node *tree);
void delete(node *tree, int val);
node *largestnode( node *tree);

int main (){
    int choice, val;
    while(1){
        printf("\n1. Insert\n2. Inorder\n3. Preorder\n4. Postorder\n5. Delete\n6. Exit\nEnter your choice: ");
        scanf("%d", &choice);
        switch(choice){
            case 1:
                printf("Enter the value to be inserted: ");
                scanf("%d", &val);
                if(root==NULL){
                    root=getnode();
                    root->data=val;
                }
                else{
                    insert(root, val, root);
                }
                break;
            case 2:
                inorder(root);
                break;
            case 3:
                preorder(root);
                break;
            case 4:
                postorder(root);
                break;
            case 5:
                printf("Enter the value to be deleted: ");
                scanf("%d", &val);
                delete(root, val);
                break;
            case 6:
                exit(0);
            default:
                printf("Invalid choice\n");
        }
    }
    return 0;
}

node *getnode(){
    node *newnode = (node*)malloc(sizeof(node));
    newnode->left=newnode->right=NULL;
    return newnode;
}

void insert(node *tree, int val, node *parent){
    if(tree==NULL){
        tree=getnode();
        (tree)->data=val;
        if(parent->data>val){
            parent->left=tree;
        }
        else{
            parent->right=tree;
        }
    }
    else if (val<(tree)->data){
        parent=tree;
        insert(((tree)->left), val, parent);
    }
    else{
        parent=tree;
        insert(((tree)->right), val, parent);
    }
    
}

/*void insert(node **tree, int val){
    if(*tree==NULL){
        *tree=getnode();
        (*tree)->data=val;
    }
    else if (val<(*tree)->data){
        insert(&((*tree)->left), val);
    }
    else{
        insert(&((*tree)->right), val);
    }
}*/

void inorder(node *tree){
    if(tree != NULL){
        inorder(tree->left);
        printf("%d\t", tree->data);
        inorder(tree->right);
    }
}

void preorder(node *tree){
    if(tree != NULL){
        printf("%d\t", tree->data);
        preorder(tree->left);
        preorder(tree->right);
    }
}

void postorder(node *tree){
    if(tree != NULL){
        postorder(tree->left);
        postorder(tree->right);
        printf("%d\t", tree->data);
    }
}
    
void delete(node *tree, int val){
    node *temp;
    if(tree==NULL){
        printf("Element not found\n");
    }
    else if(val<tree->data){
        delete(tree->left, val);
    }
    else if(val>tree->data){
        delete(tree->right, val);
    }
    else{
        if(tree->left && tree->right){
            temp=largestnode(tree->left);
            tree->data=temp->data;
            delete(tree->left, temp->data);
        }
        else{
            temp=tree;
            if(tree->left==NULL){
                tree=tree->right;
            }
            else if(tree->right==NULL){
                tree=tree->left;
            }
            free(temp);
        }
    }
}

node *largestnode( node *tree){
    if(tree==NULL) return NULL;
    else if(tree->right==NULL) return tree;
    else return largestnode(tree->right);
}

忽略我写的注释作为插入功能的替代方法。

我尝试编写一个函数，通过查找节点、用其后继替换该节点、然后释放内存来从二叉树中删除该节点。我期望该函数从树中删除节点并更新树结构。但并没有按计划进行。我认为我的逻辑或指针操作有问题。

Answer 1

如果删除根节点，那么调用者需要知道新的根节点是什么。您可以返回它（见下文），也可以传入

node **tree

来更新它。唯一棘手的情况是根是否同时有左子节点和右子节点：

node *delete(node *tree, int data){
    if(!tree){
        printf("Element not found\n");
        return tree;
    }
    if(tree->data > data) {
        tree->left = delete(tree->left, data);
        return tree;
    }
    if(tree->data < data){
        tree->right = delete(tree->right, data);
        return tree;
    }
    if(!tree->left) {
        node *temp=tree->right;
        free(tree);
        return temp;
    }
    if(!tree->right) {
        node *temp=tree->left;
        free(tree);
        return temp;
    }
    struct node *next_parent = tree;
    struct node *next = tree->right;
    for(; next->left; next = next->left, next_parent = next);
    if (next_parent != tree)
        next_parent->left = next->right;
    else
        next_parent->right = next->right;
    tree->data = next->data;
    free(next);
    return tree;
}

// ...

            case 5:
                printf("Enter the value to be deleted: ");
                scanf("%d", &val);
                root = delete(root, val);
                break;

和示例运行（我调整了程序，只在第一次显示菜单，只是更短）：

1. Insert
2. Inorder
3. Preorder
4. Postorder
5. Delete
6. Exit
Enter your choice: 1
Enter the value to be inserted: 2
: 1
Enter the value to be inserted: 1
: 1
Enter the value to be inserted: 3
: 5
Enter the value to be deleted: 2
: 2
1       3       :