应用题
33.键树(Trie),又称数字查找树,它是一棵度大于等于2的树,树中的每个结点中不是包含一个或几个关键字,而是只含有组成关键字的符号。请用类C语言或类PASCAL语言编写一个在键树T上查找关键字等于给定值KEY的记录的算法。若查找成功,返回指向该记录的指针;否则返回空指针。
【正确答案】 在Trie树上查找给定值KEY的过程如下:沿和给定值相应的指针向下,直至叶子结点,若叶子中的关键字和KEY相等,则查找成功;若分支结点中和给定值相应的指针为空,或叶子结点中的关键字和给定值不等,则查找不成功。
typedef enum{LEAF,BRANCH}NodeKind; //结点种类{叶子,分支}
typedef struct TrieNode{
NodeKind kind;
union { struct{KeyType K;Record水infoptr}If; //叶子结点
struct{TrieNode *ptr[27];int hum}bh; //分支结点
}TrieNode,*TrieTree; //键树类型
Record *SearchTrie(TrieTree T,KeyType KEY){ //在Trie树T中查找关键字等于K的记录
for(P=T,i=0; //对KEY的每个字符逐个查找
P&&P一>kind==BRANCH&&i<K.Bum; //水P为分支结点
P=P一>bh.ptr[ord(KEY.ch[i])],++i); //ord求字符在字母表中的序号
if(P&&P一>kind==LEAF&&P一>ILK==KEY)return P一>If.infoptri //查找成功
else return null;
}
【答案解析】