D&F学数据结构系列——前驱和后继

作者：AllinToyou | 2024-05-31 05:56:08

踩

数据结构结点的前驱后继

前驱和后继

本文所述为二叉排序树的前驱和后继，如果想了解二叉排序树的概念，可以参考我的博文http://www.cnblogs.com/sage-blog/p/3864640.html

给定一个二叉查找树中的结点，有时候要求找出在中序遍历顺序下它的后继。如果所有的关键字均不同，则某一结X点的后继就是所有（结点值）大于X的结点中最小的那个。

包含两种情况：

情况一：结点X的右子树非空，则X的后继是其右子树中最左的结点

情况二：结点X的右子树为空，设X的后继为Y。则Y是X的最低祖先结点，且Y的左儿子也是X的祖先（X自身也可以看做是X的祖先）

 1 BT* TreeSuccessor(BT* T)
 2 {
 3     BT*

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/650699