键树

键树又称为数字查找树（Digital Search Tree）或字符树，它是一棵度大于2的树，其结构受启

发于一部大型字典的“书边标目”，字典中首先标出词语中首字母分别是A,B,C,… ,Z的单词所在页，再对各部分标出词语中第二字母分别为A,B,C,…,Z的单词所在的页，以此类推。

​ 键树是一种特殊的查找树，它的结点不是包含一个或多个关键字，而是只包含组成关键字的一部分（字符或数字）。假设关键字是一个数值，则结点中只包含这个数值的某一位；如果关键字是单词，则结点中只包含一个字母字符。如图1所示。

图1 键树

这就是一棵键树，从根结点到叶子结点这条路径中的所有字符组成的字符串表示一个关键字，

这棵树表示的关键字集合为｛HAD,HAS,HAVE,HE,HEE,HIGH,HIS｝，叶子结点中的特殊符号“$”表示字符串的结束。

​ 键树有以下三个性质：

​ （1）关键字中的各个符号分布在从根结点到叶子结点的路径上，键树的深度和关键字集合的大小无关，它取决于关键字中字符或数位的个数。

​ （2）键树被约定为一棵有序树，即同一层中兄弟结点之间是依所含符号自左至右有序，并约定结束符“$”小于任何其它符号。

​ （3）键树中每个结点的最大度d和关键字的“基”有关；例如若关键字是单词，英文字母一共有26个，则d=27；若关键字是数值，数字有0-9共10个，则d=11；

​ 通常键树有两种存储结构：双链树和多重链树。接下来我们分别来学习这两种存储方式。

1、双链树存储结构

​ 双链树是以树的孩子兄弟链表来表示键树，每个分支结点包括三个域：

  symbol域：存储关键字的一个字符；
  first域：存储指向第一棵子树根结点的指针；
  next域：存储指向右兄弟的指针；

​ 其中叶子结点不含有first域，但有一个infoptr域，用来存储指向该结点中关键字记录的指针。分支结点和叶子结点的结构如图2所示。

图2 双链树的分支结点与叶子结点结构图

在设置双链树的结点时，可以设置一个枚举变量来表示结点的类型——分支结点和叶子结点。双链树的分支结点和叶子结点都有symbol域和next域，但叶子结点包含infoptr指向记录，而分支结点是first域指向其第一棵子树，不同的一个域可以用联合体表示。如下所示为双链树的结构定义：

typedef enum{BRANCH, LEAF} NodeKind; //枚举类型
typedef struct DLTNode
{
    char symbol;
    struct DLTNode* next; //指向兄弟结点的指针
    NodeKind kind;
    union
    {
        Record* infoptr; //叶子结点内的记录指针
        struct DLTNode* first; //分支结点内的孩子链指针
    };
}DLTNode, *DLTree; //双链树的类型

使用双链树表示图1中的键树如图3所示。

图3 双链树

在分支结点中，左侧指针指向子树根结点，右侧指针指向其右兄弟。每一条路径中的所记录的

关键字如图中椭圆所示。

​ 在双链树中进行查找，假设T为指向双链树根结点的指针，给定值为K.ch[0]至K.ch[num-1]，其中K.ch[0]至K.ch[num-1]表示待查找关键字中的num-1个字符，K.ch[num-1]为结束符$。从双链树的根结点出发，顺first指针找到第一棵子树的根结点，使K.ch[0]和此结点的symbol域比较，若相等，则顺first域再比较下一字符；否则沿next域顺序查找。若直到关键字指针空仍未相等，则查找不成功。

2、多重链树存储结构（Trie树）

​ 如果用树的多重链表表示键树，则树的每个结点中应含有d个指针域，此时的键树又称为Trie（音同try）树，Trie是从检索的英文单词retireve中取的中间四个字符。若从键树中某个结点到叶子结点的路径上每个结点都只有一个孩子，则可将该路径上所有结点压缩成一个“叶子结点”，且在该叶子结点中存储关键字及指向记录的指针等信息。

​ 在Trie树中也有两种结点：

​ 分支结点：包含有d个指针域和一个指示该结点中非空指针个数的域。在分支结点中不设数据域，每个分支结点所表示的字符均有其父结点中指向该结点的指针所在位置决定。

​ 叶子结点：含有关键字域和指向记录的指针域。

两种结点的结构如图4所示。

图4 Trie树的分支结点与叶子结点

则Trie树对应的结点存储结构代码如下所示：

typedef enum{BRANCH, LEAF}NodeKind;
typedef struct TrieNode
{
    NodeKind kind;
    union
    {
        struct //叶子结点
        {
            KeyType K; //关键字
            Record* infoptr; //指向记录的指针
        }lf;
        struct //分支结点
        {
            TrieNode* ptr[NUM]; //指向下一层结点的指针
            int num; //非空指针个数
        }bh;
    };
}TrieNode, *TrieTree; //键树类型

用Trie树来表示键树如图5所示。

图5 Trie树表示的键树

这棵Trie树以26个字母为基。在每一层中，有字母的指针域指向下一个结点，这样一路标识下去，直到叶子结点，叶子结点中就记录了这一条路径上的字符组成的关键字（如图8-61中椭圆中的标记），而且在叶子结点中都有一个指向记录的指针。

在Trie树中查找关键字，沿给定值相应的指针逐层向下，直到叶子结点，若叶子结点中的关键字和给定值相等，则查找成功；若分支结点中和给定值相应的指针为空，或叶子结点中的关键字和给定值不相等，则查找不成功。