할 내가 블로그를 통해 작업, 트라이 데이터 구조의 삽입의 C++ 구현을 구현하기 위해 노력 해왔다

Question

있는 이해 할 수없는 나는 몇 가지가있다 http://theoryofprogramming.com/2015/01/16/trie-tree-implementation/

또한

 if (traverse->children[*word - CASE] == NULL) 

우리는 다음 주요 기능 1로 모든 요소를 ​​초기화대로 : 나는 insertword에서이 사항이 무엇을 이해 드릴 수 없습니다

#define ALPHABETS 26 
#define CASE 'a' 
#define MAX_WORD_SIZE 25 
using namespace std; 

struct Node 
    { 
    struct Node * parent; 
    struct Node * children[ALPHABETS]; 
    vector<int> occurrences; 
    }; 

    // Inserts a word 'text' into the Trie Tree 
    // 'trieTree' and marks it's occurence as 'index'. 

    void InsertWord(struct Node * trieTree, char word[], int index) 
    { 
    struct Node * traverse = trieTree; 
    while (*word != '\0') { // Until there is something to process 
    if (traverse->children[*word - CASE] == NULL) { 

     // There is no node in 'trieTree' corresponding to this alphabet 

     // Allocate using calloc(), so that components are initialised 
     traverse->children[*word - CASE] = (struct Node *) calloc(1, sizeof(struct Node)); 
     traverse->children[*word - CASE]->parent = traverse; // Assigning parent 
    } 

    traverse = traverse->children[*word - CASE]; 
    ++word; // The next alphabet 
} 

    traverse->occurrences.push_back(index);  // Mark the occurence of the word 
} 

// Prints the 'trieTree' in a Pre-Order or a DFS manner 
// which automatically results in a Lexicographical Order 
void LexicographicalPrint(struct Node * trieTree, vector<char> word) 
    { 
    int i; 
    bool noChild = true; 
    if (trieTree->occurrences.size() != 0) { 
    // Condition trie_tree->occurrences.size() != 0, 
    // is a neccessary and sufficient condition to 
    // tell if a node is associated with a word or not 
    vector<char>::iterator charItr = word.begin(); 
    while (charItr != word.end()) { 
     printf("%c", *charItr); 
     ++charItr; 
    } 
    printf(" -> @ index -> "); 

    vector<int>::iterator counter = trieTree->occurrences.begin(); 
    // This is to print the occurences of the word 

    while (counter != trieTree->occurrences.end()) { 
     printf("%d, ", *counter); 
     ++counter; 
    } 

    printf("\n"); 
} 

for (i = 0; i < ALPHABETS; ++i) { 
    if (trieTree->children[i] != NULL) { 
     noChild = false; 
     word.push_back(CASE + i); // Select a child 

     // and explore everything associated with the cild 
     LexicographicalPrint(trieTree->children[i], word); 
     word.pop_back(); 
     // Remove the alphabet as we dealt 
     // everything associated with it 
    } 
} 

    word.pop_back(); 
} 

int main() 
    { 
    int n, i; 
    vector<char> printUtil;  // Utility variable to print tree 
    // Creating the Trie Tree using calloc 
    // so that the components are initialised 
    struct Node * trieTree = (struct Node *) calloc(1, sizeof(struct Node)); 
    char word[MAX_WORD_SIZE]; 
    printf("Enter the number of words-\n"); 
    scanf("%d", &n); 
    for (i = 1; i <= n; ++i) { 
    scanf("%s", word); 
    InsertWord(trieTree, word, i); 
    } 

    printf("\n"); // Just to make the output more readable 
    LexicographicalPrint(trieTree, printUtil); 

return 0; 
} 

어떻게 우리가 null이 될 수 있습니까?

Answer 1

함수 InsertWord()은 트라이에 새 단어를 동적으로 추가하고 해당 단어의 접두사가 이미 트라이에 추가 된 다른 단어의 접두사와 일치하지 않을 때마다 새로운 노드를 만듭니다.

이것은 정확히 귀하의 회선이 테스트중인 내용입니다. 내가 볼 수 있듯이 traverse은 단어 접두사의 현재 노드에 대한 포인터입니다. *word은 접두어 뒤의 단어에서 다음 문자입니다. 단어의 현재 k -prefix에 해당하는 노드가 다음 문자에 해당하는 레이블 (포인터가 NULL입니다) 아이가없는 경우, 그것은 우리가 단어의 다음 k+1 -prefix에 대한 새로운 노드를 할당 할 필요가 의미 .