在C中使二叉搜索树为空时存在困惑。

huangapple go评论52阅读模式
英文:

Confusion about making binary search tree EMPTY in C

问题

I want to define a function which makes binary search tree empty with return-type void.

These are my codes as below:

Node structure

typedef struct _Node {
    int data;
    struct _Node* l_child;
    struct _Node* r_child;
} Node;

BST_To_Empty

void BST_To_Empty(Node* root)
{
    if(root)
    {
        BST_To_Empty(root->l_child);
        BST_To_Empty(root->r_child);
        free(root);
    }
    printf("[BST_To_Empty] Now BST is NULL");
}

CheckEmpty

void isEmpty(Node* root)
{
    if (root == NULL)
    {
        printf("NULL");
    }
    else
    {
        printf("Not NULL");
    }
}

With these codes, I made the main function as below:

int main()
{
    Node* root = NULL;
    // Some Initialization
    BST_To_Empty(root);
    CheckEmpty(root);
}

So I think I can get a result that "BST is NULL" and "NULL," but I got "BST is NULL" and "Not NULL." I have a little confusion, why the result of "CheckEmpty" is "Not NULL" although I made root free? What should I modify to get the result of "CheckEmpty" as "NULL"?

Thanks for your help.

英文:

I want to define a function which makes binary search tree to empty with return-type void.

These are my codes as below :

_Node structure

typedef struct _Node {
    int data;
    struct _Node* l_child;
    struct _Node* r_child;
} Node;

BST_To_Empty

void BST_To_Empty(Node* root)
{
    if(root)
    {
        BST_To_Empty(root->l_child);
        BST_To_Empty(root->r_child);
        free(root);
    }
    printf("[BST_To_Empty] Now BST is NULL");
}

CheckEmpty

void isEmpty(Node* root)
{
    if (root == NULL)
    {
        printf("NULL");
    }
    else
    {
        printf("Not NULL");
    }
}

With these codes I made main function as below :

int main()
{
    Node* root = NULL;
    // Some Initialization
    BST_To_Empty(root);
    CheckEmpty(root);
}

So I think I can get a result that
"[BST_To_Empty] Now BST is NULL" and
"NULL"

But I got
"[BST_To_Empty] Now BST is NULL" and
"Not NULL"

I have a little confusion, why the result of "CheckEmpty" is "Not NULL" although
I made root free?

What should I modify to get result of "CheckEmpty" is "NULL"?

Thanks for your help.

答案1

得分: 0

函数BST_To_Empty声明如下:

void BST_To_Empty(Node* root)

处理在main函数中声明的指针root的值的副本:

Node* root = NULL;
BST_To_Empty(root);

在函数内部更改原始指针的值的副本不会改变原始指针。而且,free函数也接受一个按值传递的指针,并不会将原始指针设置为NULL

您需要通过引用将原始指针root传递给函数。

在C中,通过引用传递对象意味着通过指向它的指针间接传递它。

因此,函数将如下所示:

void BST_To_Empty(Node **root)
{
    if (*root)
    {
        BST_To_Empty(&((*root)->l_child));
        BST_To_Empty(&((*root)->r_child));
        free(*root);
        *root = NULL;
    }
}

并且可以这样调用:

BST_To_Empty(&root);

然后,函数isEmpty应该声明和定义如下:

int isEmpty(const Node *root)
{
    return root == NULL;
}

而且这些函数不应该显示任何消息。调用这些函数的人将决定是否输出消息,例如:

if (isEmpty(root))
{
    puts("NULL");
}
else
{
    puts("Not NULL");
}
英文:

The function BST_To_Empty declared like

void BST_To_Empty(Node* root)

deals with a copy of the value of the pointer root declared in main

Node* root = NULL;
BST_To_Empty(root);

Changing the copy of the value of the original pointer within the function leaves the original pointer unchanged. And moreover the function free also accepts a pointer by value and does not set the original pointer to NULL.

You need to pass the original pointer root to the function by reference.

In C passing an object by reference means passing it indirectly through a pointer to it.

That is the function will look like

void BST_To_Empty(Node **root )
{
    if( *root )
    {
        BST_To_Empty( &( *root )->l_child );
        BST_To_Empty( &( *root )->r_child );
        free( *root );
        *root = NULL;
    }
}

and be called like

BST_To_Empty( &root );

In turn the function isEmpty should be declared and defined like

int isEmpty( const Node *root )
{
    return root == NULL:
}

And the functions should not display any message. It is the caller of the functions that will decide whether to output a message as for example

if ( isEmpty( root ) )
{
    puts("NULL");
}
else
{
    puts("Not NULL");
}

huangapple
  • 本文由 发表于 2023年5月25日 05:37:59
  • 转载请务必保留本文链接:https://go.coder-hub.com/76327568.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定