binarysortdelete.cpp

包含各种测试,查找和算法等代码,如冒泡算法,树的遍历,链表,队列,堆栈等

#include <stdio.h>

typedef int keytype;

typedef struct BSNode
{
   keytype key;
   struct BSNode *lchild, *rchild;
} bsnodetype;

bsnodetype *BinarySortInsert(bsnodetype *t,keytype key,bsnodetype *p);
bsnodetype *BinarySortDelete(bsnodetype *t,bsnodetype *p,bsnodetype *q);
InOrder(bsnodetype *t);

main()
{
   int Test[15]={190,381,12,40,410,394,540,760,
                  35,476,800,146,9,445,600};
   int i, n=15;
   keytype key=394;
   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);
}

bsnodetype *BinarySortDelete(bsnodetype *t, elemtype Item)
/**/
{
   bsnodetype *DNodePtr, PNodePtr, RNodePtr;
   if((DNodePtr = BinarySortSeach(t,Item,PNodePtr)) == NULL)
      return;

   else if(DNodePtr->lchild ==NULL)
      RNodePtr = DNodePtr->rchild;


}

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;
}

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);
}