|
Trie樹|字典樹(字符串排序)
有時,，我們會碰到對字符串的排序,，若采用一些經(jīng)典的排序算法,，則時間復(fù)雜度一般為O(n*lgn),，但若采用Trie樹,，則時間復(fù)雜度僅為O(n),。 Trie樹又名字典樹,，從字面意思即可理解,，這種樹的結(jié)構(gòu)像英文字典一樣,，相鄰的單詞一般前綴相同，之所以時間復(fù)雜度低,，是因為其采用了以空間換取時間的策略,。 下圖為一個針對字符串排序的Trie樹(我們假設(shè)在這里字符串都是小寫字母)，每個結(jié)點有26個分支,，每個分支代表一個字母,，結(jié)點存放的是從root節(jié)點到達(dá)此結(jié)點的路經(jīng)上的字符組成的字符串。 將每個字符串插入到trie樹中,，到達(dá)特定的結(jié)尾節(jié)點時,，在這個節(jié)點上進(jìn)行標(biāo)記，如插入"afb",，第一個字母為a,，沿著a往下,，然后第二個字母為f，沿著f往下,，第三個為b,，沿著b往下，由于字符串最后一個字符為'\0',，因而結(jié)束,，不再往下了，然后在這個節(jié)點上標(biāo)記afb.count++,，即其個數(shù)增加1. 之后,，通過前序遍歷此樹，即可得到字符串從小到大的順序,。
實現(xiàn)代碼如下（g++,、VC++都編譯通過）：  1 #include <iostream> 2 #include <string.h> 3 using namespace std; 4 5 #define NUM 26 6 7 class Node 8 { 9 public: 10 int count; //記錄該處字符串個數(shù) 11 Node* char_arr[NUM]; //分支 12 char* current_str; //記錄到達(dá)此處的路徑上的所有字母組成的字符串 13 Node(); 14 }; 15 16 class Trie 17 { 18 public: 19 Node* root; 20 Trie(); 21 22 void insert(char* str); 23 void output(Node* &node, char** str, int& count); 24 }; 25 26 //程序未考慮delete動態(tài)內(nèi)存 27 int main() 28 { 29 char** str = new char*[12]; 30 str[0] = "zbdfasd"; 31 str[1] = "zbcfd"; 32 str[2] = "zbcdfdasfasf"; 33 str[3] = "abcdaf"; 34 str[4] = "defdasfa"; 35 str[5] = "fedfasfd"; 36 str[6] = "dfdfsa"; 37 str[7] = "dadfd"; 38 str[8] = "dfdfasf"; 39 str[9] = "abcfdfa"; 40 str[10] = "fbcdfd"; 41 str[11] = "abcdaf"; 42 43 //建立trie樹 44 Trie* trie = new Trie(); 45 for(int i = 0; i < 12; i++) 46 trie->insert(str[i]); 47 48 int count = 0; 49 trie->output(trie->root, str, count); 50 51 for(int i = 0; i < 12; i++) 52 cout<<str[i]<<endl; 53 54 return 0; 55 } 56 57 Node::Node() 58 { 59 count = 0; 60 for(int i = 0; i < NUM; i++) 61 char_arr[i] = NULL; 62 current_str = new char[100]; 63 current_str[0] = '\0'; 64 } 65 66 Trie::Trie() 67 { 68 root = new Node(); 69 } 70 71 void Trie::insert(char* str) 72 { 73 int i = 0; 74 Node* parent = root; 75 76 //將str[i]插入到trie樹中 77 while(str[i] != '\0') 78 { 79 //如果包含str[i]的分支存在，則新建此分支 80 if(parent->char_arr[str[i] - 'a'] == NULL) 81 { 82 parent->char_arr[str[i] - 'a'] = new Node(); 83 //將父節(jié)點中的字符串添加到當(dāng)前節(jié)點的字符串中 84 strcat(parent->char_arr[str[i] - 'a']->current_str, parent->current_str); 85 86 char str_tmp[2]; 87 str_tmp[0] = str[i]; 88 str_tmp[1] = '\0'; 89 90 //將str[i]添加到當(dāng)前節(jié)點的字符串中 91 strcat(parent->char_arr[str[i] - 'a']->current_str, str_tmp); 92 93 parent = parent->char_arr[str[i] - 'a']; 94 } 95 else 96 { 97 parent = parent->char_arr[str[i] - 'a']; 98 } 99 i++; 100 } 101 parent->count++; 102 } 103 104 //采用前序遍歷 105 void Trie::output(Node* &node, char** str, int& count) 106 { 107 if(node != NULL) 108 { 109 if(node->count != 0) 110 { 111 for(int i = 0; i < node->count; i++) 112 str[count++] = node->current_str; 113 } 114 for(int i = 0; i < NUM; i++) 115 { 116 output(node->char_arr[i], str, count); 117 } 118 119 } 120 } |
|
|
