树形索引（键树）

一、键树

键树又称为数字查找树，它是一颗度大于等于2的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。例如，若关键字为数值，则结点中只包含一个数位；若关键字为单词，则结点中只包含一个字母字符。这种树会给某种类型关键字的表的查找带来方便。

        我们来举一个例子吧，下面有一个集合：

{CAI,CAO,LI,LAN,CHA,CHANG,WEN,CHAO,YUN,YANG,LONG,WANG,ZHAO,LIU,WU,CHEN}

        我们先针对首字母将其分配：

{CAI,CAO,CHA,CHANG,CHAO,CHEN}

{WEN,WANG,WU}

{ZHAO}

{LI,LAN,LONG,LIU}

{YUN,YANG}

        然后对其中4个关键字大于1的子集再按照第二个字符不同进行分割，直到分割到每个子集包含一个关键字为止。如下图所示：

从根节点到叶子结点路径上的元素组成一个关键字，其中叶子结点的特殊字符$表示字符串的结束。

为了查找的方便，我们约定同一层兄弟节点关键字从左到右有序。并约定$字符小于任何字符

二、存储结构

1、孩子兄弟链表

结点结构：

symbol：存储关键码的一个字符

此外，每个非叶结点包括两个指针域：

first：存储指向第一棵子树根的指针

next：存储指向右兄弟的指针

每个叶结点只包括recptr域，存储指向该关键码记录的指针

在双链树的表示下结点类型的描述如下：

enum NodeType {leaf,nonleaf};
struct SBNode;
struct twopr
{
    SBNode *first,*next;
};
union unionptrnode
{
    RecLinkType recptr;//若是叶结点，即nodetp=leaf
    twopr tptr;//若是非叶结点，即nodetp=nonleaf
};
struct SBNode
{
    char symbol;
    NodeType nodetp;//枚举类型
    unionptrnode uptr;
};

键树的孩子兄弟链表表示的逻辑树称为双链树。例：

双链树中查找算法：

//双链树中查找算法
RecLinkType KeyTreeSearch(SBNode *t,char K[])
{//在由指针t指向其根的非空双链树中查找关键码等于K的记录
    //若查找成功，则返回指向记录指针，否则返回空指针
    if(!t) return NULL;
    int num=strlen(K);
    SBNode *p;
    int i=0;
    p=t->uptr.tptr.first;
    while(p)
    {
        switch(p->nodetp)
        {
            case leaf:
                if(i==num) return p->uptr.recptr;//查找成功
                else return NULL;//查找失败
                break;
            case nonleaf:
                i=0;
                if(i<num&&p->symbol<K[i])
                    p=p->uptr.tptr.next;//查找关键码第i位字符
                if(i==num&&p->symbol=='$')
                    return(p->uptr.recptr);//查找成功
                if(i<num&&p->symbol==K[i])
                {
                    p=p->uptr.tptr.first;//准备查找下一位
                    i++;
                    break;
                }
                if(i==num&&p->symbol!='$') return NULL;//查找失败
                break;
        }
    }
    return NULL;//查找失败
}

键树中每个结点的最大度和关键码的基数有关，若为单词，则d=26，若为数值，则d=10.键树的深度h取决于关键码中字符或数位的个数。假设关键码是随机的（即关键码中每一位取基数中任何值的概率相等），则在双链树中对每一位的平均查找长度为(1+d)/2,。又假设关键码中字符（或数位）的个数都是h，则在双链树中查找的平均查找长度为(1+d)*h/2

在双链树中插入一个关键码，首先要查找，以便关键码的前缀部分与树中已存储的与之匹配的从根开始到达某个节点的部分不必重复存储，然后将关键码后续部分从头至尾按每个字符字母逐一生成结点连接在该节点之后，最后生成‘$’结点（其中还包括指向该关键码记录的指针）。

在双链树中删除一个关键码，则也需从根开始先向下查找，记下最后的分支点，该分支点过后有一条路径中字母字符构成的序列和要删除的关键码的后缀匹配，且其上不会再出现新的分支，然后，从该分支点将通向与其后缀匹配的路径上的所有结点删除。

2、多重链表

const int maxlen=30;//设关键码最大长度为30
enum NodeType {branch,leaf};
struct TNode;
struct BranchNode
{
    TNode *ptr[27];//按字母字符关键码设计，d=26,d+1=27
    int num;
};
struct LeafNode
{
    char data[maxlen];
    RecordLinkType recptr;
};
union UnionMixNode
{
    BranchNode branchfld;
    LeafNode leaffld;
};
struct TNode
{
    NodeType nodetp;
    UnionMixNode mxp;
};

RecordLinkType TrieSearch(TNode *t,char K[])
{//在Trie树上查找关键码等于给定值K的记录
    //若存在，则返回指向记录的指针，否则返回空指针
    TNode *p=t;
    int i=1;
    int num=strlen(K);
    while(p&&i<num&&p->nodetp!=leaf)//p为分支节点
    {
        p=p->mxp.branchfld.ptr[ord(K[i])];//ord求字母在字母表中的序号
    //假设字符'$'的序号为0.ord(K[i])可用K[i]-'A'+1代替
        i++;
    }
    if(p&&p->nodetp==leaf&&strcmp(p->mxp.leaffld.data,K)==1)
        return p->mxp.leaffld.recptr;
    else return NULL;
}