前缀树可用于查询一个集合中是否包含某个特定序列。上图（引自Wikipedia）表明了前缀树的查询方式。例如我们要查询序列“ted”，则会从根节点开始，顺着“t”、“e”、“d”依次遍历到叶结点。如果序列没有遍历完就已经到了叶结点，则说明集合中没有该序列。前缀树至少有以下两个好处：
查询性能与集合中元素的数量n无关，对于查找一个长度为m的序列，其时间复杂度总是O(m)，而对于二叉搜索树（Binary Search Tree）来说，其时间复杂度可能退化至O(m * log(n))。
只需对序列遍历一遍即可得到结果，且其中无需保存之前遍历的结果
有了思路之后，实现并不是什么大问题。如果要简单地构造一颗前缀树，最常用的方式便是让前缀树的每个节点包含一个哈希表，而每一次查找（Lookup）其实就是一次哈希表的查询操作。以下是PrefixTreeVisitor（也是另一个ExpressionVisitor的子类）中构造的预备代码：
public class PrefixTreeVisitor : ExpressionVisitor
{
private Hashtable m_storage;
public Hashtable CurrentStorage { get; private set; }
public bool StopLookingUpWhenMissed { get; private set; }
public PrefixTreeVisitor(Hashtable storage, bool stopLookingUpWhenMissed)
{
this.m_storage = storage;
this.StopLookingUpWhenMissed = stopLookingUpWhenMissed;
}
public Hashtable Accept(Expression exp)
{
this.CurrentStorage = this.m_storage;
this.Visit(exp);
return this.CurrentStorage;
}
}
PrefixTreeVisitor的构造函数会接受两个参数：一个作为前缀树根节点的Hashtable，以及一个标识“是否在命中失败的时候停止”。如果第二个参数为true，则对于前缀树的构造将在某次查找命中失败时中止，显然它可用于对前缀树的“查询”；如果第二个参数为false，那么在查找命失败后扩展前缀树，也就是创建新的节点（Hashtable），并建立与“父节点”的关系。这段逻辑可以从关键性的LookUp方法中得到体现：
private static readonly object s_nullKey = new object();
/// <summary>
///
/// </summary>
/// <param name="key"></param>
/// <returns>Stop or not</returns>
protected virtual bool LookUp(object key)
{
if (this.CurrentStorage == null) return true;
key = key ?? s_nullKey;
Hashtable next = this.CurrentStorage[key] as Hashtable;
if (next == null && !this.StopLookingUpWhenMissed)
{
next = new Hashtable();
this.CurrentStorage[key] = next;
}
this.CurrentStorage = next;
return next == null;
}
LookUp方法的返回值表示该次查询是否跳出。从代码中可以看出，只有当StopLookingUpWhenMissed为true时LookUp方法才会可能返回false，因为在StopLookingUpWhenMissed为false时，LookUp方法会不断地“拓展”前缀树，永远不会中止。至于在PrefixTreeVisitor的Visit等重载方法中，便是构造合适的的节点（在这里一般使用匿名类型），作为正在遍历的序列中的某个元素，并交给LookUp方法进行“深入”。如果LookUp方法返回false，则立即返回，因为前缀树已经“探底”，可以“反弹”了：
protected override Expression Visit(Expression exp)
{
if (exp == null) return exp;
var key = new
{
NodeType = exp.NodeType,
Type = exp.Type
};
if (this.LookUp(key)) return exp;
return base.Visit(exp);
}
protected override Expression VisitBinary(BinaryExpression b)
{
var key = new
{
IsLifted = b.IsLifted,
IsLiftedToNull = b.IsLiftedToNull,
Method = b.Method
};
if (this.LookUp(key)) return b;
return base.VisitBinary(b);
}
protected override Expression VisitConstant(ConstantExpression c)
{
if (this.LookUp(c.Value)) return c;
return base.VisitConstant(c);
}
protected override Expression VisitMemberAccess(MemberExpression m)
{
if (this.LookUp(m.Member)) return m;
return base.VisitMemberAccess(m);
}
protected override Expression VisitMethodCall(MethodCallExpression m)
{
if (this.LookUp(m.Method)) return m;
return base.VisitMethodCall(m);
}
...
