非递归删除二叉树的问题

Question

Alex Allain 的 Jumping Into C++ 给我分配了一项难以置信的任务，即非递归地删除二叉搜索树（第 17 章）。我想出了一种方法来简化此任务，方法是修改我的结构定义，使其包含指向 parent 节点的指针，而不是简单的左右指针。我尽量避免使用 stack/linked 列表数据结构。

我的算法是：

检查当前节点的L和R指针是否都为NULL
如果是，则删除该节点并转到父节点。
如果没有，则转到L和R节点，直到完成第1步（如果L/R指针都被占用，则先左）
当我们命中 NULL 父节点（根节点的父节点为 NULL）时，我的算法结束

问题是我陷入了无限循环。我怀疑我的 insert() 函数有问题，但我可能是错的。

以下代码包括到目前为止提到的所有 functions/structures：

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

Answer 1

当你删除一个节点时，你需要将它的指针从parent中清空，以左右指针中指向它的那个为准。如果有parent。否则第一个 if 测试永远不会为真，您将永远遍历。

非递归删除二叉树的问题

Trouble with deleting a binary tree non-recursively

c++

binary-tree

pointers

while-loop