算法 8.9.txt

《数据结构及应用算法教程》一书的源代码。作者：严蔚敏

算法 8.9
bool Insert_DLTree( DLTree &root, KeysType K, int &n )
{
    // 指针root所指双链树中已含n个关键字，若不存在和K相同的关键字，
    // 则将关键字K插入到双链树中相应位置，n增1且返回TRUE;
    // 否则不再插入且返回FALSE
        p = root->first;  f = root;  j = 0;
        while ( p && j < K.num ) {           // 在键树中进行查找
          pre = NULL; 
        while( p && p->symbol < K.ch[j] )  // 查找和K.ch[j]相同的结点
            { pre = p;  p = p->next; }
          if ( p && p->symbol == K.ch[j] )  
            { f = p;  p = p->first;  j++; }   // 找到后进入到键树的下一层
          else {  // 没有找到和K.ch[j]相同的结点，插入K.ch[j]
             s = new DLNode;  s->kind = BRANCH;  s->symbol = K.ch[j++];
             if (pre)  pre->next = s;
             else  f->first = s;
             s->next = p;  p = s; 
             break;
          }//else
        }//while
        if ( p && j == K.num )
          if ( p->first->kind == LEAF )  return FALSE;  // 键树中已存在K
          else {  // 键树中已存在相同前缀的单词,插入由剩余字符构成的单支树
            while ( j <= K.num ) {
              s = new DLNode;  
              s->next = p->first;  p->first = s;  p = s;
              if ( j < K.num) 
                { s->kind = BRANCH;  s->symbol = K.ch[j++]; s->first = NULL; }
              else 
                { s->kind = LEAF;  s->symbol = '$';  n++;  s->idx = n;  }
            }//while
            return TRUE;
          }//else
}//Insert_DLTree