以非递归方式删除二叉树的问题

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

以非递归方式删除二叉树的问题

回答

相关问题