c++ - 数据结构：关于二叉查找树(BinarySearchTree)的删除算法的疑问？

问题描述

问 题

Mark Allen Weiss的《数据结构与算法分析》第4章中讲到二叉查找树这种数据结构，关于删除的代码是这样的：

// 删除以t为根的BST中值为x的节点
void remove(int x, BinaryNode*& t)
{
    if ( t == NULL)
    {
        return ;
    }
    if (x < t->data)
    {
        remove(x, t->left);
    }
    else if (x > t->data)
    {
        remove(x, t->right);
    }
    // 左右都有节点的情况
    else if (t->left != NULL && t->right != NULL)
    {
        t->data = findMin(t->right)->data; // 右子树最小的节点
        remove(t->data, t->right);
    }
    else
    {
        BinaryNode* oldNode = t;
        t = (t->left != NULL) ? t->left : t->right);
        delete oldNode;
    }
}

对于这段代码，有个问题是：倒数第三行 delete oldNode 部分，如果是叶子节点，直接删除，但是这样会造成该叶子节点的父节点指向一个被删除的节点，也就是说该代码只是删除了节点，并没有让其父节点指向NULL。我自己用测试代码测试时也发现了这个情况。

真的是书本上的代码存在问题吗？

解决方案

没问题，函数参数中传递的是指针的引用BinaryNode*& t，前一句t = (t->left != NULL) ? t->left : t->right;已经把父节点中指向当前节点的指针指向当前节点的非空子节点（如果都为空则为NULL）了。

这篇关于c++ - 数据结构：关于二叉查找树(BinarySearchTree)的删除算法的疑问？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！