C++迭代销毁二叉树

我正在尝试编写一个迭代销毁二叉树的代码。我知道递归要容易得多，但我想我会尝试迭代地做（尽管主要使用C符号，只使用结构，不需要类）。我的想法是像下面这样：C++迭代销毁二叉树

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;

}

我不知道什么是错我的逻辑。它是这样的。遍历二叉树直到我们点击没有子节点的节点，然后删除该节点。重复，直到我们只有原始的父节点。然后最后删除它。

编辑：我已经更改了代码以回应这些建议。它现在似乎工作，并没有无限循环，但是当我尝试打印二进制树的内容时，该函数陷入无限循环。我知道我的打印功能是正确的，所以这个delete_tree函数仍然有问题。

来源

2016-04-25 Jim

一个错误是在这里：

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

你只是迭代的同时向下节点有两个孩子。你想检查||而不是&&。

来源

2016-04-25 03:45:09 Dolda2000

其中一个可能也应该说'p_right'。尽管如此，内部的逻辑被破坏 - 它应该避免下降到目前为止'local_node'被设置为'nullptr'。 –

哈哈，真正的数据。 – Dolda2000

感谢您的快速响应。我的愚蠢错误。但是我的代码在第一次遍历后似乎仍然陷入了无限循环。 – Jim

我会做一堆指向节点的指针。一些像这样的：

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

来源

2016-04-25 13:23:08 lrleon

C++迭代销毁二叉树

回答

相关问题