有时,我们会碰到对字符串的排序,若采用一些经典的排序算法,则时间复杂度一般为O(n*lgn),但若采用Trie树,则时间复杂度仅为O(n)。
Trie树又名字典树,从字面意思即可理解,这种树的结构像英文字典一样,相邻的单词一般前缀相同,之所以时间复杂度低,是因为其采用了以空间换取时间的策略。
下图为一个针对字符串排序的Trie树(我们假设在这里字符串都是小写字母),每个结点有26个分支,每个分支代表一个字母,结点存放的是从root节点到达此结点的路经上的字符组成的字符串。
将每个字符串插入到trie树中,到达特定的结尾节点时,在这个节点上进行标记,如插入"afb",第一个字母为a,沿着a往下,然后第二个字母为f,沿着f往下,第三个为b,沿着b往下,由于字符串最后一个字符为'\0',因而结束,不再往下了,然后在这个节点上标记afb.count++,即其个数增加1.
之后,通过前序遍历此树,即可得到字符串从小到大的顺序。
实现代码如下(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; //记录该处字符串个数 11 Node* char_arr[NUM]; //分支 12 char* current_str; //记录到达此处的路径上的所有字母组成的字符串 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动态内存 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 //将父节点中的字符串添加到当前节点的字符串中 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]添加到当前节点的字符串中 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 }