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++迭代銷燬二叉樹

回答

相關問題