CODEWITHSUNDEEP
c++binary-tree
Jim
Jim

Reputation: 131

c++ iteratively destroying a binary tree

I was trying to write a code that iteratively destroys a binary tree. I know that recursion is much easier, but I thought I would try to do it iteratively (albeit using mostly C notation and using only structures, no need for classes). My thinking was something like the following:

void delete_tree (node *p_tree){
node *local_node;
node *parent;
int left_or_right;
while (p_tree->p_left != NULL || p_tree->p_right != NULL){
    parent = p_tree;
    if (parent->p_left != NULL){
        local_node = parent->p_left;
        left_or_right = 1;
    } else {
        local_node = parent->p_right;
        left_or_right = 2;
    }
    while (local_node->p_left != NULL || local_node->p_right != NULL){
        if (local_node->p_left == NULL){
            parent = local_node;
            local_node = local_node->p_right;
            left_or_right = 2;
        } else if (local_node ->p_right == NULL){
            parent = local_node;
            local_node = local_node->p_left;
            left_or_right = 1;
        } else {
            parent = local_node;
            local_node = local_node->p_left;
            left_or_right = 1;
        }
    }
    cout << "Deleting node with value: " << local_node->key_value << endl;
    delete local_node;
    local_node = NULL;
    if (left_or_right == 1){
        parent->p_left = NULL;
    } else if (left_or_right == 2){
        parent->p_right = NULL;
    }
}
cout << "Deleting node with value: " << p_tree->key_value << endl;
delete p_tree;
p_tree = NULL;

}

I don't know what is wrong with my logic. It goes like this. Traverse down the binary tree until we hit a node with no children, then delete that node. Repeat until we just have the original parent node. Then finally delete that.

Edit: I've changed the code in response to the suggestions. It now seems to work and there is no infinite loop, but when I try to print out the contents of the binary tree, that function gets stuck in an infinite loop. I know my print function is correct, so there must still be something wrong with this delete_tree function.

Upvotes: 3

Views: 273

Answers (2)

lrleon
lrleon

Reputation: 2648

I would do it with a stack of pointers to nodes. Some like this:

void preOrderStack_aux(node *p)
{
  if (p == NULL) 
    return;

  stack_t stack;

  stack_push(p); 

  while (not stack_is_empty(stack))
    {
      p = stack_pop(stack);

      if (p->p_right != NULL)
        stack_push(p->p_right);

      if (LLINK(p) != NULL)
        stack_push(p->p_link);

      // here stack has stored descendents
      free(p);
    }
}

Upvotes: 0

Dolda2000
Dolda2000

Reputation: 25855

One error is here:

while (local_node->p_left != NULL && local_node->p_left != NULL)

You're only iterating downwards while the node has two children. You want to check || instead of &&.

Upvotes: 3

Related Questions