while(ptag= BRANCH)∥沿分支向下查找 for(i=0ip-> keynum&&key>p-> key; i+),/确定关键字所在子树 if(i=p-> keynum) return error,关键字太大 p=p->child[i] for(i=0;ip-> keynum&&key!=p>key;+),∥在叶子结点中查找 ifi=p-> keynum) return Error;∥找不到关键字 ptrp pos=1, eturn OK 3//BPTree Search 942 void Trie Tree Insert Key( TrieTree& T, String Type key/在Te树T中插入字符串 key, String Type的结构见第四章 q=(TrieNode* )malloc(sizeof(TrieNode)); q->kind=LEAF; q->fk-key,∥建叶子结点 klen=keya] p=T;r=1; while(p&&i<=klen&&p->bh. ptrord(keyD p=p->bh. ptrlord(key D }∥自上而下查找 ifp->kind= BRANCH)/如果最后落到分支结点(无同义词) p-> bh. ptrlord(key[)=q,∥直接连上叶子 p- >bh. num++. else∥如果最后落到叶子结点(有同义词 r=( TrieNode*) malloc(sizeof( TrieNode),∥建立新的分支结点 last-> bh. ptrlord(key[i-])=,∥用新分支结点取代老叶子结点和上一层的联系 [->kind=BRANCH: r->bh. num=2 r->bh. ptrIord(key D=q r-> bh. ptrlord(p→fk[jD=p,/新分支结点与新老两个叶子结点相连 i//Trie Tree Insert Key 分析:当自上而下的査找结束时存在两种情况一种情况树中没有待插入关键字p=T; while(p.tag==BRANCH) //沿分支向下查找 { for(i=0;i<p->keynum&&key>p->key[i];i++); //确定关键字所在子树 if(i==p->keynum) return ERROR; //关键字太大 p=p->child[i]; } for(i=0;i<p->keynum&&key!=p->key[i];i++); //在叶子结点中查找 if(i==p->keynum) return ERROR; //找不到关键字 ptr=p;pos=i; return OK; }//BPTree_Search 9.42 void TrieTree_Insert_Key(TrieTree &T,StringType key)//在 Trie 树 T 中插入字符串 key,StringType 的结构见第四章 { q=(TrieNode*)malloc(sizeof(TrieNode)); q->kind=LEAF; q->lf.k=key; //建叶子结点 klen=key[0]; p=T;i=1; while(p&&i<=klen&&p->bh.ptr[ord(key[i])]) { last=p; p=p->bh.ptr[ord(key[i])]; i++; } //自上而下查找 if(p->kind==BRANCH) //如果最后落到分支结点(无同义词): { p->bh.ptr[ord(key[i])]=q; //直接连上叶子 p->bh.num++; } else //如果最后落到叶子结点(有同义词): { r=(TrieNode*)malloc(sizeof(TrieNode)); //建立新的分支结点 last->bh.ptr[ord(key[i-1])]=r; //用新分支结点取代老叶子结点和上一层的联系 r->kind=BRANCH;r->bh.num=2; r->bh.ptr[ord(key[i])]=q; r->bh.ptr[ord(p->lf.k[i])]=p; //新分支结点与新老两个叶子结点相连 } }//TrieTree_Insert_Key 分析:当自上而下的查找结束时,存在两种情况.一种情况,树中没有待插入关键字