本程序实现有关二叉树的递归算法，包括

1．求二叉树的层次（高度）

2．求二叉树的叶子个数

3．求二叉树的总结点个数

4．求二叉树的度为1的结点个数

5．求二叉树的度为2的结点个数

6．复制二叉树

7．交换二叉树的左右子树

8．利用先序序列建立二叉链表存储的二叉树

（二）基本要求

1．用二叉链表的形式存储二叉树

2．利用C的图形功能显示二叉树形态 为蓝底白树

#include<stdio.h>        

#include<stdlib.h>
#include<graphics.h>
#include<conio.h>
#include<string.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define NULL 0
typedef int Status;
typedef char TElemType;
typedef struct BiTNode{
 TElemType data;
 struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status CreateBiTree(BiTree *T)         //先序创建二叉树
{ char data;
  scanf("%c",&data);
  if(data=='#') *T=NULL;
  else {
 *T=(BiTree)malloc(sizeof(BiTNode));
 if(!(*T)) exit(OVERFLOW);
 (*T)->data=data;
 CreateBiTree(&(*T)->lchild);
 CreateBiTree(&(*T)->rchild);
       }
    return OK;
}
Status DestroyBiTree(BiTree *T)             //销毁二叉树 释放内存
{  if((*T)->data==NULL)return ERROR;
   free(*T);
   *T=NULL;
   return OK;
}

void Paint(BiTree T,int x,int y,int g)           // 打印二叉树树形（递归实现）
{ char c[2];
  int you=0,zuo=0;
  if(T)
  {setcolor(WHITE);
   circle(x,y,10);
   c[0]=T->data;
   c[1]='\0';
   outtextxy(x,y,c);
   if(T->lchild!=NULL)
   {if(x>g) zuo=(x-g)/2+g;
    if(x<g) zuo=(x-g)/2+x;
    line(x-1,y,zuo,y+80);
   }
   if(T->rchild!=NULL)
   {you=2*x-zuo;
   line(x-1,y,you,y+80);
   }
   Paint(T->lchild,zuo,y+80,x);
   Paint(T->rchild,you,y+80,x);
  }
  
}
int level(BiTree T)                                  //求二叉树的层次（高度）
{
 int l1,l2;
 if(T==NULL) return 0;
 else{l1=level(T->lchild);
      l2=level(T->rchild);
      return l1>l2?l1+1:l2+1;
     }
}

int leaf(BiTree T)                  //求二叉树的叶子节点数
{
 int n1,n2;
 if(T==NULL) return 0;
 else if(T->lchild==NULL&&T->rchild==NULL)return 1;
      else {n1=leaf(T->lchild);
         n2=leaf(T->rchild);
         return n1+n2;
        }
}

int nodes(BiTree T)                    //求二叉树的总节点数
{
 int n1,n2;
 if(T==NULL) return 0;
 else if(T->lchild==NULL&&T->rchild==NULL)return 1;
      else {n1=nodes(T->lchild);
         n2=nodes(T->rchild);
         return n1+n2+1;
        }  
}

int node1(BiTree T)                          //求度为一的节点数目
{
 int n1,n2,n=0;
 if(T==NULL) return 0;
 else { if(T->lchild&&T->rchild==NULL||T->lchild==NULL&&T->rchild)
          n=1;
        n1=node1(T->lchild);
        n2=node1(T->rchild);
        return n1+n2+n;
      }
}

int node2(BiTree T)                     //求度为二的节点数目
{
 int n=0,n1,n2;
 if(T==NULL) return 0;
 else {
      if(T->lchild&&T->rchild) n=1;
      n1=node2(T->lchild);
      n2=node2(T->rchild);
      return n+n1+n2;
      }
}

void Copy(BiTree T,BiTree *T2)                         //复制二叉树
{
 if(T==NULL) *T2=NULL;
 else{*T2=(BiTree)malloc(sizeof(BiTNode));
      (*T2)->data=T->data;
      Copy(T->lchild,&(*T2)->lchild);
      Copy(T->rchild,&(*T2)->rchild);
     }
}

void exchange(BiTree *T)                 //交换二叉树的所有左右子树
{
 BiTNode *t;
 if(*T)
 {t=(*T)->lchild;
  (*T)->lchild=(*T)->rchild;
  (*T)->rchild=t;
  exchange(&(*T)->lchild);
  exchange(&(*T)->rchild);
 }
}

main()
{
BiTree T,T2;  int x,y,g;
int gdriver,gmode;
int d,yezi,jiedian,dian1,dian2;
x=320;y=30;  g=0;
gdriver=DETECT;

printf("input the BiTree's data(in PreOrder and <=63ge):\n");             //创建
if(!CreateBiTree(&T))printf("kongjian OVERFLOW! can not create!\n");
else printf("cunchu success!\n");
printf("press any key to contunue:\n");
getch();

printf("level of the tree is :\n");                  //求层数
d=level(T);
printf("%d\n",d);
printf("\n press any key to continue:\n");
getch();

printf("leaf number of the tree is :\n");                 //求叶子
yezi=leaf(T);
printf("%d\n",yezi);
printf("\n press any key to continue:\n");
getch();

printf("nodes number of the tree is :\n");                 //求总节点
jiedian=nodes(T);
printf("%d\n",jiedian);
printf("\n press any key to continue:\n");
getch();

printf("du wei 1 d jiedian node1 of the tree is :\n");            //求度为一的节点数     
dian1=node1(T);
printf("%d\n",dian1);
printf("\n press any key to continue:\n");
getch();

printf("node2 of the tree is :\n");                 //求度为二的节点
dian2=node2(T);
printf("%d\n",dian2);
printf("\n press any key to continue:\n");
getch();

printf("Now copy the tree:\n");                 //复制树
Copy(T,&T2);
printf("\n press any key to continue:\n");
getch();
printf("now,print the BiTree like a tree:\n");           //打印树
printf("press any key to see the tree:\n");
getch();
initgraph(&gdriver,&gmode,"C:\\TC");
setbkcolor(BLUE);
cleardevice();
Paint(T,x,y,g);
getch();
closegraph();
printf("press any key to continue:\n");
getch();

printf("Now change the tree d right and left:\n");           //交换左右子树
exchange(&T);
printf("\n press any key to continue:\n");
getch();
printf("now,print the BiTree like a tree:\n");
printf("press any key to see the tree:\n");              //打印树形以确认交换
getch();
initgraph(&gdriver,&gmode,"C:\\TC");
setbkcolor(BLUE);
cleardevice();
Paint(T,x,y,g);
getch();
closegraph();
printf("press any key to continue:\n");
getch();
if(DestroyBiTree(&T))printf("the BiTree destroyed!\n");        //销毁树
else printf("NULL!can not destroy!\n");
printf("press any key to continue:\n");                //结束程序
getch();

}