sy8_2.c

数据结构实验与学习指导

/*  sy8_2.c */
#include "stdio.h"
#include "alloc.h"
#define MAXSIZE 11
typedef struct BTnode
  { int key;
    struct BTnode *lchild,*rchild;
  }BTNode;/*定义二叉树的存储结构*/
 BTNode *f;   /*当前结点的前驱*/
BTNode *BST_Search(BTNode *t,int K)/*二叉排序树的查找*/
{  BTNode *p=t; /*t为根结点*/
   f=NULL;
   while(p!=NULL)
   { if(K==p->key)
     { printf("查找成功K=%d\n",K);
       return p;
      }  /*查找结束*/
     else
       if(K<p->key)
        { f=p;p=p->lchild; }/*在左子树上查找*/
       else
        { f=p; p=p->rchild;} /*在右子树上查找*/
    }
   printf("查找失败!插入%d\n",K);   /*未找到，插入*/
   return NULL;
}
BTNode *BST_Insert(BTNode *t,int K)/*在二叉排序树上执行插入操作*/
{ BTNode *s,*p;
  p=BST_Search(t,K);/*判断树中是否存在值为K的结点*/
  if(p==NULL)
  { s=(BTNode *)malloc(sizeof(BTNode));/*申请结点空间*/
    s->key=K;
    s->lchild=s->rchild=NULL;   /*结点赋值*/
    if(t==NULL)
     t=s;       /*生成根结点*/
    else
      if(K<f->key)
        f->lchild=s;  /*生成左孩子*/
    else
        f->rchild=s; /*生成右孩子*/
    }
  return t;
  }
 void InOrder(BTNode *t)  /*中序遍历*/
 {
   if (t)
   { InOrder(t->lchild);
     printf("%d  ",t->key);
     InOrder(t->rchild);
   }
 }
void main()
{ int i,k;
  BTNode *t;
  t=(BTNode*)malloc(sizeof(BTNode));
  t=NULL;
  printf("请输入%d个数\n",MAXSIZE);
  for(i=0;i<MAXSIZE;i++)   /*输入K值，查找过程创建二叉排序树*/
  { printf("请输入K:");
    scanf("%d",&k);
    t=BST_Insert(t,k); }
    printf("\n这个查找树的中序遍历结果是:\n");
    InOrder(t);
   getch();
 }