3 진 검색 트리의 단어를 사전 순으로 나열하는 방법은 무엇입니까?

Question

알파벳순으로 TST에 포함 된 단어를 나열하려면 어떻게해야합니까?

주문형 순회가 트릭을 수행하는 BST와 달리 TST는 작동하지 않습니다. 순회 선전이나 순항 선전도하지 않습니다.

그렇다면 TST의 노드는 일부 BST 구현의 노드와는 달리 단어가 아닌 알파벳을 포함합니다. 그리고 왼쪽 노드에서 오른쪽 노드로 이동할 때 포함되지 않는 알파벳이 있습니다.

나는 그 주위에 내 머리를 얻을 수 있습니다.

아래 그림은 TST 단어 목록을 알파벳 순서로 보여줍니다.

이미지에서 : http://www.geeksforgeeks.org/ternary-search-tree/

Answer 1

당신은 다른 이진 검색 나무의 계층 구조로 삼항 검색 트리 생각할 수

- 검은 선이 같은 BST 함께 노드를 연결하고, 점선 링크 서로 다른 BST를 함께 사용하십시오.

수정 된 inorder 순회를 수행하여 TST의 모든 단어를 나열 할 수 있습니다. 특히, inorder traversal을 수행하고 각 노드에서 현재 노드에 연결된 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); 
    } 
} 

희망 :

는 여기에 몇 가지 의사 코드입니다!