Как перечислить в алфавитном порядке слова тройного дерева поиска?

Question

Как я могу перечислить слова, содержащиеся в TST, в алфавитном порядке?

В отличие от BST, где обход в порядке сделает трюк, это не сработает TST. Также не было предварительного заказа и послепорядка.

Кроме того, узлы TST содержат алфавиты, а не слова, в отличие от узлов некоторой реализации BST. И есть несколько алфавитов, которые не включаются при переходе с левых узлов на правые узлы.

Похоже, что я обволакиваю голову.

На рисунке ниже показан список слов 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); 
    } 
} 

Надеется, что это помогает!