binarysortinsert.cpp

数据结构c++-书的一些源代码

bsnodetype *BinarySortInsert(bsnodetype *t,keytype key,bsnodetype *p)
/*在以t为根结点的二叉排序树上查找（不存在时插入）关键字为key结点的*/
/*非递归算法*/
{
   bsnodetype *s;

   if(t==NULL)
   {
      t=p;
      return t;
   }

   s=t;
   while(s != NULL)
   {
      /*查找成功*/
      if(s->key == key) s=NULL;

      /*若key在左子树则继续沿lchild链向下查找*/
      else if(key < s->key )
      {
	 if(s->lchild != NULL) s=s->lchild;

        /*未查找到把该结点插入当前结点的左子树*/
	 else
	 {
	    s->lchild = p;
	    s=NULL;
	 }
      }

      /*若key在右子树则继续沿rchild链向下查找*/
      else
      {
	 if(s->rchild != NULL) s=s->rchild;

        /*未查找到把该结点插入当前结点的右子树*/
	 else
	 {
	    s->rchild = p;
	    s=NULL;
	 }
      }
   }
   return t;
}

main()
{
   int Test[15]={381,12,40,190,410,394,540,760,
                  35,476,800,146,9,445,600};
   int i, n=15;
   bsnodetype *t, *p;

   t=NULL;
   for(i=0;i<n;i++)
   {
      p=(bsnodetype *)malloc(sizeof(bsnodetype));
      p->lchild=NULL;
      p->rchild=NULL;
      p->key=Test[i];
      t=BinarySortInsert(t,p->key,p);
   }
   printf("\n");
   InOrder(t);
}

void InOrder(bsnodetype *t)
/*中序遍历打印二叉树*/
{
   if(t==NULL) return ;

   printf("%d   ", t->key);
   if(t->lchild!=NULL) InOrder(t->lchild);
   if(t->rchild!=NULL) InOrder(t->rchild);
}