以非遞歸方式刪除二叉樹的問題

Alex Allain的跳入C++指定了我非遞歸地刪除二叉查找樹的難以置信的任務（第17章）。我想出了一種方法來通過修改我的結構定義來簡化這個任務，以便它包含一個指向父節點的指針，而不僅僅是左指針和右指針。我儘量避免使用堆棧/鏈接列表數據結構。以非遞歸方式刪除二叉樹的問題

我完成這個算法是：

檢查當前節點的L和R指針都是NULL
如果是刪除節點，並轉到父節點。
如果沒有，轉到L和R節點，直到達到步驟1（如果左/右指針都被佔用，則先左移）
我的算法在我們擊中NULL父節點（根節點父是NULL）

問題是，我卡在一個無限的while循環。我懷疑我的insert（）函數有缺陷，但我可能是錯的。

下面的代碼包括迄今爲止提到的所有功能/結構：

struct node 
{ 
    int key_value; 
    node *p_left; 
    node *p_right; 
    node *parent; 
}; 

node* insert (node *p_tree, int key, node* parent) 
{ 
    if (p_tree == NULL) 
    { 
     node* p_new_tree = new node; 
     p_new_tree->p_left = NULL; 
     p_new_tree->p_right = NULL; 
     p_new_tree->key_value = key; 
     p_new_tree->parent = parent; 
     return p_new_tree; 
    } 

    else if(key < p_tree->key_value) 
     p_tree->p_left = insert(p_tree->p_left, key, p_tree); 

    else 
     p_tree->p_right = insert(p_tree->p_right, key, p_tree); 

    return p_tree; 
} 

void destroy_tree_Iteratively(node* p_tree) 
{ 
    int nodesDestroyed = 0; //checking to see if I delete the right amount 

    while (p_tree != NULL) 
    { 
     if (p_tree->p_left == NULL && p_tree->p_right == NULL) 
     { 
      node* placeHolder = p_tree->parent; 
      delete p_tree; 
      p_tree = placeHolder; 
     } 
     else if (p_tree->p_left != NULL) 
      p_tree = p_tree->p_left; 
     else if (p_tree->p_right != NULL) 
      p_tree = p_tree->p_right; 
    } 

    cout << "You've deleted " << nodesDestroyed << " nodes!" << endl; 
}

來源

2016-03-26 54skyxenon

我已經打印出哪些節點正在添加，它看起來很好 – 54skyxenon

@downvoter請解釋。 – EJP

當你刪除你需要空出從父它的指針，節點取其左，右指針點吧。如果有父母。否則第一個if測試永遠不會是真的，你只會永遠遍歷。

來源

2016-03-26 06:26:42 EJP

以非遞歸方式刪除二叉樹的問題

回答

相關問題