算法 6.16.txt

数据结构各种算法原代码及图形示例

算法 6.16
void Insert_BST( BiTree &T,  KeyType e ) {
  // 在以T为根指针的二叉排序树中插入记录e
  s = new BiTNode;;                         // 生成新的结点
  s ->data = e;  s->lchild = NULL;  s->rchild = NULL;    // 新插入结点必为叶子结点
  if (!T)  T = s;                           // 插入的结点为根结点
  else {
         p = T;
         while ( p)                         // 查找插入位置
         if ( e .key< p->data .key)
             { f = p;  p = p->lchild; }     // 应插入在左子树中
         else
             { f = p;  p = p->rchild; }     // 应插入在右子树中
         if ( e.key < f->data.key )  f->lchild = s;     // 插入为f 所指结点的左子树根
         else  f->rchild = s;               // 插入为f所指结点的右子树根
       } //else
} // Insert_BST