589 字
2 分钟
二叉搜索树的中继后续节点
二叉搜索树的中继后续节点
一、引言
我们知道，在利用深度优先中的中序遍历（Inorder）时，首先访问左子树，然后是根节点，最后是右子树。
中序遍历我们之前实现过，简答回顾一下吧。
void Inorder(root){ if(root==NULL)return else { Inorder(root->left); print root->data; Inorder(root->right); }}如果你还是不懂如何实现中序遍历，以及中序遍历的样子，你可以看看我之前写的文章。😎
如果给定一个值，想要找到它的中序后继，对于一颗二叉搜索树，他将会是这棵树的下一个比他大的值。
二、思考
中序后继（In-order Successor）就是「中序遍历中当前节点的下一个节点」！ 用大白话讲：在二叉搜索树（BST）里，它是比当前节点大的最小值！
我们要研究它，就得分情况讨论。
case1：节点有右子树。我们需要深入遍历得到该右子树的最左边的节点，也就是最小值。
case2：没有右子树。需要来到最近的祖先，给定的节点将会位于祖先的左子树中。比如下图的12节点，他就没右孩子。那么它的中序后继节点就是15。
那么问题就来了，我们如何从一个孩子节点访问它的父节点呢？
我们可以加一个父节点的链接，这样类似于双向链表
struct Node{ int data; Node* left; Node* right; Node* parent;}但是如果不想多加一个链接呢？
我们可以从根节点开始，走访到给定的节点。
中序后继将会是这条路径上最深的节点或者最深的祖先。对于祖先来说，给定的节点在他的左子树上。
比如上图的12只有两个祖先，10和15。但是12在10的右边，而12在15的左边，因此15是祖先。
换句话说，如果没有右子树，那么它的中序后继就是祖先（它挂在祖先的左子树上）。
三、cpp实现
#include<iostream>using namespace std;struct Node{ int data; Node *left; Node *right;};Node* findmin(Node *root){ if(root==NULL)return NULL; while(root->left!=NULL){ root=root->left; } return root;}Node *find(Node *root,int data);Node* Getsuccessor(Node* root,int data){ //找到该节点 Node* current=find(root,data); if(current==NULL)return NULL; //case1:node has right subtree if(current->right!=NULL){ Node* temp= current->right; while(temp->left!=NULL)temp=temp->left; return temp; } //case2:no right subtree else { Node *successor=NULL; Node *ancestor=root;//祖先节点从根走下来 while(ancestor!=current){//判断从根一步步走下来的ancestor是否和当前节点重合 if(current->data<ancestor->data){ successor=ancestor; ancestor=ancestor->left;//在最后一次，ancestor会被赋值成current。 } else ancestor=ancestor->right; } return successor; }}理解了中序后继，那么中序前驱也不会很难，加油吧，孩子！🫡
二叉搜索树的中继后续节点
https://fatdog.20060113.xyz/posts/bstree-successor/ 部分信息可能已经过时