二叉树.cpp

数值计算程序 包括：变步长梯形公式算法、二叉树算法、二分法、高斯列主消去法、曲线拟合算法等

#include<stdio.h>
#define NULL 0
typedef struct tree
{ int data;
struct tree*lchild;
struct tree*rchild;
}Tree;

void ins_lchild(Tree*p,int x)
{ Tree*q;
if(p==NULL)
printf("插入失败！\n");
else
{ q=(Tree*)malloc(sizeof(Tree));
   q->data=x;
   q->lchild=NULL;
   q->rchild=NULL;
   p->lchild=q;
}
}

void ins_rchild(Tree*p,int x)
{ Tree*q;
if(p==NULL)
printf("插入失败！\n");
else
{ q=(Tree*)malloc(sizeof(Tree));
   q->data=x;
   q->rchild=NULL;
   q->lchild=NULL;
   p->rchild=q;
}
}


void Tree_sturct(Tree*bt)
{ if(bt!=NULL)
{ printf("%d",bt->data);
     if(bt->lchild!=NULL||bt->rchild!=NULL)
      { printf("(");
       Tree_sturct(bt->lchild);
       if(bt->rchild!=NULL)
     printf(",");
       Tree_sturct(bt->rchild);
    printf(")");
      }
}
}


void Fir_print(Tree*bt)
{ if(bt!=NULL)
{ printf("%d ",bt->data);
    Fir_print(bt->lchild);
    Fir_print(bt->rchild);
   }
}


void Mid_print(Tree*bt)
{ if(bt!=NULL)
{ Mid_print(bt->lchild);
    printf("%d ",bt->data);
    Mid_print(bt->rchild);
   }
}


void Beh_print(Tree*bt)
{ if(bt!=NULL)
{ Beh_print(bt->lchild);
    Beh_print(bt->rchild);
    printf("%d ",bt->data);
   }
}

int Tree_hight(Tree*bt)
{ int lchilddep,rchilddep;
if(bt==NULL)
   return 0;
else
   { lchilddep=Tree_hight(bt->lchild);
     rchilddep=Tree_hight(bt->rchild);
    return (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1);
   }
}


int Node_count(Tree*bt)
{ int num1,num2;
if(bt==NULL)
   return 0;
else
   { num1=Node_count(bt->lchild);
     num2=Node_count(bt->rchild);
     return(num1+num2+1);
   }
}
void Postorder(Tree*bt)
{ int flag;
printf("\n请选择你要遍历的方式:\n");
printf(" 1.前序遍历 2.中序遍历 3.后序遍历\n");
   scanf("%d",&flag);
switch(flag)
{ case 1:{printf("前序遍历为:\n");
    Fir_print(bt);
     break;
   }
   case 2:{printf("中序遍历为:\n");
     Mid_print(bt);
     break;
   }
   case 3:{printf("后序遍历为:\n");
     Beh_print(bt);
     break;
   }
default:{ printf("输入不合法，请重新输入!!\n");
     Postorder(bt);
     break;
   }
}
}


Tree *search(Tree *bt,int k)
{Tree *s;
if(bt==NULL)
{printf("未找到");
return(bt);
}
s=bt;
if(s->data==k)
{printf("已找到");
return(s);
}
else
if(s->data>k)
return(search(s->lchild,k));
else
return(search(s->rchild,k));
}


