删除（最小）节点的时候为什么不能用node=node->right的语句而使用return右节点？

Question

如上，希望老师耐心指正。我的C++基本功可能有点渣

Answer 1

liuyubobobo 2017-07-26 04:58:28

在这个课程中，二叉树的所有算法都使用递归算法实现。在删除最小节点这个递归算法中，removeMin(Node* node)完成的是“删除以node节点为根节点的二叉树中的最小节点，然后返回新的二叉树的根节点”，返回的节点用于在上层递归中，具体表现在这句话里：

node->left = removeMin(node->left);

在removeMin中，使用node = node->right是完全无法改变整个二叉树的结构的。因为node只是一个局部的指针变量，改变node的指向，但是在removeMin结束以后，node这个指针就消除了，整个二叉树的结构没有变化。（这不仅仅是C++的问题，在Java或者其他语言中同理，只不过node不是指针而是引用而已。）

如果有必要，你可以使用一个小的测试数据，比如只有两个节点的二叉树，实际跟踪一下，看看删除节点，使用node = node->right的逻辑，看看会发生什么？数据是如何变化的？哪里和你的预期不一样？再仔细思考一下为什么会这样？

另外，你也可以尝试一下，实现这个算法的非递归算法，相信会对你理解这个递归算法有更深刻的认识。（事实上，二叉树整章的算法都可以写成非递归算法，是一个非常非常好的练习，我甚至认为是非常有必要的练习：））

• 提问者 gin_gin #1

  非常感谢！