I am studying binary search trees right now, and I came across this code

void free_tree(Node* root) {
    // Deallocates memory corresponding
    // to every node in the tree.
    Node* temp = root;
    if (!temp)
        return;
    free_tree(temp->left);
    free_tree(temp->right);
    if (!temp->left && !temp->right) {
        free(temp);
        return;
    }
}

what does !temp mean in this context? Does it mean if temp == NULL? and does that mean !temp->left or !temp->right mean "if right of temp == NULL"? I'm kind of confused with this code in general.

I tried searching for related questions, but so far got no answers.

CodePudding user response：

From the C Standard (6.5.3.3 Unary arithmetic operators)

5 The result of the logical negation operator ! is 0 if the value of its operand compares unequal to 0, 1 if the value of its operand compares equal to 0. The result has type int. The expression !E is equivalent to (0==E).

and (6.3.2.3 Pointers)

3 An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant. 66) If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function.

So these if statements

if (!temp)

and

if (!temp->left && !temp->right) {

is equivalent to

if ( temp == NULL )

and

if ( temp->left == NULL && temp->right == NULL ) {

Pay attention to that your function is wrong. It frees only memory for nodes data members left and right of which are null pointers.

A correct function can look for example the following wat

void free_tree( Node *root ) 
{
    // Deallocates memory corresponding
    // to every node in the tree.
    if ( root != NULL )
    {
        free_tree( root->left );
        free_tree( root->right );

        free( root );
    }
}

Though it will be better to declare and define it the following way

void free_tree( Node **root ) 
{
    // Deallocates memory corresponding
    // to every node in the tree.
    if ( *root != NULL )
    {
        free_tree( &( *root )->left );
        free_tree( &( *root )->right );

        free( *root );
        *root = NULL;
    }
}

After calling the function the original pointer to the root node passed to the function by reference through pointer to it will be equal to NULL.

CodePudding user response：

what does !temp mean in this context? Does it mean if temp == NULL?

Here ...

    Node* temp = root;
    if (!temp)
        return;

... yes, it means exactly that. In boolean context, a value of pointer type evaluates to true if and only if it is non-NULL. That is, pointer != NULL. The ! operator computes the logical negation, so !pointer is equivalent to pointer == NULL.

and does that mean !temp->left or !temp->right mean "if right of temp == NULL"?

No. The -> operator has higher precedence than the ! operator, so an expression of the form !x->y is equivalent to !(x->y). From context, we can determine that temp->left and temp->right designate pointers, so !temp->left and !temp->right mean temp->left == NULL and temp->right == NULL, respectively.