Поиск преемника в заказе в двоичном дереве поиска с использованием рекурсии

Question

Мне нужно найти последователя в порядке в двоичном дереве поиска. Например, дано дерево с форматом:

4 
/\ 
2 7 

и пропусканием поиска значение 2, правопреемника заказ будет 4.

Соответствующий код:

template <typename T, typename Compare=std::less<T>>class BinarySearchTree { 
    private: 
    struct Node { 

     // Default constructor - does nothing 
     Node() {} 

     // Custom constructor provided for convenience 
     Node(const T &datum_in, Node *left_in, Node *right_in) 
     : datum(datum_in), left(left_in), right(right_in) { } 

     T datum; 
     Node *left; 
     Node *right; 
    }; 

И вот мой функция поиска для последующего преемника

static Node * min_greater_than_impl(Node *node, const T &val, Compare less) { 
    // base case: empty tree 
    if (node == nullptr) { 
     return nullptr; 
    } 
    // base case: no such element exists 
    if (less((max_element_impl(node))->datum, val) || (!less((max_element_impl(node))->datum, val) 
                && !less(val, (max_element_impl(node))->datum))){ 
     return nullptr; 
    } 
    // recursive case: go right 
    if (less(node->datum, val)) { 
     if (node->right != nullptr) { 
      return min_greater_than_impl(node->right, val, less); 
     } 
    } 
    // recursive case: go left 
    else if (less(val, node->datum)) { 
     if (node->left != nullptr) { 
      return min_greater_than_impl(node->left, val, less); 
     } 
    } 
    // recurisve case: nequal to node, go right 
    else { 
     if (node->right != nullptr) { 
      return min_greater_than_impl(node->right, val, less); 
     } 
    } 
    return node; 
} 

Теперь я считаю, что проблема заключается в том, что моя функция не reco gnizing, когда он фактически находится на нужном узле. Я думаю, что мне нужно проверить это, возможно, в дополнительном базовом случае или, возможно, другом, если оператор в конце функции. Однако я не могу придумать, как это сделать, не делая рекурсивного вызова текущего узла, но это просто закончится бесконечным циклом.

Answer 1

Самый простой способ сделать это - добавить родительский указатель. Затем, чтобы получить «следующий», поднимитесь, пока не найдете брата.

Если вы не можете использовать родителя, часто по уважительным причинам (например, дерево разрешает дублирование подвеществ), вы должны сохранить свой собственный стек родительских объектов по мере того, как вы спускаетесь. Чтобы получить следующий объект, если мы левый лист, он является родителем, если мы являемся правым листом, тогда если родительский левый лист, это дедушка и бабушка, в противном случае нам нужно подняться и проверить, является ли бабушка и дедушка левой лист прадедушки. (Если мы попали в корень, то наш узел был последним правым листом).