在BST中查找前身 [英] Find Predecessor in a BST

问题描述

我想在不使用父指针的情况下在二叉搜索树中递归和有效地搜索前身. 我将树的根和某些数据(可以包含在BST中或不包含在BST中)作为函数的参数.

I want to search recursively and efficiently a predecessor in a binary search tree without using parent pointer. I give the root of the tree and a certain data (that can be contained or not in the BST) as parameter of the function.

我很麻烦，因为如果BST不包含数据，则该函数应该在输出中给出小于它的最大值.

I'm having troubles because if the BST does not contain the data, the function should give in output the maximum value smaller than it.

Node *recPredecessor(Node *root, int data, Node *pred){
    if(root->key > data){
        return recPredecessor(root->left, data, pred);
    }
    if(root->key < data){
        return recPredecessor(root->right, data, root);
    }
    if((root == NULL) || (root->key == data)){
        if(root == NULL){
            return pred;
        }
        if(root->key == data){
            if(root->left != NULL){
                return bstRecGetMax(root->left); //this func return node with Max key
            }else{
                return pred;
            }
        }
    }
}

推荐答案

鉴于您希望前任以有序遍历的方式结点 N 可能性:

Given you want the predecessor to node N in an in-order traversal sense, there are three possibilities:

1. N 有一个左孩子.在这种情况下，前任元素是 N 左子树的最右侧元素.
2. N 没有左孩子，并且从根到 N 的路径中至少有一个向右的步骤.在这种情况下，前任是该路径上最靠近 N 的向右步进的源节点.
3. N 没有左孩子，并且从根到它的路径上没有向右走的步骤.在这种情况下， N 是树中的最小元素，因此它没有前任.

1. N has a left child. In this case, the predecessor is the rightmost element of N's left subtree.
2. N does not have a left child, and there is at least one rightward step in the path from the root to N. In this case, the predecessor is the source node of the rightward step nearest to N on that path.
3. N does not have a left child, and there are no rightward steps along the path to it from the root. In this case, N is the minimum element in the tree, so it has no predecessor.

因此，您必须做的是跟踪最近的向右步进的源(不一定是直接父级)，作为递归搜索功能的附加参数，通过该参数您可以找到节点 N .当您达到 N 时，如果 N 没有左子的话，您便可以使用它了. ，如果 N 确实有个左孩子，则可以忽略它.

What you must do, therefore, is track the source of the most recent rightward step (not necessarily the immediate parent) as an additional parameter to the recursive search function by which you find node N. When you reach N, you will then have that ready to use in the event that N has no left child, and you can ignore it if N does have a left child.

这篇关于在BST中查找前身的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！