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

Question

如何才能按字母顺序列出TST包含的单词？

与按顺序遍历可以解决问题的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);
    }
}

希望这可以帮助！