C语言经典算法之二叉排序树 include, C语言, 经典

苹果也疯狂

#include<stdio.h>
#include<stdlib.h>
struct nodb
{
         intdata;
         structnodb *lch,*rch;
};
struct nodb *root,*q,*p;
void insert1(struct nodb *s);
void creat()
{
         structnodb *s;
         inti,n,k;
         printf("n=?");
         scanf("%d",&n);
         for(i=1;i<n;i++)
         {
                   printf("k%d=?",i);
                   scanf("%d",&k);
                   s=(structnodb *)malloc(sizeof(struct nodb));
                   s->data=k;s->lch=NULL;s->rch=NULL;
                   insert1(s);
         }
}
void insert1(struct nodb *s)
{  //非递归插入
         structnodb *p,*q;
         if(root==NULL)
                   root=s;
         else
         {
                   p=root;
                   while(p!=NULL)
                   {
                            q=p;//当p向子数节点移动时，q记录p的双亲的位置
                            if(s->data<p->data)
                                     p=p->lch;
                            else
                                     p=p->rch;
                   }
                   if(s->data<q->data)
                            q->lch=s;
                   else
                            q->rch=s;//当p为空时，q就是可插入的地方
         }
}
void print(struct nodb *t)
{
         if(t!=NULL)
         {
                   print(t->lch);
                   printf("%6d",t->data);
                   print(t->rch);
         }
}
void bstsrch(struct nodb*t,int k)
{
         intflag;
         p=NULL;
         q=t;
         flag=0;
         while((q!=NULL)&&(flag==0))
         {
                   if(q->data==k)
                   {
                            printf("发现%5d",q->data);
                            flag=1;
                   }
                   elseif(k<q->data)
                   {
                            p=q;
                            q=q->lch;
                   }
                   else
                   {
                            p=q;
                            q=q->rch;
                   }
         }
         if(flag==0)printf("没有发现节点");
}
void bstins(struct nodb *t,int k)
{
         structnodb *r;
         bstsrch(root,k);
         if(q==NULL)
         {
                   r=(structnodb*)malloc(sizeof(struct nodb));
                   r->data=k;
                   r->lch=NULL;
                   r->rch=NULL;
                   if(root==NULL)
                            root=r;
                   elseif(k<p->data)
                            p->lch=r;
                   else
                            p->rch=r;
         }
}
main()
{
         intn;
         root=0;
         creat();
         print(root);
         printf("请出入关键值n=?");
         scanf("%d",&n);
         bstsrch(root,n);
         printf("\n");
         bstins(root,n);
         print(root);
}