我怎么能去上市在按字母顺序TST包含单词？不像BSTS凡在序遍历会做的伎俩，这是不行的TST。无论是将pre阶也不是后序遍历。更何况，TST的节点包含英文字母不相对于一些BST执行节点的话。还有一些字母从左边节点向右移动节点时，其中不包括在内。 我似乎可以让我的头周围。

How can I go about listing the words a TST contains in an alphabetical order? Unlike BSTs where an in-order traversal will do the trick, this won't work TST. Neither would pre-order nor post-order traversals. More so, the nodes of TST contain alphabets not words as opposed to the nodes of some BST implementation. And there are some alphabets which not be included when moving from the left nodes to right nodes. I can seem to get my head around it.

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

The figure below show the list of words of a TST in alphabetical order.

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

感谢。

推荐答案

您能想到的三元搜索树不同的二叉搜索树的层次 - 黑线连接起来的节点在同一BST和虚线链接不同BSTS在一起。

You can think of a ternary search tree as a hierarchy of different binary search trees - the black lines connect together nodes in the same BST, and the dotted lines link different BSTs together.

您可以通过执行修改后序遍历列出关在尖沙咀所有的话。具体而言，做一个序遍历，并在每个节点上，递归地列出了所有在尖沙咀的话链接到当前节点，prefixed通过任何字母的道路上为止。

You can list off all the words in a TST by doing a modified inorder traversal. Specifically, do an inorder traversal, and at each node, recursively list off all of the words in the TST linked to the current node, prefixed by whatever letters are on the path so far.

下面是一些伪code：

Here's some pseudocode:

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

希望这有助于！

Hope this helps!