二叉排序树删除不成功

Question

#include<stdio.h>
#include<stdlib.h>
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
}Node;
typedef struct  {
    Node* root;
}Tree;
void addnode(Tree* tree, int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    if (tree->root == NULL) {
        tree->root = node;
    }
    else {
        Node* temp = (Node*)malloc(sizeof(Node));//存储当前根节点内容
        temp = tree->root;
        while (temp != NULL) {
            if (temp->data > data) {
                if (temp->left == NULL) {
                    temp->left = node;
                    return;
                }
                else {
                    temp = temp->left;

                }
            }
            else {
                if (temp->data < data) {
                    if (temp->right == NULL) {
                        temp->right = node;
                        return;
                    }
                    else {
                        temp = temp->right;
                    }
                }
            }
        }
    }
}

Node* findmin(Node* node) {
    if (node == NULL)
        return NULL;
    while (node->left != NULL)
        node = node->left;
    return node;
}
bool denode(Node* node, int data) {
    Node* temp = (Node*)malloc(sizeof(Node));
    temp = node;
    while (temp->data != data) {
        if (temp->data > data) {
            temp = temp->left;
        }
        else {
            temp = temp->right;
        }
    }
if (temp->left == NULL && temp->right ==NULL) {
        temp = NULL;
    }
    else if (temp->left != NULL && temp->right == NULL) {
        
        temp = temp->left;

    }
    else if (temp->right != NULL && temp->left == NULL) {
        temp = temp->right;
    }
    else {
        Node* pre = findmin(temp->right);
        temp->data = pre->data;
        free(pre);
    }
    return true;
}
void firorder(Node* node) {
    if (node != NULL) {
        printf("%d\n", node->data);
        firorder(node->left);
        firorder(node->right);
    }
}
int main() {

    int arry[7] = { 6,3,8,2,5,1,7 };
    Tree tree;
    tree.root = NULL;
    for (int i = 0; i < 7; i++) {
        addnode(&tree, arry[i]);
    }
    firorder(tree.root);
    printf("--------\n");
    addnode(&tree, 4);
    firorder(tree.root);
    printf("--------\n");
    denode(tree.root, 7);
    firorder(tree.root);
}

删除没有双亲节点或者只有一个双亲节点的删不掉，删除有两个双亲节点的会报错

532158F
6321548
542
15
572662307
``

Answer 1

if (temp->left == NULL && temp->right ==NULL)
{
temp = NULL;
}
else if (temp->left != NULL && temp->right == NULL)
{
temp = temp->left;
}
else if (temp->right != NULL && temp->left == NULL)
{
temp = temp->right;
}
这个代码是没有任何效果的。你应该修改temp->left和 temp->right的值。修改temp没有用，这个只是临时变量
修改如下：增加了freenode函数删除节点，修改了denode的删除节点部分。删除节点得用递归

#include<stdio.h>
#include<stdlib.h>
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
}Node;
typedef struct  {
    Node* root;
}Tree;
void addnode(Tree* tree, int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    if (tree->root == NULL) {
        tree->root = node;
    }
    else {
        Node* temp = (Node*)malloc(sizeof(Node));//存储当前根节点内容
        temp = tree->root;
        while (temp != NULL) {
            if (temp->data > data) {
                if (temp->left == NULL) {
                    temp->left = node;
                    return;
                }
                else {
                    temp = temp->left;
                }
            }
            else {
                if (temp->data < data) {
                    if (temp->right == NULL) {
                        temp->right = node;
                        return;
                    }
                    else {
                        temp = temp->right;
                    }
                }
            }
        }
    }
}
void freeNode(Node *node,int lr)
{
    if(lr == 0 && node->left != NULL)
    {
        freeNode(node->left,0);
        freeNode(node->left,1);
        free(node->left);
    }
    if(lr == 1 && node->right != NULL)
    {
        freeNode(node->right,0);
        freeNode(node->right,1);
        free(node->right);
    }    
}
Node* findmin(Node* node) {
    if (node == NULL)
        return NULL;
    while (node->left != NULL)
        node = node->left;
    return node;
}
bool denode(Node* node, int data) 
{
    Node *parent = NULL;
    int lr = 0;
    Node* temp = node;
    while (temp->data != data) 
    {
        parent = temp;
        if (temp->data > data) 
        {
            temp = temp->left;
            lr = 0;
        }
        else 
        {
            temp = temp->right;
            lr = 1;
        }

    }
    freeNode(parent,lr);
    if(lr == 0)
        parent->left = NULL;
    else if(lr == 1)
        parent->right = NULL;

    return true;
}
void firorder(Node* node) {
    if (node != NULL) {
        printf("%d\n", node->data);
        firorder(node->left);
        firorder(node->right);
    }
}

int main() {
    int arry[7] = { 6,3,8,2,5,1,7 };
    Tree tree;
    tree.root = NULL;
    for (int i = 0; i < 7; i++) {
        addnode(&tree, arry[i]);
    }
    firorder(tree.root);
    printf("--------\n");
    addnode(&tree, 4);
    firorder(tree.root);
    printf("--------\n");
    denode(tree.root, 3);
    firorder(tree.root);
    return 0;
}