algorithm - 如何按字母顺序列出三元搜索树的单词？

Question

我怎样才能按字母顺序列出 TST 包含的单词？

与 BST 不同，在 BST 中，中序遍历可以解决问题，这对 TST 不起作用。预排序和后排序遍历都不会。

更重要的是，与某些 BST 实现的节点相反，TST 的节点包含字母而不是单词。还有一些字母在从左节点移动到右节点时没有被包括在内。

我似乎可以理解它。

下图按字母顺序显示了 TST 的单词列表。

图片来自:http://www.geeksforgeeks.org/ternary-search-tree/

Answer 1

您可以将三元搜索树视为不同二叉搜索树的层次结构 - 黑线将同一 BST 中的节点连接在一起，虚线将不同的 BST 连接在一起。

您可以通过修改后的中序遍历列出 TST 中的所有单词。具体来说，进行中序遍历，并在每个节点上递归列出 TST 中链接到当前节点的所有单词，以到目前为止路径上的任何字母为前缀。

这是一些伪代码:

function tst_inorder_traversal(node) {
    _tst_inorder_traversal_aux(node, "");
}


function _tst_inorder_traversal_aux(node, prefix) {
    if (node is not null) {

        /* Start normal in-order traversal. 
          This prints all words that come alphabetically before the words rooted here.*/
        _tst_inorder_traversal_aux(node->left, prefix);

        /* List all words starting with the current character. */
        if (node marks the end of the word) 
            print(prefix + tree->character);

        _tst_inorder_traversal_aux(node->middle, prefix + node->character);

        /* Finish the in-order traversal by listing all words that come after this word.*/
        _tst_inorder_traversal_aux(node->right, prefix);
    }
}

希望这对您有所帮助!