バイナリトライ辞書的後継アルゴリズム

Question

私はバイナリトライを持っています（ノードには値がありますが、それは今のところ問題ではないので）、私は与えられたノードの辞書的（キー、インオーダー）の後継を見つけたいと思います。ノードは親、左と右のポインタで実装されています。

私は、利用可能な場合は左の子を返し、そうでない場合は正しい子供を返し、右の子がなくなるまで子どもがいない場合は、その子供を返します。しかし、それは明らかにどんな正しい子供でもサイクルにつながります。私は既に訪問した権利を持つ子供をまだ訪問されていない子供と区別する方法は考えられません。 "しかし、戻ってきたときに何らかの枝を越えて行く"という考えに沿った何か。

EDIT：のは、（文字がここに値です）トライがあるとしましょうたとえば

：すべての左の子がキー「0」とすべての右の子を持つ

 A 
    /\ 
    B C 
/\ \ 
    D E F 

が持つキー「1」 。だからDにアクセスしたいときは、キー "00"でアクセスします。

何の後継がなくなるまでsuccessorNode関数を呼び出すことで実現

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

：

今、私が注文した出力になりたいです。

EDIT 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

私は、このトライに対して1つのトラバーサルで実行できるこの問題の非常に単純で洗練された解決策を持っています。

まず、rootで始めましょう。このトライはバイナリツリーのようなものなので、左に持っていくと0になります。それ以外の場合は0になります。

ここで、keyをString、valueを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()); 

並べ替え、それはあなたが望む順序で手配します。

希望すると便利です。