[题目分析] 在Trie树上查找给定值KEY的过程如下:沿和给定值相应的指针向下,直至叶子结点,若叶子中的关键字和KEY相等,则查找成功;若分枝结点中和给定值相应的指针为空,或叶子结点中的关键字和给定值不等,则查找不成功。
typedef enum{LEAF,BRANCH}NodeKind;//结点种类{叶子,分枝} typedef struct TrieNode {NodeKind kind; union {struct{KeyType K;Record *infoptr} lf; //叶子结点 struct{TrieNode *ptr[27];int num} bh; //分枝结点 }; }TrieNode,*TrieTree;//键树类型Record *SearchTrie(TrieTree T,KeyType KEY) //在Trie树T中查找关键字等于K 的记录。 {for(P=T,i=0; //对KEY的每个字符逐个查找 P && P->kind==BRANCH && i<K.num; //*P为分枝结点 P=P->bh.ptr[ord(KEY.ch[i])],++i);//ord求字符在字母表中的序号 if(P && P->kind==LEAF && P->lf.K==KEY )return P->lf.infoptr;//查找成功 else return null; }//结束SearchTrie