c - 二叉树 - 删除段错误。

Question

我基本上只需要另一双眼睛；我知道我遗漏了一些小东西，但我现在找不到。

这是我的完整二叉树程序。

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

//-------------------------Structure definition----------------------------------------------------------------------------------
struct tree {
    int data;
    struct tree *left;
    struct tree *right;
};


//-------------------------Function definitions--------------------------------------------------------------------------------
int traverse(struct tree *);    //Traverse to print the data.
struct tree * insert(struct tree *, int num);   //insert data.
int search(struct tree *, int num);     //Find a number, return found/not found status.
struct tree * delete(struct tree *, int num);       //Delete a number.
int maxdepth(struct tree *);    //Find depth of tree.
int bal(struct tree *);     //Indicates whether or not the tree is balanced. 
void help();        //Simple help routine. 


//-------------------------Help function to display commands. ----------------------------------------------------------
void help()
{
    printf("\n Q to quit program. \n");
    printf(" # to insert # into the list. \n");
    printf(" s # to search for # in the list. \n");
    printf(" d # to delete # from list. \n");
    printf(" p to print the entire list. \n");
    printf(" ? to view this message again. \n\n");
}



//-------------------------Insert function to sort and insert user input. ----------------------------------------------
struct tree * insert(struct tree *root, int num)
{

    if(root==NULL)
    {
        root=malloc(sizeof(struct tree));
        root->data = num;
        root->left = root->right=NULL;
        return(root);
    }
    if(num > root->data)
    {
        root->right=insert(root->right, num);
        return(root);
    }
    if(num < root->data)
    {
        root->left=insert(root->left, num);
        return(root);
    }
/*  if(num==root->data)
    {
        return (root);
    }
*/
}


//-------------------------Search function. Just returns a 1/0 for yes/no. ------------------------------------------
int search(struct tree *root, int num)
{
    if(root==NULL)return(0);
    if(num==root->data)return(1);
    if(1==search(root->left, num) || 1==search(root->right, num))
    {
        return(1);
    }
    else
    {
        return(0);
    }
}

//-------------------------Delete function. Deletes target, replaces with following num. ----------------------------
struct tree * delete(struct tree *root, int num)
{
    struct tree *parent;
    struct tree *successor; //Placeholders.

    //If root isn't there...
    if(root=NULL)
    {
        printf("Number not found. \n\n");
        return NULL;
    }

    //If target is greater than root->data, go right.
    if(num>root->data)
    {
        root->right=delete(root->right, num);
        return (root);
    }

    //If target is less than root->data, go left. 
    if(num<root->data)
    {
        root->left=delete(root->left, num);
        return(root);
    }
    //If target equals root->data, put on headphones. Push play.    
    if(num==root->data)    //DELETE SEGFAULTS HERE (FROM GDB)
    {
        if((root->left==NULL) && (root->right==NULL))   //If no children....
        {
            free(root);
            return NULL;
        }

        if((root->left==NULL) && (root->right!=NULL))   //If right child...
        {
            successor=root->right;
            free(root);
            return(successor);
        }

        if((root->left!=NULL) && (root->right==NULL))   //If left child...
        {
            successor=root->left;
            free(root);
            return(successor);
        }

        if((root->left!=NULL) && (root->right!=NULL))   //If root has two children
        {
            parent=root;    //Remember root node
            successor=root->right;  //Find his replacement
            if(successor->left==NULL)   //If no left child, replace with successor and free root.
            {
                successor->left=root->left;
                free(root);
                return(successor);
            }
            else
            {
                while(successor->left!=NULL)    //If there is a left child, follow to the end.
                {
                    successor=successor->left;
                }
            parent->data=successor->data;   //Replace root with successor, free root.
            free(parent);
            return(successor);
            }
        }
    }
}   


/*-------------------------Balance function. Indicates whether or not the tree is balanced. ------------------------------------------------------
int bal(struct tree *root)
{
    int ld; //Depth of left branches.
    int rd; //Depth of right branches.

    if(root=NULL)
    {
        return(1);
    }

    ld=maxdepth(root->left);    //Segfaults here. BLAH.
    rd=maxdepth(root->right);
    if((ld-rd>1) || (rd-ld>1))
    {
        return(0);
    }

}
*/
//------------------------MaxDepth function to calculate the depth of the tree. --------------------------------
int maxdepth(struct tree *root)
{
    int ldepth;
    int rdepth;
    if(root==NULL)
    {
        return 0;
    }


    ldepth=maxdepth(root->left);
    rdepth=maxdepth(root->right);
    if(ldepth > rdepth)
    {
        return ldepth+1;
    }
    else
    {
        return rdepth+1;
    }
}

//-------------------------Traverse (print) --------------------------------------------------------------------------------------
int traverse(struct tree *root)
{ 
    if(root==NULL)
    {
        return 0;
    }
    traverse(root->left);
    printf("%d ", root->data);
    traverse(root->right);

}

//-------------------------Main! ------------------------------------------------------------------------------------
int main(void)
{
    struct tree *root=NULL;
    char buffer[120]; //Temp storage
    int num; //User input will move from buffer to here.
    int searchVal;
    int balval;

//Memory Allocations block. 
    root=NULL;  
    printf("Hello. \n");
    while(1==1)
    {
        printf("> ");

        fgets(buffer, sizeof(buffer), stdin);

        switch(buffer[0])
        {
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
                if(1==(sscanf(buffer, "%d", &num))){
                    if(0==search(root, num))
                    {
                    root=insert(root, num);
                    }
                    else printf("Number is already in list. \n");
                }
                break;

            case 's':
                if(1==(sscanf(buffer, "s %d", &num))){
                    if(1==search(root, num)){
                        printf("That number is in the list. \n");
                    }else{
                        printf("That number is not in the list. \n");
                    }
                }
                break;


            case 'p':

                traverse(root);
                printf("\n Tree depth: %d \n", maxdepth(root));

                //if(0==bal(root)){
                //  printf("Balance returned 0, your tree sucks. \n");
                //}
                //if(1==bal(root))
                //{
                //  printf("Balance returned 1, congratulations. Go listen to Sunlounger. :) \n");
                //}

                break;

            case 'd':
                if(1==(sscanf(buffer, "d %d", &num))){
                    root=delete(root, num);
                }


            case '?':
                help();
                break;

            case 'q':
            case 'Q':
                exit(0);
                break;

            default:
                help();
                break;

            }
    }
}

在 Delete 中，if(num>root->data) 是我发生段错误的地方(第 105 行)。这是该函数第一次尝试访问树 *root 中的内容。从代码中可以看出，平衡函数中也存在段错误，但目前我并不担心。

感谢任何帮助或指点(哈哈)。提前致谢。

Answer 1

首先看下面的错误。这应该可以解决您的问题。享受..

在函数struct tree * delete(struct tree *root, int num)

这不是检查 null.. 而是将 root 分配给 null。稍后在该函数中，您试图取消引用 null 指针(Seg 错误)

 if(root=NULL)

应该是

if(root==NULL) or if(!root)