电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: C语言经典算法之二叉排序树 [打印本页]

作者: 苹果也疯狂 时间: 2014-5-22 09:43 标题: 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);
}

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)