偶然在网上看见C#实现的键树，以前不知这东东是啥玩意（数据结构没过关），有何用途？于是仔细研学了一把，本人对这种算法的东西，看着就头痛，自己照着做了一遍。基本参考网上已实现的代码算法，放于此，给自己做个参考，以备查阅。以下是代码：
using System; using System.Collections.Generic; using System.Text; namespace AlgorithmTest { /// <summary> /// 键树(一般应用于大数据量的查找) /// <remarks> /// 如果一个关键字可以表示成字符的序号，即字符串，那么可以用键树（keyword tree）， /// 又称数字搜索树（digital search tree）或字符树，来表示这样的字符串的集合。 /// 键树是一棵多叉树，树中每个结点并不代表一个关键字或元素，而只代表字符串中的一个字符。 /// 例如，它可以表示数字串中的一个数位，或单词中的一个字母等等。根结点不代表任何字符， /// 根以下第一层的结点对应于字符串的第一个字符，第二层的结点对应于字符串的第二个字符…… /// 每个字符串可由一个特殊的字符如“$”等作为字符串的结束符，用一个叶子结点来表示该特殊字符。 /// 把从根到叶子的路径上，所有结点（除根以外）对应的字符连接起来，就得到一个字符串。因此， /// 每个叶子结点对应一个关键字。在叶子结点还可以包含一个指针，指向该关键字所对应的元素。 /// 整个字符串集合中的字符串的数目等于叶子结点的数目。如果一个集合中的关键字都具有这样的字符串特性， /// 那么，该关键字集合就可采用这样一棵键树来表示。事实上，还可以赋予“字符串”更广泛的含义， /// 它可以是任何类型的对象组成的串。 /// </remarks> /// </summary> [Serializable()] public class KeyTree { private bool _keyChanged = false; //根节点 private KeyTreeNode rootNode = new KeyTreeNode(); //添加数到键数中 public void AddKey(long key) { string strKey = key.ToString(); KeyTreeNode tempNode = rootNode; for (int i = 0; i < strKey.Length; i++) { int index = int.Parse(strKey[i].ToString()); if (i == strKey.Length - 1) { tempNode.endFlags[index] = true; _keyChanged = true; break; } if (tempNode.pointers[index] == null) tempNode.pointers[index] = new KeyTreeNode(); tempNode = tempNode.pointers[index]; } } //删除key public void RemoveKey(long key) { string strKey = key.ToString(); KeyTreeNode tempNode = rootNode; for (int i = 0; i < strKey.Length; i++) { int index = int.Parse(strKey[i].ToString()); if (tempNode != null) { if (i == strKey.Length - 1 && tempNode.endFlags[index] == true) { tempNode.endFlags[index] = false; _keyChanged = true; } else { tempNode = tempNode.pointers[index]; } } else { break; } } } //key存在判定 public bool IsExist(long key) { string strKey = key.ToString(); KeyTreeNode tempNode = rootNode; for(int i =0;i<strKey.Length;i++) { int index = int.Parse(strKey[i].ToString()); if (tempNode != null) { if (i == strKey.Length - 1 && tempNode.endFlags[index] == true) return true; else tempNode = tempNode.pointers[index]; } else { return false; } } return false; } //key清除 public void Clear() { for (int i = 0; i < rootNode.pointers.Length; i++) { rootNode.pointers[i] = null; rootNode.endFlags[i] = false; } _keyChanged = true; _lstKey.Clear(); } //取得全部的key private List<long> _lstKey = new List<long>(); public List<long> Keys { get { if (_keyChanged) { _lstKey.Clear(); FindAllKey(rootNode, "", ref _lstKey); _keyChanged = false; } return _lstKey; } } //（这个递归，头都想大了，我太菜了。。。） private void FindAllKey(KeyTreeNode treeNode, string strKey, ref List<long> lstKey) { for (int i = 0; i < treeNode.pointers.Length; i++) { string keyTemp = strKey + i.ToString(); if (treeNode.endFlags[i] == true) { lstKey.Add(Convert.ToInt64(keyTemp)); } if (treeNode.pointers[i] != null) { FindAllKey(treeNode.pointers[i], keyTemp, ref lstKey); } } } } [Serializable] public class KeyTreeNode { public KeyTreeNode[] pointers = new KeyTreeNode[10]; public bool[] endFlags = new bool[10]; } }
测试代码：
m_keyTree.Clear(); System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch(); sw.Start(); for (long i = 0; i < long.Parse(this.textBox1.Text); i++) { m_keyTree.AddKey(i); } sw.Stop(); MessageBox.Show("time:" + sw.ElapsedMilliseconds); System.Runtime.Serialization.Formatters.Binary.BinaryFormatter bf = new System.Runtime.Serialization.Formatters.Binary.BinaryFormatter(); System.IO.MemoryStream ms = new System.IO.MemoryStream(); bf.Serialize(ms, m_keyTree); MessageBox.Show("byte(kb):" + ms.Length / 1024);
经过测试，发现这种键数的查找速度和HashTable基本相当，但是内存用量却只有HashTable的一半不到。这个对于大容量的数据查找还是一种可行的方法。
备注：key值为long型，对于一些字符串或对象集合的查找处理，可用对象的GetHashCode（）方法转换成一个哈希值，再使用KeyTree。