关于在 C 中使二叉搜索树为 EMPTY 的困惑

Confusion about making binary search tree EMPTY in C

提问人:bFur4list 提问时间:5/25/2023 最后编辑:Vlad from MoscowbFur4list 更新时间:5/25/2023 访问量:53

问:

我想定义一个函数,该函数使用返回类型 void 使二叉搜索树清空。

这些是我的代码,如下所示:

_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");
    }
}

使用这些代码,我制作了如下主要功能:

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

所以我想我可以得到一个结果 “[BST_To_Empty] 现在 BST 为 NULL”和 “空”

但我得到了 “[BST_To_Empty] 现在 BST 为 NULL”和 “非 NULL”

我有点困惑,为什么“CheckEmpty”的结果是“Not NULL”,虽然 我让root免费了?

我应该修改什么才能得到“CheckEmpty”为“NULL”的结果?

感谢您的帮助。

c 函数 binary-search-tree pass-by-reference pass-by-value

评论


答:

0赞 Vlad from Moscow 5/25/2023 #1

函数声明为BST_To_Empty

void BST_To_Empty(Node* root)

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

Node* root = NULL;
BST_To_Empty(root);

在函数中更改原始指针值的副本可使原始指针保持不变。此外,该函数还接受按值的指针,并且不会将原始指针设置为 。freeNULL

您需要通过引用将原始指针传递给函数。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");
}