为什么我的二叉树搜索功能不返回根地址?

问题描述 投票:0回答:1

对不起,我问的太多了,所以这与我以前的问题几乎一样。我有一个带有删除功能的平衡二叉树代码,所以问题出在我的searchdelete()函数中。我不知道为什么它不能返回根。因此,例如

5, 4, 3, 2, 1

然后我在菜单上输入“要删除的数据:1”它去了searchdelete();功能,然后成功显示已找到数据,found = 1但是在那之后,它将不会返回根地址。我不知道为什么它不会回来。因此在Delete();中功能,它不会打印printf("root after = %d", root->data)

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

struct node{

    int data, balance;

    struct node *left, *right;

};

int insert(struct node **root, struct node **curr, int data){

    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    newNode -> data = data;
    newNode -> left = NULL;
    newNode -> right = NULL;
    newNode -> balance = 0;

    if((*root) == NULL){
        (*root) = (*curr) = newNode;
        (*root) -> left = NULL;
        (*root) -> right = NULL;
        return 0;
    } else {
        if((*curr)->left == NULL && (*curr)->balance == 0){
            (*curr) -> balance = (*curr) -> balance - 1;
            (*curr) -> left = newNode;
            return 0;
        } else if ((*curr)->right == NULL && (*curr)->balance == -1){
            (*curr) -> balance = (*curr) -> balance + 1;
            (*curr) -> right = newNode;
            return 0;
        } else if ((*curr)->balance == 0 && (*curr)->left->balance == 0){
            (*curr) -> balance = (*curr) -> balance - 1;
            (*curr) = (*curr)->left;
            return insert(root,curr,data);
        } else if ((*curr)->balance < 0 && (*curr)->left->balance < 0){
            (*curr) -> balance = (*curr) -> balance - 1;
            (*curr) = (*curr) -> left;
            return insert(root,curr,data);
        } else if ((*curr)->balance < 0 && (*curr)->left->balance == 0){
            (*curr) -> balance = (*curr) -> balance + 1;
            (*curr) = (*curr)->right;
            return insert(root, curr, data);
        }
    }
}

void preorder(struct node *root){

    if(root == NULL) return;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);

}

void postorder(struct node *root){

    if(root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);

}

void inorder(struct node *root){

    if(root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);

}


void search(struct node *root, int *key, int *found){

    if(root == NULL) return;
    search(root->left, key, found);
    if(root->data == *key){
        *found = 1;
        return ;
    }
    search(root->right, key, found);

}

struct node *findMin(struct node *root){

    while(root->left != NULL) root = root->left;
    return root;
}

struct node *searchdelete(struct node *root, int data){

    if(root == NULL) return root;                                    //This is the searchdelete
    searchdelete(root->left, data);
    if(root->data == data){
        printf("found = %d", root->data);
        return root;
    }
    searchdelete(root->right, data);

}

struct node *Delete(struct node *root, int data){

    printf("root before = %d\n", root->data);
    if(root == NULL) return root;
    else if(data != root->data) {
        root = searchdelete(root, data);
        printf("root after = %d\n", root->data);           //this is where it won't print
        system("pause");
    }
    else{
        //Case 1: no child / leaf node
        if(root->left == NULL && root->right == NULL){
            printf("NULL\n");
            free(root);
            root = NULL;
        }
        //Case 2: one child, left or right
        else if(root->left == NULL){
            printf("left null\n");
            struct node *temp = root;
            root = root->right;
            free(temp);
        } else if (root->right == NULL){
            printf("right null\n");
            struct node *temp = root;
            root = root->left;
            free(temp);
        }
        //Case 3: two children
        else{
            printf("two children \n");
            if(root->right->data > root->data){
                struct node *temp = root;
                root = root->right;
                free(temp);
            } else {
                struct node *temp = root;
                root = root->left;
                free(temp);
            }
        }
    }
    system("pause");
    return root;
}


int main(){

    struct node *root, *curr;
    int choice, data, key, found, delKey;
    root = curr = NULL;

    while(1){
        found = 0;
        printf("Balanced Binary Tree Menu\n");
        printf("1. Insert Data\n");
        printf("2. View on pre order\n");
        printf("3. View on post order\n");
        printf("4. View on in order\n");
        printf("5. Search\n");
        printf("6. Delete\n");
        printf("7. Exit\n");
        printf("Pilihan: ");scanf("%d", &choice);fflush(stdin);

        if(choice == 1){
            printf("Enter data : "); scanf("%d", &data);
            curr = root;
            insert(&root, &curr, data);
        } else if (choice == 2){
            preorder(root);
            system("pause");
        } else if (choice == 3){
            postorder(root);
            system("pause");
        } else if (choice == 4){
            inorder(root);
            system("pause");
        } else if (choice == 5){
            printf("Search: "); scanf("%d", &key);
            search(root, &key, &found);
            if(found == 1){
                printf("Data found !\n");
            } else {
                printf("Data not found !\n");
            }
            system("pause");
        } else if (choice == 6){
            printf("Enter data to be deleted: "); scanf("%d", &delKey);
            Delete(root, delKey);
        } else if (choice == 7){
            return 1;
        }
        system("cls");
    }

    return 0;
}


c struct binary-tree
1个回答
0
投票

如果您想search从定义中返回包含*key的单元格:

struct node * search(struct node *root, int *key, int *found){
    if(root == NULL)
      return NULL;
    if(root->data == *key){
        *found = 1;
        return root;
    }
    if ((root = search(root->left, key, found)) != NULL)
      return root;
    return search(root->right, key, found);
}

为什么keyint*而不是像searchdelete那样的int?请注意,如果返回值为NULL(表示未找到),则具有found是没有用的,否则意味着找到。因此search是没有用的,您只需将searchdelete重命名为search(或find

与[[搜索删除相同::

struct node * searchdelete(struct node *root, int data){ if(root == NULL) return root; if(root->data == data){ printf("found = %d", root->data); /* debug, to be removed */ return root; } if ((root = searchdelete(root->left, data)) != NULL) return root; return searchdelete(root->right, data); }
在两种搜索中都没有使用可以对树进行排序的事实,我的意思是左边的数据较少,右边的数据较大,这提高了性能

如果元素随机放置在二叉树中根本没有兴趣

© www.soinside.com 2019 - 2024. All rights reserved.