键树

在前面用来表示集合的数据结构中，元素由主关键字唯一表示，关键字值总是作为一个整体存于结点中。相应的搜索操作都是建立在关键字值之间的比较的基础上，因而称为比较关键字的搜索。

如果一个关键字可以表示成字符的序号，即字符串，那么可以用键树（keyword tree），又称数字搜索树（digital search tree）或字符树，来表示这样的字符串的集合。键树是一棵多叉树，树中每个结点并不代表一个关键字或元素，而只代表字符串中的一个字符。例如，它可以表示数字串中的一个数位，或单词中的一个字母等等。根结点不代表任何字符，根以下第一层的结点对应于字符串的第一个字符，第二层的结点对应于字符串的第二个字符……每个字符串可由一个特殊的字符如“$”等作为字符串的结束符，用一个叶子结点来表示该特殊字符。把从根到叶子的路径上，所有结点（除根以外）对应的字符连接起来，就得到一个字符串。因此，每个叶子结点对应一个关键字。在叶子结点还可以包含一个指针，指向该关键字所对应的元素。整个字符串集合中的字符串的数目等于叶子结点的数目。如果一个集合中的关键字都具有这样的字符串特性，那么，该关键字集合就可采用这样一棵键树来表示。事实上，还可以赋予“字符串”更广泛的含义，它可以是任何类型的对象组成的串。