[데이터 구조] 트 리 에 대한 소개 와 실현

트 리 는 접두사 트 리 로 한 노드 의 모든 하위 노드 에 같은 접 두 사 를 가 진 것 을 말한다.보통 문자열 검색 에 사 용 됩 니 다. 고전 사용 장면 은 검색 알림 에서 사용자 검색 어 에 대한 힌트 입 니 다. 사용자 가 현재 입력 한 검색 어 에 따라 그 단어의 접두사 와 입력 이 같 습 니 다. 위 키 를 참고 하 십시오.접사 분사 에서 어고 의 데이터 구 조 를 저장 하 는 데 사용 할 수 있다.한 편의 문장 에 대해 단 어 를 나 눌 때, 어고 와 비 교 를 통 해 어떻게 단 어 를 자 르 고 단 어 를 나 누 어야 하 는 지 에 대한 간단 한 소 개 를 찾 을 수 있다.
트 리 와 관련 된 또 다른 데이터 구 조 는 접미사 트 리 다.접미사 트 리 는 같은 접미사 의 모든 노드 로 구 성 된 트 리 데이터 구조 입 니 다.
위 키 백과 의 실현 을 참고 하여 트 리 트 리 를 간단하게 실현 하 였 습 니 다.새로운 단 어 를 삽입 하고 단 어 를 검색 하 는 것 을 포함한다.그 중에서 Trie 트 리 를 만 드 는 데 는 어고 가 끝 날 때 까지 삽입 방법 을 순환 적 으로 호출 할 수 있 습 니 다.한 단 어 를 검색 하 는 것 은 사실 유한 상태 자동 동 기 를 확인 하 는 과정 이다.나중에 위 키 를 보고 나 서 야 컴 파일 원리 에서 배 웠 던 이 정 의 를 떠 올 렸 다.쉽게 말 하면 하나의 상 태 를 정 한 후에 확실한 다음 상 태 를 조정 하거나 끝 상태 로 조정 할 수 있다.Tries 트 리 에 대해 모든 노드 는 하나의 상태 이 고 노드 간 의 연결선 은 상태 전이 이다.
다음은 코드 구현 입 니 다. 간단 한 프로그램 에서 c 와 c + 스타일 이 모두 '멘 붕' 이 있 습 니 다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ALPHABET_SIZE 26
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')
typedef struct trie_node{
		int value;
		trie_node *children[ALPHABET_SIZE];		
};

typedef struct trie{
		trie_node *root;
		int count;		
};

void initNode(trie_node *current_node){
	 for(int level = 0; level < ALPHABET_SIZE; level ++){
	 		 current_node -> children[level] = 0;
     }
     current_node -> value = -1;
}

void insert(trie *pTrie, char *key, int value){
	 if(pTrie == 0){
	 		  pTrie = (trie *) malloc(sizeof(trie));
	 		  pTrie -> count = 0;
	  }
	  pTrie -> count++;
	  trie_node *tn = pTrie -> root;
	  int length = strlen(key);
	  int level = 0, index = 0;
	  for(; level < length; level ++){
	  		index = CHAR_TO_INDEX(key[level]);
	  		if(tn -> children[index] == 0 && !(tn -> children[index])){
				  trie_node *new_node = (trie_node *) malloc(sizeof(trie_node));
				  initNode(new_node);
				  tn -> children[index] = new_node;
	        }
	        tn = tn -> children[index];
	  }
	  tn -> value = value;
	  
}
int search(const trie *pTrie, char *key){
	int result = -1;
	if(pTrie == 0){
		 return result;
  }
  trie_node *tn = ((trie *) pTrie) -> root;
  int level = 0, length = strlen(key);
  int index = 0;
  for(; level < length; level ++){
  		index = CHAR_TO_INDEX(key[level]);
  		if(tn -> children[index] == 0 || !(tn -> children[index])){
					 printf("can't finde the \" %s \"", key);
					 result = -1;
			 break; 
        }
        tn = tn -> children[index];
		result = level;
   }
	return result;
}

main(){
	   trie *pTrie = (trie *) malloc(sizeof(trie));
	   pTrie -> count = 0;
	   pTrie -> root = (trie_node *) malloc(sizeof(trie_node));
	   initNode(pTrie -> root);
	   trie_node *node = pTrie -> root;
	   insert(pTrie, "abc", -1);
	   int result = search(pTrie, "ac");
	   printf("
result num : %d
", result);
      system("pause"); 
}