t_insert.c

《数据结构》教材源程序,可以让你轻松的根据教材学习数据结构

/**********************************************/
/*           二叉排序树的插入算法             */
/*   文件名：t_insert.c 函数名：insertbstree()*/
/**********************************************/

void insertbstree(bstree *t,datatype x)
{
  bstree f,p;
  p=*t;
  while (p)   /*查找插入位置*/
      {
       if (x==p->key) return;    /* 若二叉排序树t中已有key，则无需插入 */
       f=p;                      /* f用于保存新结点的最终插入位置 */
       p=(x<p->key)? p->lchild:p->rchild;
      }
  p=(bstree) malloc(sizeof(bsnode));  /*生成待插入的新结点*/
  p->key=x;
  p->lchild=p->rchild=NULL;
  if (*t==NULL)      *t=p;      /*原树为空*/
       else
	  if (x<f->key)
              f->lchild=p;
              else  f->rchild=p;
}