이진 검색 트리에서 순차 찾기 찾기 재순환 사용

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

그리고이야 내 in-order successor를 검색하는 함수

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

이제는 내 기능이 리콜되지 않는다고 생각합니다. 실제로 원하는 노드에있을 때 gnizing합니다. 함수의 끝 부분에 다른 기본 구문 또는 if else 문이 있는지 확인해야한다고 생각합니다. 그러나 현재 노드에서 재귀 호출을하지 않고이 작업을 수행하는 방법을 생각할 수는 없지만 무한 루프로 끝납니다.

Answer 1

가장 쉬운 방법은 상위 포인터를 추가하는 것입니다. 그런 다음 "다음"을 얻으려면 형제를 찾을 때까지 올라가십시오.

부모를 사용할 수없는 경우 (예 : 트리가 중복 하위 분기를 허용하는 등) 종종 하위 개체를 스택으로 유지해야합니다. 다음 객체를 얻으려면, 우리가 왼쪽 잎이면 그것은 부모입니다. 우리가 오른쪽 잎이면 부모가 왼쪽 잎이면 그것은 조부모입니다. 그렇지 않으면 우리는 올라가서 조부모가 왼쪽인지 확인해야합니다 조부모의 잎. (우리가 루트를 친다면 우리 노드는 마지막 오른쪽 리프였습니다).