二进制trie词汇学后继算法

Question

我有二进制trie（节点有值，但因为它是一个现在无关紧要的特里）而且我想找到给定节点的词典（按键，按顺序）后继。该节点使用父指针，左指针和右指针实现。

我认为核心的想法应该是让剩下的孩子回来，如果可以的话，还是让正确的孩子回来，当没有孩子的时候回去，直到有了正确的孩子，然后归还那个孩子。但这显然会导致任何正确的孩子出现循环。我想不出有什么方法可以区分已经访问过的正确儿童和尚未访问的儿童。可能是“在返回时经过一些分支”的想法。

编辑：

例如，让我们说trie是（这里的字符是值）：

      A
     / \
    B   C
   / \   \
  D   E   F

每个左孩子都有“0”键，每个右孩子都有“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

对于这个问题，我有一个非常简单和优雅的解决方案，可以通过这个trie进行一次遍历。

所以让我们从root开始吧。现在因为这个trie就像一个二叉树，我们有条件定义，如果我们采取左边，它是0，否则它是1。

现在我将跟踪一个全局HashMap，键为String，值也为String。

所以例如关键将是00，价值将是A

现在让我们来看看伪代码。

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());

因此，在main（）方法中，您将进行调用

traversal(root, "");

现在地图存储键值对如下： -

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

现在当你排序时，它会按照你想要的顺序排列。

希望这可以帮助！