Найти Предшественника в BST

Question

Я хочу рекурсивно и эффективно искать предшественника в бинарном дереве поиска без использования родительского указателя. Я даю корень дерева и определенные данные (которые могут содержаться или не содержаться в BST) в качестве параметра функции.

У меня проблемы, потому что, если BST не содержит данных, функция должна выдавать на выходе максимальное значение, меньшее, чем оно.

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;
            }
        }
    }
}

Answer 1

Учитывая, что вы хотите, чтобы предшественник нода N в смысле обхода в порядке, есть три возможности:

1. N имеет левого ребенка . В этом случае предшественник является самым правым элементом левого поддерева N .
2. N не имеет левого дочернего элемента, и на пути от корня до N имеется хотя бы один правый шаг. В этом случае предшественник является узлом источника правого шага, ближайшего к N на этом пути.
3. N не имеет левого потомка, и нет никаких правых шагов по пути к нему от корня . В этом случае N является минимальным элементом в дереве, поэтому у него нет предшественника.

Поэтому вы должны отслеживать источник самого последнего правого шага (не обязательно непосредственного родителя) в качестве дополнительного параметра к функции рекурсивного поиска, по которой вы находите узел N . Когда вы наберете N , вы будете готовы к использованию в том случае, если у N нет левого ребенка, и вы сможете игнорируйте его, если у N есть левый ребенок.