单词查找树==数据结构Tire 树
?
?
它有3个基本性质：
?根节点不包含字符，除根节点外每一个节点都只包含一个字符。 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。 每个节点的所有子节点包含的字符都不相同。
?基本操作
其基本操作有:查找 插入和删除,当然删除操作比较少见.我在这里只是实现了对整个树的删除操作,至于单个word的删除操作也很简单.
???namespace ConsoleApplication1{ public class TireTree { private TireNode root = new TireNode(' '); public TireTree() { } private void CreateTireTree(TireNode node, string word, int index) { if (word.Length == index) return; char key = word[index]; TireNode newNode = null; if (node.NextNode.ContainsKey(key)) { newNode = node.NextNode[key]; } else { newNode = new TireNode(key); node.NextNode.Add(key, newNode); } if (word.Length - 1 == index) { newNode.Word = word; } CreateTireTree(node.NextNode[key], word, index + 1); } public void AddWords(string word) { CreateTireTree(root, word, 0); } public List<string> SearchWords(string content) { List<string> result = new List<string>(); char[] charArr = content.ToCharArray(); TireNode currentNode = root; for (int i = 0; i < charArr.Length; i++) { if (currentNode.NextNode.ContainsKey(charArr[i])) //如果下个节点找得到当前字，则继续往下找下个字符。 { currentNode = currentNode.NextNode[charArr[i]]; } else if (root.NextNode.ContainsKey(charArr[i])) //如果下个节点找不到当前字，则从根节点找。 { currentNode = root.NextNode[charArr[i]]; } else //否则下个字符，也从根节点找。 { currentNode = root; } if (currentNode.IsWord) { if (!result.Contains(currentNode.Word)) result.Add(currentNode.Word); } } return result; } private class TireNode { public char Key { get; set; } public string Word { get; set; } public bool IsWord { get { return this.Word != null; } } private Dictionary<char, TireNode> nextNode = new Dictionary<char, TireNode>(); public Dictionary<char, TireNode> NextNode { get { return nextNode; } set { nextNode = value; } } public TireNode(char key) { this.Key = key; } } }}
实现方法
实现方法
搜索字典项目的方法为(1) 从根结点开始一次搜索；
?(2) 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索；
?(3) 在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
?(4) 迭代过程……
?(5) 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。
?? 测试代码
private void TestTireTree() { const int count=100; string[] Arr = new string[count]; for (int i = 0; i < Arr.Length; i++) { Arr[i] = (Guid.NewGuid()).ToString(); } // 这里是只是演示放入字符，建立Tire树 TireTree Tree = new TireTree(); foreach (string str in Arr) { Tree.AddWords(str ); } string word = "检测的字符"; List<string> ResultList= Tree.SearchWords(word); foreach(string result in ResultList) { Console.WriteLine(string.Format("检测到非法词语{0}"),result); } }代码中 CreateTireTree(TireNode node, string word, int index) 使用递归实现的，可以修改回溯版本，提高效率。
private void CreateArrayTireTree(TireNode node, string word) { char[] wordsarray = word.ToCharArray(); for (int i = 0; i < wordsarray.Length; i++) { char key = word[i]; TireNode newNode = null; if (node.NextNode.ContainsKey(key)) { newNode = node.NextNode[key]; } else { newNode = new TireNode(key); node.NextNode.Add(key, newNode); } if (i == wordsarray.Length - 1) { newNode.Word = word; } node = node.NextNode[key]; } }?