转自：http://www.cnblogs.com/sooner/p/3256559.html
字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。
字典树与字典很相似,当你要查一个单词是不是在字典树中,首先看单词的第一个字母是不是在字典的第一层,如果不在,说明字典树里没有该单词,如果在就在该字母的孩子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样的方法继续查找.字典树不仅可以用来储存字母,也可以储存数字等其它数据。
Trie的数据结构定义：
#define MAX 26 struct Trie { Trie *next[MAX]; int v; //根据需要变化 }; Trie *root;
MAX是表示每层有多少种类的数，如果只是小写字母，则26即可，若改为大小写字母，则是52，若再加上数字，则是62了，这里根据题意来确定。
v可以表示一个字典树到此有多少相同前缀的数目，这里根据需要应当学会自由变化。
生成字典树：将一个字符串存储在字典树上，若当前字符对应的结点已经建立，直接将统计变量v加一即可,否则还有新建结点。root结点不对应字符串中字符
void createTrie(char *str) { int len = strlen(str); Trie *p = root, *q; for(int i=0; i<len; ++i) { int id = str[i]-'0'; if(p->next[id] == NULL) { q = (Trie *)malloc(sizeof(Trie)); q->v = 1; //初始v==1 for(int j=0; j<MAX; ++j) q->next[j] = NULL; p->next[id] = q; p = p->next[id]; } else { p->next[id]->v++; p = p->next[id]; } } p->v = -1; //若为结尾，则将v改成-1表示 }
字典树的查找：
int findTrie(char *str) { int len = strlen(str); Trie *p = root; for(int i=0; i<len; ++i) { int id = str[i]-'0'; p = p->next[id]; if(p == NULL) //若为空集，表示不存以此为前缀的串 return 0; if(p->v == -1) //字符集中已有串是此串的前缀 return -1; } return -1; //此串是字符集中某串的前缀 }
1、给一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么b是a的兄弟单词，比如的单词army和mary互为兄弟单词。
现在要给出一种解决方案，对于用户输入的单词，根据给定的字典找出输入单词有哪些兄弟单词。请具体说明数据结构和查询流程，要求时间和空间效率尽可能地高。
字典树的典型应用，一般情况下，字典树的结构都是采用26叉树进行组织的，每个节点对应一个字母，查找的时候，就是一个字母一个字母的进行匹配，算法的时间复杂度就是单词的长度n，效率很高。因此这个题目可以定义一个字典树作为数据结构来查询的，时间效率会很高，这样就转化为在一棵字典树中查找兄弟单词，只要在字典树中的前缀中在存储一个vector结构的容器，这样查找起来就是常数级的时间复杂度了，效率很高的。。
数据结构可以定义如下：
struct word
{
vector<string> brother; // 用于保存每个单词的兄弟单词
word *next[26]; // 字典树中每个节点代表一个字符，并指向下一个字符
};
如上述数据结构所示，字典树的建立是在预处理阶段完成的，首先根据字典中的单词来建立字典树，建立的时候，需要稍微特殊处理一下，就是比如pots、stop和tops互为兄弟单词，那么在字典中按照首字母顺序的话，应该先遇到pots单词，那么我首先对其进行排序，结果是opts，那么字典树中就分别建立4个节点，分别为o->p->t->s，当然这个是不同层次的，在节点s处的vector容器brother中添加单词pots，遇到stop的时候，同样的方法，排序是opts，此时发现这4个节点已经建立了，那么只需要在第四个节点s处的vector容器brother中添加单词stop，tops单词的处理方法是同样的。
这样建立完字典树后，查询兄弟单词的效率就会很高了，比哈希的效率还要高；查到tops的兄弟的单词的时候，首先排序，那么就是opts，然后在字典树中查找opts，在s处将其vector容器brother中的的单词输出就是tops的所有兄弟单词。
思路二：使用unordered_map(string,vector<string>),遍历一遍输入单词,将其放到对应的key的value中，将单词按字母从小到大重新排序后作为其key。
时间复杂度：O(Nlogk),logk是单词排序的复杂度
思路三：在思路2中主要的问题是key的求取需要较多时间，从这里着手，我们换一个求key的方法：
可以直接定义一个映射关系，每个字母对应一个素数：
a=2 b=3 c=5 d=7 e=11 f=13 g=17
h=19 i=23 j=29 k=31 l=37 m=41 n=43
o=47 p=53 q=59 r=61 s=67 t=71
u=73 v=79 w=83 x=89 y=97 z=101
将每个单词所有字母的素数相乘，可以确保兄弟单词的key相同，非兄弟单词的key不同。
唯一的问题是可能key的结果太大，可以使用Java的BigInteger类。
2、C和C++中如何动态分配和释放内存？他们的区别是什么？
malloc/free是C/C++语言的标准库函数，new/delete是C++的运算符。
对于用户自定义的对象而言，用maloc/free无法满足动态管理对象的要求。对象在创建的同时要自动执行构造函数，对象在消亡之前要自动执行析构函数。由于malloc/free是库函数而不是运算符，不在编译器控制权限之内，不能够把执行构造函数和析构函数的任务强加于malloc/free。因此C++需要一个能完成动态内存分配和初始化工作的运算符new，以及一个能完成清理与释放内存工作的运算符delete。由于内部数据类型的“对象”没有构造与析构的过程，对它们而言malloc/free和new/delete是等价的。