CODEWITHSUNDEEP
calgorithmtreebinary-tree
andre
andre

Reputation: 175

Deallocating binary-tree structure in C

I have a linked list, I guess a tree looks like this: enter image description here

-> grandma
    -> dad
        -> me
        -> sister
            -> niece
        -> brother
    -> uncle
        -> cousin

and I have a struct as following

struct Node{
    Node *parent;
    Node *next;
    Node *child;
}

How would I free that linked list?
My idea is to do a depth first search and deallocate each node?

Upvotes: 0

Views: 2546

Answers (4)

mtszkw
mtszkw

Reputation: 2783

Recursive depth-search (DFS): You're right, it's a good way to dealocate binary-tree memory:

remove(node):
    if node is null: return

    //else
    remove(left node)
    remove(right node)

    free(node)

Iterative solution: https://codegolf.stackexchange.com/questions/478/free-a-binary-tree
Since you don't want to use any recursive solution, there you can find well-described iterative one.

Upvotes: 4

CiaPan
CiaPan

Reputation: 9570

Iterative version, inspired by Day–Stout–Warren algorithm:

void removetree(Node *node)
{
    while(node != NULL)
    {
        Node *temp = node;

        if(node->child != NULL)
        {
            node = node->child;
            temp->child = node->next;
            node->next = temp;
        }
        else
        {
            node = node->next;
            remove(temp);
        }
    }
}

This algorithm somewhat like tries to convert the tree into a list single-linked with next pointers, which is very simple to destroy just by iterative unlinking and destroying the first item. However it never completes the conversion, because it unlinks and removes the head node as soon as it can, despite the rest of tree not being converted yet. So to say, it interleaves a relink step with unlink-and-destroy step.

We test with the if instruction whether the first (head) node has any children. If so, we make its child a new head and the current node becomes the new head's next node. This way we have one more next link in the first-level list. What was 'next' to the now-head node becomes a child to a previous-head node, which is now the head's first next.

transformation step

On the other hand if the head node has no children, it may be removed and its next becomes a new head.

These two steps are iterated by the while loop until all children are converted into siblings and removed afterwards.

Upvotes: 1

Mark Shevchenko
Mark Shevchenko

Reputation: 8207

You can optimize allocation/deallocation of the tree.

Imagine, you want to create tree with 20 or 30 persons. You can allocate an array of 30 Node structs:

size_t currentArraySize = 30;
Node* nodes = (Node*)malloc(currentArraySize * sizeof(Node));
size_t nextFreeIndex = 0;

To add new element you can write simple function:

Node* allocateNode()
{
    // Oops! There's not more memory in the buffer.
    // Lets increase its size.
    if (nextFreeIndex >= currentArraySize) {
        currentArraySize *= 2;
        Node* newNodes = (Node*)realloc(nodes, currentArraySize * sizeof(Node));

        // Should correct pointers (thanks to user3386109)
        if (newNodes != nodes) {
            for (size_t i = 0; i < nextFreeIndex; i++) {
                if (newNodes[i]->parent != NULL)
                    newNodes[i]->parent -= nodes += newNodes;
                if (newNodes[i]->next != NULL)
                    newNodes[i]->next -= nodes += newNodes;
                if (newNodes[i]->child != NULL)
                    newNodes[i]->child -= nodes += newNodes;
            }
        }
    }

    return nodes[nextFreeIndex++];
}

To deallocate all nodes you can just free the single pointer nodes.

Now the code looks a little scary as wrote user3386109, so we may simplify it a little:

Node* allocateNode()
{
    // Oops! There's not more memory in the buffer.
    // Lets increase its size.
    if (nextFreeIndex >= currentArraySize) {
        currentArraySize *= 2;
        Node* newNodes = (Node*)realloc(nodes, currentArraySize * sizeof(Node));

        // Should correct pointers (thanks to user3386109)
        if (newNodes != nodes)
            correctPointers(newNodes, nodes);
    }

    return nodes[nextFreeIndex++];
}

#define correctPointer(pointer, oldOffset, newOffset) if (pointer != NULL) { \\
                                                          pointer -= oldOffset; \\
                                                          pointer += newOffset; \\
                                                      }

void correctPointers(Node* newNodes, Node* nodes)
{
    for (size_t i = 0; i < nextFreeIndex; i++) {
        correntPointer(newNodes[i]->parent, nodes, newNodes);
        correntPointer(newNodes[i]->child, nodes, newNodes);
        correntPointer(newNodes[i]->next, nodes, newNodes);
    }
}

Upvotes: 2

Hafiz Muhammad Danish
Hafiz Muhammad Danish

Reputation: 1

You may use recursive solution 

free(root)
{
    if (root->next == null)
    {
        free(node)
    }
    free(root->left)
    free(right->)
}

Upvotes: -3

Related Questions