查找二叉搜索树的中序后继节点

核心思路

对于一个给定的节点，他的中序后继节点有两种情况:

给定节点存在右子树时，中序后继节点即为右子树中的最小值

若不存在右子树，则中序后继节点为给定节点所在的左子树的祖先

Code

BstNode* Find(BstNode* root, int data) {//寻找给定data的地址
	if (root == NULL)return NULL;
	if (data < root->data) return Find(root->left, data);
	else if (data > root->data) return Find(root->right, data);
	else return root;
}
BstNode* Getsuccessor(BstNode* root, int data) {
	BstNode* current = Find(root, data);
	if (current == NULL)return NULL;
	if (current->right != NULL) {
		return FindMin(current->right);
	}
	else {
		BstNode* successor = NULL;
		BstNode* ancestor = root;
		while (ancestor != current) {
			if (current->data < ancestor->data) {
				successor = ancestor;
				ancestor = ancestor->left;
			}
			else
			{
				ancestor = ancestor->right;
			}
		}
		return ancestor;
	}
}