erchashu.c

数据结构基础学习程序

#include<stdio.h>       //haoshi de tongji ercha shu de gao du
#define max 20        //erchashu zhongde zui duo jiedianshu
typedef struct node     //ding yi erchashu de jiedian leixing
{
char data;
struct node *lchild,*rchild;
}bitree;

bitree *cre_tree(char *str,int i,int m)   //ercha shu ianli zihanshu
{bitree *p;           //wuxiao de jiedian
if(i>=m)
return NULL;
p=(bitree *)malloc(sizeof(bitree));      //shengcheng xin de jiedian
p->data=str[i];               //jiang zifhuchuan de di i ge zufu fugei xin de shuju yu
p->lchild=cre_tree(str,2*i+1,m);   //chuang jian xin jiedian de zuo zi shu
p->rchild=cre_tree(str,2*i+2,m);   //chuang jian xin jiedian de you zishu
return p;
}

bitree *swap(bitree *p) //jiang zhizhen zhixiang de erchashu zhong de zuo you haizi huhuan
{
 bitree *stack[max];  //stack wei zhizhen leixing de duizhan
 int k;
 k=0;
 stack[k]=NULL; //jiaohuan p jiedian de zuo you haizi
 if(p!=NULL)
 {
 stack[++k]=p->lchild;
 p->lchild=p->rchild;
 p->rchild=stack[k];
 p->lchild=swap(p->lchild);   //jiang p jiedian zuo zishu zhong de zuoyou haizi huhuan
 p->rchild=swap(p->rchild); //jiangp jie dian youzishu zhong de zuoyou haizi huhuan
 }
 return p;
}

void preorder(bitree *t)     //qianxu bianli erchashu
{
 if(t!=NULL)
 {
 printf("%c",t->data);
 if(t->lchild)
 {
 printf("->");
 preorder(t->lchild);
 }
 if(t->rchild)
 {
  printf("->");
  preorder(t->rchild);
  }
 }
}

void inorder(bitree *t)  //zhong xu bianli erchashu
{
 if(t!=NULL)
 {
  inorder(t->lchild);
  printf("%c",t->data);
  printf("->");
  inorder(t->rchild);
  }
}

void lev_order(bitree *t,int m)   //an ceng bianli erchashu
{
 bitree *queue[max];
 bitree *p;
 int front=0,rear=0;
 queue[rear++]=t;
 while(front!=rear)
 {
  p=queue[front];
  front=(front+1)%m;
  printf("%c",p->data);  //shuchu genjiedian de zhi
  printf("->");
  if(p->lchild!=NULL)  //bianli zuo zishu
 {
    if((rear+1)%m!=front)
    {
     queue[rear]=p->lchild;
     rear=(rear+1)%m;
     }
 }
 if(p->rchild!=NULL)   //bianli youzi shu
 {
  if((rear+1)%m!=front)
  {
   queue[rear]=p->rchild;
   rear=(rear+1)%m;
   }
  }
 }
}


int treehigh(t)     //ji suan erchashu de gaodu zihanshu
bitree *t;        //keyi zai ci chu ding yi qunju bian liang de ****
{int lh,rh,h;
if(t==NULL)
h=0;
else
{
 lh=treehigh(t->lchild); //tongji zuo zishu jidian geshu
 rh=treehigh(t->rchild); //tongji you jiedian geshu
 h=(lh>rh ? lh:rh)+1;
}
return(h);
}


//zhuhanshu
void main()
{
int i, n,y;
char str[max];       //str wei zifuxing shuzu
bitree *root;        //root wei zhixiang erchashu de gejiedian de zhizhen
clrscr();            //zai vc++ zhong buxu yao
printf("please input node num:\n");
scanf("%d",&n);
getchar();          //jiang de dao de shu shuchu xian shi jinguan bianyi hui tishi Code ha no effct keshi haishi buneng qu diao ,buran jieguo cuowu
printf("please input a string which lenghth is %d:",n);

for(i=0;i<n;i++)    //kaishi shuru zi fuchuan
str[i]=getchar();

printf( "\n\n");
root=cre_tree(str,0,n);  //chuangjian yike root gen zhixiang de erchashu
y=treehigh(root);      //diao yong tongji gaodu zi hanshu
printf("height is :%d\n",y);   //shu chu gao du
printf("%c\n\n",root->data);   //shuchu gen jiedian de zhi

printf("lev_order before swaping:");
lev_order(root,n); //an ceng bianli jiaohuan qian de erchashu

printf("\n");
printf("preorder before swaping:");
preorder(root);    //qianxu bianli erchashu

printf("\n");
printf("inorder before swaping:");
inorder(root);

printf("\n\n");
root=swap(root);

printf("lev_order afrer swaping:");
lev_order(root,n);

printf("\n");
printf("preorder after swaping:");
preorder(root);

printf("\n");
printf("inorder after swaping:");
inorder(root);
}
    //bei wang: jiedianleingzhong :btnode->node
    // bttree->bitee;
    //shurushi:abcdef@   @ bunengshao fouze jieguo cuowu