c++ - 非递归删除二叉树的问题

Question

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

我实现这个的算法是:

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

问题是我陷入了无限循环。我怀疑我的 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;
}

Answer 1

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