C++二叉树：使用指向指针的指针删除单孩子节点问题排查

咱们先一步步拆解你的问题，搞清楚各个版本的问题所在，以及老师要求用指针的指针的核心原因。

一、版本1失效的根本原因 #

你版本1的代码里犯了一个典型的指针误区：

Node** tmp = &root;

这里的root是函数的局部参数指针，它只是二叉树中对应节点的一个"副本指针"。你取它的地址得到的tmp，指向的是这个局部变量本身，而不是二叉树中真正指向该节点的指针（比如父节点的pLeft/pRight，或者根节点的pRoot）。

所以当你执行delete *tmp;和*tmp = child;时，只是修改了局部变量root的值，完全不会影响二叉树的实际结构——父节点的指针仍然指向原来被删除的节点地址，这就导致了悬空指针，程序自然无法正常工作。

二、为什么老师要求用指针的指针？ #

版本2和你后来更新的实现，本质是**"内容替换"**：把单孩子节点的内容复制到当前节点，然后删除子节点。这种方式虽然能运行，但和老师要求的逻辑完全不同：

• 老师要你实现的是真正删除节点，并让父节点的指针直接指向子节点，这才是二叉树节点删除的标准指针操作逻辑；
• 内容替换的方式在节点数据量大时，复制成本很高，而且逻辑上是"偷梁换柱"，不是真正的节点删除。

指针的指针的核心作用，就是让你能直接修改二叉树中实际存储的指针（比如父节点的左/右指针、根指针），而不是修改局部副本指针。

三、正确的指针的指针实现方式 #

你需要把函数参数改成指针的指针，递归时传递的是当前节点左/右指针的地址，这样才能直接修改树的结构：

void BinTree::deleteSingle(Node** ppNode) {
    if (*ppNode == nullptr) {
        return;
    }

    // 先递归处理左右子树，注意传递的是指针的指针
    deleteSingle(&((*ppNode)->pLeft));
    deleteSingle(&((*ppNode)->pRight));

    Node* pCurrent = *ppNode;
    // 仅含左子节点的情况
    if (pCurrent->pLeft != nullptr && pCurrent->pRight == nullptr) {
        Node* pChild = pCurrent->pLeft;
        delete pCurrent; // 删除当前节点
        *ppNode = pChild; // 让父节点的指针直接指向左孩子
    }
    // 仅含右子节点的情况
    else if (pCurrent->pRight != nullptr && pCurrent->pLeft == nullptr) {
        Node* pChild = pCurrent->pRight;
        delete pCurrent;
        *ppNode = pChild;
    }
    // 有两个孩子或无孩子，不处理
}

调用时从根指针的地址开始：

deleteSingle(&pRoot);

四、关于版本2的隐藏问题 #

版本2的代码其实存在未定义行为：

delete root;
*root = *child;

delete root之后，root指向的内存已经被操作系统回收，此时再解引用root进行赋值操作，属于非法访问已释放内存——虽然看起来运行正常，但这是运气问题，在不同环境下可能崩溃或出现诡异的bug，绝对不能这么写。

你后来更新的实现（直接复制键、数据、子指针再删除子节点）是合法的，但正如前面所说，这不是老师要求的指针操作逻辑。

五、和Node类析构/赋值运算符的关系 #

你的问题和Node的析构函数、赋值运算符没有直接关系：

• 版本1的错误是指针操作的逻辑问题，和析构/赋值无关；
• 版本2的错误是非法访问已释放内存，和赋值运算符的实现无关，只是刚好你的赋值运算符能运行，但本质是错误的。

内容的提问来源于stack exchange，提问作者V_swan