c - 插入和删除后在二叉搜索树中查找高度

Question

下面的代码应该在一系列插入和删除之后输出二叉搜索树的最终高度。

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

struct Node{
    int data;
    struct Node *left;
    struct Node *right;
};

struct Node* Insert(int data, struct Node *root){
    if(root == NULL){
        root = malloc(sizeof(struct Node));
        root -> data = data;
        root -> left = root -> right = NULL;
    }
    else{
        if(data < root -> data) Insert(data, root -> left);
        else if(data > root -> data) Insert(data, root -> left);
    }
    return root;
}

struct Node* Find(int data, struct Node *root){
    if(root == NULL || root -> data == data) return root;
    if(data < root -> data) return Find(data, root -> left);
    if(data > root -> data) return Find(data, root -> right);
}

int FindMin(struct Node *root){
    int min, l_min, r_min;
    if(root == NULL) return INT_MIN;
    min = root -> data;
    l_min = FindMin(root -> left);
    r_min = FindMin(root -> right);
    if( l_min  < min ) min = l_min;
    if( r_min < min  ) min = r_min;
    return min;
}

struct Node* Delete(int data, struct Node *root){
    struct Node *temp;
    if(data < root -> data) root -> left = Delete(data, root -> left);
    else if(data > root -> data) root -> right = Delete(data, root -> right);
    else{
        if(root -> left != NULL && root -> right != NULL){
            root -> data = FindMin(root -> right);
            root -> right = Delete(root -> data, root -> right);
        }
        else{
            temp = root;
            if(root -> left == NULL) root = root -> right;
            if(root -> right == NULL) root = root -> left;
            free(temp);
        }
    }
    return root;
}

int Height(struct Node *root){
    int l_height, r_height;
    if(root == NULL) return 0;
    else{
        l_height = Height(root -> left);
        r_height = Height(root -> right);
        if(l_height > r_height) return l_height + 1;
        else return r_height + 1;
    }
}

int main(){
    struct Node *root = NULL, *temp = NULL;
    int n, a, b;
    scanf("%i",&n);
    while(n--){
        scanf("%i %i",&a,&b);
        if(a == 1){
            temp = Find(b,root);
            if(temp != NULL) continue;
            root = Insert(b,root);
        }
        else if(a == 2){
            temp = Find(b,root);
            if(temp == NULL) continue;
            root = Delete(b,root);
        }
        else{
            continue;
        }
    }
    printf("Height: %i\n",Height(root));
    return 0;
}

第一个输入是数字 n，它是后面的行数。

所有后续行都有整数“a b”。 a == 1表示插入，b == 2表示删除，b为要插入或删除的值。 “查找”功能测试 BST 上是否存在某个值，这样我就不会插入已经存在的内容或尝试删除 BST 上不存在的内容。

因此，例如，这是一个有效的测试用例，它应该返回 5:

10
1 5
1 8
1 3
1 4
1 2
1 1
1 0
1 7
1 9
2 3

但是，我的代码没有这样做，只是为每个可能的测试用例返回“1”。我不知道为什么会这样。有什么想法吗？

解决方案:感谢@coderredoc，现在这里是这段代码的完整功能版本。

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


struct Node{
    int data;
    struct Node *left;
    struct Node *right;
};

struct Node* Insert(int data, struct Node *root){
    if(root == NULL){
        root = malloc(sizeof(struct Node));
        root -> data = data;
        root -> left = root -> right = NULL;
    }
    else{
        if(data < root -> data) root -> left = Insert(data, root -> left);
        else if(data > root -> data) root -> right = Insert(data, root -> right);
    }
    return root;
}

struct Node* Find(int data, struct Node *root){
    if(root == NULL || root -> data == data) return root;
    if(data < root -> data) return Find(data, root -> left);
    if(data >= root -> data) return Find(data, root -> right);
    return NULL;
}

struct Node* FindMin(struct Node *root){
    struct Node *temp = root;
    while( temp -> left != NULL) temp = temp -> left;
    return temp;
}

struct Node* Delete(int data, struct Node *root){
    struct Node *temp;
    if(root == NULL) return NULL;
    if(data < root -> data) root -> left = Delete(data, root -> left);
    else if(data > root -> data) root -> right = Delete(data, root -> right);
    else{
        if(root -> left == NULL){
            temp = root -> right;
            free(root);
            return temp;
        }
        else if(root -> right == NULL){
            temp = root -> left;
            free(root);
            return temp;
        }
        else{
            temp = FindMin(root -> right);
            root -> data = temp -> data;
            root -> right = Delete( temp -> data, root -> right);
        }
    }
    return root;
}

int Height(struct Node *root){
    int l_height, r_height;
    if(root == NULL) return 0;
    else{
        l_height = Height(root -> left);
        r_height = Height(root -> right);
        if(l_height > r_height) return l_height + 1;
        else return r_height + 1;
    }
}

int main(){
    struct Node *root = NULL, *temp = NULL;
    int n, a, b;
    scanf("%i",&n);
    while(n--){
        scanf("%i %i",&a,&b);
        if(a == 1){
            temp = Find(b,root);
            if(temp != NULL) continue;
            root = Insert(b,root);
        }
        else if(a == 2){
            temp = Find(b,root);
            if(temp == NULL) continue;
            root = Delete(b,root);
        }
        else{
            continue;
        }
    }
    printf("%i\n",Height(root));
    return 0;
}

Answer 1

是的，那是因为您从未链接任何添加的节点。

if(data < root -> data) root->left= Insert(data, root -> left);
else if(data >= root -> data) root->right = Insert(data, root -> right);

另请注意，在 Insert() 中的两种情况下，您都使用了 root->left。应该如上所示。

同样在Find()函数中

struct Node* Find(int data, struct Node *root){
    if(root == NULL || root -> data == data) return root;
    if(data < root -> data) return Find(data, root -> left);
    if(data >= root -> data) return Find(data, root -> right);
    //      ^   You need to make it >=
    return NULL; //<----Add it
}

您遇到的段错误也是因为错误的删除逻辑。正确的应该是

struct Node* Delete(int data, struct Node *root){
    struct Node *temp;
    if( root == NULL) return NULL;
    if(data < root -> data) root -> left = Delete(data, root -> left);
    else if(data > root -> data) root -> right = Delete(data, root -> right);
    else{
        if (root->left == NULL)
        {
            struct Node *temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            struct Node *temp = root->left;
            free(root);
            return temp;
        }
        else
        {
            struct Node *temp = FindMin(root->right);
            root->data = temp->data;
            root->right = Delete( temp->data, root->right);
        }
    }
    return root;
}

此外，您的 findMin 版本仅返回所有节点值的最小值。但这不是 Delete() 函数所需要的。这就是这个功能的原因。

struct Node*FindMin(struct Node* node)
{
    struct Node *current = node;
    while (current->left != NULL)
            current = current->left;
    return current;
}