[repost ]Trie树|字典树的简介及实现

original:http://hi.baidu.com/luyade1987/item/7c1977f5e9015cdf6225d224 Trie,又称字典树、单词查找树,是一种树形结构，用于保存大量的字符串。它的优点是：利用字符串的公共前缀来节约存储空间。 相对来说,Trie树是一种比较简单的数据结构.理解起来比较简单,正所谓简单的东西也得付出代价.故Trie树也有它的缺点,Trie树的内存消耗非常大.当然,或许用左儿子右兄弟的方法建树的话,可能会好点. 其基本性质可以归纳为： 1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。 2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。 3. 每个节点的所有子节点包含的字符都不相同。 其基本操作有:查找 插入和删除,当然删除操作比较少见.我在这里只是实现了对整个树的删除操作,至于单个word的删除操作也很简单. 搜索字典项目的方法为： (1) 从根结点开始一次搜索； (2) 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索； (3) 在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。(4) 迭代过程……(5) 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。 其他操作类似处理. /* Name: Trie树的基本实现 Author: MaiK Description: Trie树的基本实现 ,包括查找 插入和删除操作(卫星数据可以因情况而异) */ #include<algorithm> #include<iostream> using namespace std; const int sonnum=26,base=’a'; struct Trie { int num;//to remember how many word can reach here,that is to say,prefix [...]



via WordPress http://blog.newitfarmer.com/ai/math/13150/repost-trie%e6%a0%91%e5%ad%97%e5%85%b8%e6%a0%91%e7%9a%84%e7%ae%80%e4%bb%8b%e5%8f%8a%e5%ae%9e%e7%8e%b0#utm_source=rss&utm_medium=rss&utm_campaign=repost-trie%25e6%25a0%2591%25e5%25ad%2597%25e5%2585%25b8%25e6%25a0%2591%25e7%259a%2584%25e7%25ae%2580%25e4%25bb%258b%25e5%258f%258a%25e5%25ae%259e%25e7%258e%25b0