Tree *delete(Tree **e,int k,Tree *s,int n)
{Tree *c,*d,*bt;
Tree **lbt,**rbt;
int m=0;
int g;
bt=*e;
if(bt==NULL)
{printf("删除失败，不存在此数\n");
return(bt);
}

if(bt->data==k)
       {if(bt->lchild==NULL&&bt->rchild==NULL)
       {if(n==0)
        return(-1);
        if(n==1)
        s->lchild=NULL;
        if(n==2)
        s->rchild=NULL;
        free(bt);
        return(s);}
if(bt->lchild==NULL&&bt->rchild!=NULL)
       { if(n==0)
       {*e=bt->rchild;
        free(bt);
     return(s);}
       if(n==1)
       {s->lchild=bt->rchild;
        free(bt);
        return(s);
       }
        if(n==2)
       {s->rchild=bt->rchild;
        free(bt);
        return(s);
       }
       }

if(bt->lchild!=NULL&&bt->rchild==NULL)
        {if(n==0)
        {*e=bt->lchild;
        free(bt);
     return(s);}
        if(n==1)
       {s->lchild=bt->lchild;
        free(bt);
     return(s);
       }
          if(n==2)
       {s->rchild=bt->lchild;
        free(bt);
     return(s);
       }
        }

       if(bt->lchild!=NULL&&bt->rchild!=NULL)
        {if(n==0)
          {d=bt;
         while(d->rchild!=NULL)
         {c=d;
         d=d->rchild;
         g=0;
         if(d->lchild!=NULL)
         {m=1;
          while(d->lchild!=NULL)
         {c=d;
         d=d->lchild;
         g=1;}}
         else
         if(m==0) break;}
         if(g==1)
         c->lchild=NULL;
         if(g==0)
         c->rchild=NULL;
         *e=d;
         d->lchild=bt->lchild;
         if(m==1)
         d->rchild=bt->rchild;
        free(bt);
     return(s);
        }
        if(n==1)
        {d=bt;
         while(d->rchild!=NULL)
         {c=d;
         d=d->rchild;
         g=0;
         if(d->lchild!=NULL)
          {m=1;
          while(d->lchild!=NULL)
         {c=d;
         d=d->lchild;
         g=1;}}
         else
         if(m==0) break;}
         if(g==1)
         c->lchild=NULL;
          if(g==0)
         c->rchild=NULL;
         s->lchild=d;
         d->lchild=bt->lchild;
         if(m==1)
         d->rchild=bt->rchild;
        free(bt);
     return(s);
        }
   if(n==2)
        {d=bt;
        while(bt->lchild!=NULL)
        {c=d;
        d=bt->lchild;
        g=0;
        if(d->rchild!=NULL)
        {m=1;
        while(d->rchild!=NULL)
        {c=d;
         d=d->rchild;
         g=1;}}
         else
         if(m==0) break;}
        if(g==1)
        c->rchild=NULL;
        if(g==0)
        c->lchild=NULL;
        s->rchild=d;
        d->rchild=bt->rchild;
        if(m==1)
        d->lchild=bt->lchild;
         free(bt);
      return(s);
         }
   }}

else
{s=bt;
if(bt->data>k)
{n=1;
lbt=&(bt->lchild);
delete(lbt,k,s,n);
}
else
{n=2;
rbt=&(bt->rchild); 
delete(rbt,k,s,n);
}
}
}

void insert(Tree *bt)
{Tree *p,*q;
int x;
if(bt==NULL)
{printf("输入根结点：\n");
scanf("%d",&x);
p=(Tree*)malloc(sizeof(Tree));
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
   bt=p;
}
printf("输入树中的元素\n");
scanf("%d",&x);
while(x!=0)
{ p=bt;
   q=p;
while(x!=p->data&&q!=NULL)
   { p=q;
   if(x<p->data)
    q=p->lchild;
   else
    q=p->rchild;
   }
if(x==p->data)
   {printf("该元素已插入二叉树中\n");
     return;
   }
else
   if(x<p->data)
    ins_lchild(p,x);
   else
    ins_rchild(p,x);
scanf("%d",&x);
}
   p=bt;
printf("树的结构为:\n");
   Tree_sturct(p);

} 


void choice(Tree *bt)
{ Tree **e;
int flag;
int n,c,h,k;
e=&bt;
printf("\n请选择你要进行的操作:\n");
printf(" 1.退出 2.求树的高度 3.遍历树中元素 4.求结点的个数 5.查找一个数\n");
printf("6.删除一个数 7.插入\n");
    scanf("%d",&flag);
switch(flag)
{ case 1:{ printf("操作结束!");
      break;
   }
   case 2:{ printf("树的高度为:\n");
      h=Tree_hight(bt);
      printf("Height=%d",h);
      choice(bt);
      break;
   }
   case 3:{ Postorder(bt);
      choice(bt);
      break;
   }
   case 4:{ printf("树的结点个数为:\n");
      n=Node_count(bt);
      printf("Node=%d",n);
      choice(bt);
      break;
   }
case 5:{ printf("请输入要查找的数为:\n");
      scanf("%d",&k);
      n=search(bt,k);
      choice(bt);
      break;
   }
case 6:{ printf("请输入要删除的数为:\n");
    scanf("%d",&k);
    n=delete(e,k,NULL,NULL);
    if(n!=-1)
    {printf("此时树的结构为:\n");
           Tree_sturct(bt);}
    else
    {printf("此时树为空:\n");
        bt=NULL;} 
           choice(bt);
    break; 
}
case 7:{ 
      insert(bt);
      choice(bt);
      break;
   }
default:{ printf("输入不合法，请重新输入!!\n");
      choice(bt);
      break;
   }

}

}



void main()
{ Tree*bt,*p,*q;
int x,h;
printf("输入根结点：\n");
scanf("%d",&x);
p=(Tree*)malloc(sizeof(Tree));
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
   bt=p;
printf("输入树中的元素\n");
scanf("%d",&x);
while(x!=0)
{ p=bt;
   q=p;
while(x!=p->data&&q!=NULL)
   { p=q;
   if(x<p->data)
    q=p->lchild;
   else
    q=p->rchild;
   }
if(x==p->data)
   {printf("该元素已插入二叉树中\n");
     return;
   }
else
   if(x<p->data)
    ins_lchild(p,x);
   else
    ins_rchild(p,x);
scanf("%d",&x);
}
   p=bt;
printf("树的结构为:\n");
   Tree_sturct(p);
choice(p);
getch();
clrscr();
}