前驱后继节点的实现
来源：5-9 二分搜索树的顺序性
envy
2017-07-04
上网搜了一下前驱后继的实现，发现大家的node构造函数中都有父节点这一项，然而如果有这一项的话，之前所有函数的操作都要加父节点的指向，如果不加父节点这一属性可以实现前驱后继节点吗？
另外感觉后继节点和我们的删除不一样，因为后继节点的过程应该是：节点值大于该节点val的最小节点，如果有右子树则返回右子树的最小值，如果右子树为空，则判断与父节点的关系，如果该节点是父节点的左孩子，则后继节点即位父节点，如果为右孩子，则需要一直向上找，直到找到一个节点p，p节点是其父节点q的左孩子，那么q节点就是要找的后继节点。而我们的删除只需要判断他的子树并不需要向树的顶端查找，这也就是为什么大家都用parent这一属性的原因了吧。。。是不是说如果不更改现有的node构造函数就无法实现前驱后继节点的查找了呢？
1回答
-
赞思考！
确实，后继节点的寻找不是简单的寻找该节点右子树中的最小值；前驱节点的寻找也不是简单的寻找该节点左子树中的最大值。如果在寻找前驱时。当该节点存在左子树；或者在寻找后继时，该节点存在右子树，这个问题就变得很简单，只需要寻找相应的左子树的最大值或者右子树的最小值即可。关键是若寻找前驱时，该节点的左子树为空；或者寻找后继时，该节点的右子树为空怎么办？此时，对于寻找前驱，我们就需要寻找从根节点到这个节点的路径上，比这个节点小的最大值；对于寻找后继，我们就需要寻找从根节点到这个节点的路径上，比这个节点大的最小值。
在具体实现上，使用没有指向父指针的节点当然能实现，只不过稍微不方便一些而已。这有点儿像我们事先链表，链表的节点如果只有指向下一个节点的指针，而没有指向上一个节点的指针，对于链表的所有操作都能实现，只不过对于一些操作会不方便一些。当然，如果我们的节点包含指向上一个节点的指针，我们的麻烦就变成了在每一个操作中都要维护这个指针。对于二叉树是同理的。
我在这个课程的官方github上加入了对于二叉树的前驱和后继的代码，具体在这里。在我认为必要的地方加入了注释，供参考：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/Optional-03-Predecessor-and-Successor/main.cpp
依然是，我的代码采用递归实现。感兴趣的话可以自己尝试编写非递归实现。同时，如果感兴趣，也可以尝试编写一个二叉树，其中的所有节点都包含一个指向父亲节点的指针。然后体会一下，节点中多了这个指针以后，对于哪些操作变得简单了，而对于哪些操作变得复杂了。是一个不错的练习哦：）
加油！
122017-07-10
相似问题