b20-6.c

数据结构168个实验程序,很全面

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
分析:当自上而下的查找结束时,存在两种情况.一种情况,树中没有待插入关键字的同义词,此时只要新建一个叶子结点并连到分
支结点上即可.另一种情况,有同义词,此时要把同义词的叶子结点与树断开,在断开的部位新建一个下一层的分支结点,再把同义
词和新关键字的叶子结点连到新分支结点的下一层.