바이너리 트라이 어휘 후계 알고리즘

Question

바이너리 트라이 (노드에는 값이 있지만 현재는 중요하지 않은 트라이이기 때문에)와 주어진 노드의 어휘 (키순, inorder에 의한) 후계자를 찾고 싶습니다. 노드는 부모, 왼쪽 및 오른쪽 포인터로 구현됩니다.

핵심 아이디어는 가능한 경우 왼쪽 자식을 반환하고, 그렇지 않으면 올바른 자식을 반환하고, 오른쪽 자식이있을 때까지 자식이 돌아 가지 않으면 그 자식을 반환하는 것입니다. 그러나 그것은 분명히 어떤 올바른 아이에서 순환을 유도합니다. 나는 이미 방문한 어린이를 아직 방문하지 않은 어린이와 구별하는 방법을 생각할 수 없다. "그러나 돌아올 때 어떤 분기점을 지나갈 것"이라는 생각에 뭔가가있을 수 있습니다.

편집 :의합니다 (문자가 여기에 값입니다)이 트라이가 가정 해 봅시다 예를 들어

: 모든 왼쪽 아이가 키 "0"모든 권리 아이가

 A 
    /\ 
    B C 
/\ \ 
    D E F 

은이 키 "1" . 따라서 D에 액세스하려면 키 "00"을 사용하여 액세스합니다.

는 지금은 명령 출력이 원하는 :

A with key ("") 
B with key ("0") 
D with key ("00") 
E with key ("01") 
C with key ("1") 
F with key ("11") 

이 후계자가 없어 질 때까지 successorNode 함수를 호출 달성.

편집 2

가능 오해 죄송합니다 - 나는 후계자 기능이 필요하므로 예를 들어 출력 의지가 될 : 여기

input node* with value A with key ("") -> output node* B with key ("0") 
input node* with value B with key ("0") -> output node* D with key ("00") 
input node* with value D with key ("00") -> output node* E with key ("01") 
input node* with value E with key ("01") -> output node* C with key ("1") 
input node* with value C with key ("1") -> output node* F with key ("11") 

이 (작동하지 반복자 코드, 나중에 을 더 추가합니다) :

struct TrieIterator { 
    TrieIterator() = default; 
    TrieIterator(Node *current) : current(current) {} 

    TrieIterator const& operator++() { 
     inorderAdvance(); 
     return *this; 
    } 

    TrieIterator operator++(int) { 
     auto copy = *this; 
     inorderAdvance(); 
     return copy; 
    } 

    bool operator==(const TrieIterator& other) const { 
     return current == other.current; 
    } 

    bool operator!=(const TrieIterator& other) const { 
     return !(*this == other); 
    } 

    Node const& operator*() const { 
     return *current; 
    } 

    Node& operator*() { 
     return *current; 
    } 

    Node* operator->() const { 
     return current; 
    } 

    Node* operator->() { 
     return current; 
    } 
private: 
    Node* current; 
    Node* last; 
    void inorderAdvance() { 
     if (current->isLeaf() && (current->parent()->right() == current)) { 
      current = nullptr; 
      return; 
     } 
     if (!current) { 
      return; 
     } 
     if (current->left()) { 
      current->left_.get(); 
      return; 
     } 
     if (current->right()) { 
      current->right_.get(); 
     } 
     while (!current->right()) { 
      if(!current) { 
       return; 
      } 
      current = current->parent_; 
     } 
     current->right_.get(); 
    } 
}; 

Answer 1

저는이 문제에 대해 매우 간단하고 우아한 해결책을 가지고 있습니다.이 문제는이 트라이에 대해 한 번의 탐색에서 수행 할 수 있습니다.

그럼 루트부터 시작해 보겠습니다. 이제이 트리가 이진 트리와 같기 때문에 우리는 왼쪽으로 가져 가면 0이고 그렇지 않으면 1입니다.

이제는 key를 String으로, 값을 String으로 사용하여 전역 HashMap을 추적합니다.

그래서 예를 들어 키를 00되며 값은 이제 의사 코드를 살펴 보자 이제 A

될 것입니다. 이제 때를

"" -> A 
"0" -> B 
"00" -> D 
"01" -> E 
"11" -> F 
"1" -> C 

- : 당신이

traversal(root, ""); 

으로 호출 다음과 같이 이제지도 저장소 키 값 쌍을 만드는 것입니다 그래서 당신의 main() 메소드의 내부

class Node { 
    string value; 
    Node left; 
    Node right; 
} 

map<string, string> m; // This is global map 

void traversal(Node root, string value) { 
    if(root == NULL) { 
     return; 
    } 
    m.insert(value, root.value); 
    traversal(root->left, value + '0'); 
    traversal(root->right, value + '1'); 
} 

sort(m.begin(), m.end()); 

정렬하면 순서대로 정렬됩니다.

희망이 도움이됩니다.