二叉樹的實驗操作：
題目如下：
1．設某二叉樹的結點類型為整數類型，以二叉鏈表形式作為存儲結構。試編程實現：
(1) 生成一棵二叉樹.
(2) 用遞歸算法、非遞歸算法實現二叉樹的遍歷；
(3) 求度分別為0、1、2的結點的數目,分別用遞歸算法、非遞歸算法實現；
(4) 按層次遍歷二叉樹(提示：使用一個隊列實現）；
*(5) 求二叉樹的高度(深度)；
*(6) 判斷是否為完全二叉樹，輸出"Yes!"/"No!"；
*(7) 交換每個結點的左右子樹；
*(8) 對交換左右子樹后的二叉樹作中序遍歷。


#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#define ERROR  0
#define OK  1
#define OVERFLOW -2
#define queuesize 20
typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild; //左右孩子指針
}BiTNode,*BiTree;
typedef struct Queue{
    int front ,rear ;
     BiTree data[queuesize]; //循環隊列元素類型為二叉鏈表結點指針
     int count;
}Queue; //循環隊列結構定義

int CreateBiTree(BiTree * T) { //聲明的就是一個BiTree類型的指針,通過修改來對main中的T做修改，然后使其指向根結點
  // 按先序次序輸入二叉樹中結點的值（一個字符），空格字符表示空樹，
  // 構造二叉鏈表表示的二叉樹T。
  int ch;
  printf("請輸入一個根結點的值（如果為空，則輸入0）\n");
  scanf("%d",&ch);
  if (ch==0) (*T)= NULL;
  else {
    if (!(*T = (BiTNode *)malloc(sizeof(BiTNode))))  return ERROR;
    (*T)->data = ch;              // 生成根結點
    CreateBiTree(&(*T)->lchild);   // 構造左子樹
    CreateBiTree(&(*T)->rchild);   // 構造右子樹
  }
  return OK;
} // CreateBiTree

int PreOrderTraverse(BiTree T) //用遞歸算法寫的遍歷函數，按照先序遍歷，同時輸出結點的值
{
    if(T!=NULL)
    {
        printf("%d  ",T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
    return OK;
}

int InorderTraverse(BiTree T)
{
    if(T!=NULL)
    {
        InorderTraverse(T->lchild);
        printf("%d ",T->data);
        InorderTraverse(T->rchild);
    }
    return OK;
}
int PreOrderTraverse2(BiTree T)  //用非遞歸的算法寫的遍歷函數，按照先序遍歷，同時輸出結點的值
{
   BiTree p,s[20];
   int top=0;
   p=T;
   while((p!=NULL)||(top>0))
   {
       while(p!=NULL)
       {
           printf("%d ",p->data);
           s[++top]=p;
           p=p->lchild;
       }
       p=s[top--];
       p=p->rchild;
   }
   return OK;
}

int get_all_node(BiTree T)  //求出總的結點的個數
{
   BiTree p,s[20];
   int num_node=0;
   int top=0;
   p=T;
   while((p!=NULL)||(top>0))
   {
       while(p!=NULL)
       {
           num_node++;
           s[++top]=p;
           p=p->lchild;
       }
       p=s[top--];
       p=p->rchild;
   }
   return num_node;
}

int get_node0_1(BiTree T)//利用遞歸算法得到度為0的結點的個數
{
    int num1,num2;
    if(T==NULL)
        return 0;
    else
    {
        if((T->lchild==NULL)&&(T->rchild==NULL))
            return 1;
        else
        {
            num1=get_node0_1(T->lchild);
            num2=get_node0_1(T->rchild);
            return (num1+num2);
        }
    }
}
int get_node0_2(BiTree T) //利用非遞歸算法得到度為0的結點
{
    int num=0;
    BiTree p=T,s[20];
    int top=0;      //定義一個棧
    while((p!=NULL)||(top>0))
    {
        while(p!=NULL)
        {
            s[++top]=p;
            p=p->lchild;
        }
    
        {    p=s[--top];
        if(p->rchild==NULL)
        {
            ++num;
        }
        else
            p=p->rchild;
        }
    }
    return num;

}

int get_node1(BiTree T) //利用總的關系求出度為1的結點的個數
{
    int num=get_all_node(T)-2*get_node0_1(T)+1;
    return num;
}
int get_node1_1(BiTree T)   //非遞歸算法，同時利用關系求度為1的結點。
{
    int num=get_all_node(T)-2*get_node0_2(T)+1;
    return num;
}
int get_node2(BiTree T) //利用度為2的結點個數與度為0的結點個數的關系得到
{
    int num=get_node0_1(T)-1;
    return num;
}
int get_node2_1(BiTree T)   //非遞歸算法，同時利用關系求度為2的結點。
{
    int num=get_node0_2(T)-1;
    return num;
}
int get_node(BiTree T)
{
    int get;
   printf("請輸入你要查找的結點的度\n");
   printf("1.查詢度為0的所有結點的個數\n");
   printf("2.查詢度為1的所有結點的個數\n");
   printf("3.查詢度為2的所有結點的個數\n");
   scanf("%d",&get);
   switch(get){
   case 1:
      printf("度為0的所有結點的個數是%d\n",get_node0_1(T));
      break;
   case 2:
       printf("度為1的所有結點的個數是%d\n",get_node1(T));
       break;
   case 3:
       printf("度為2的所有結點的個數是%d\n",get_node2(T));
       break;
   }
   return OK;
}
int get_node_1(BiTree T)        //利用非遞歸算法的實現
{
    int get;
    printf("下面是用非遞歸算法來查詢\n");
   printf("請輸入你要查找的結點的度\n");
   printf("1.查詢度為0的所有結點的個數\n");
   printf("2.查詢度為1的所有結點的個數\n");
   printf("3.查詢度為2的所有結點的個數\n");
   scanf("%d",&get);
   switch(get){
   case 1:
      printf("度為0的所有結點的個數是%d\n",get_node0_2(T));
      break;
   case 2:
       printf("度為1的所有結點的個數是%d\n",get_node1_1(T));
       break;
   case 3:
       printf("度為2的所有結點的個數是%d\n",get_node2_1(T));
       break;
   }
   return OK;
}
int LevelOrder(BiTree T)
{    Queue *q;
     BiTree p;
     int flag=0;                      //定義flag為層號
     q=(Queue *)malloc(sizeof(Queue));  //申請循環隊列空間
     q->rear=q->front=q->count=0;      //將循環隊列初始化為空
     q->data[q->rear]=T;
     q->count++;
     q->rear=(q->rear+1)%queuesize;       //將根結點入隊
     while (q->count)                   //若隊列不為空，做以下操作
         if(q->data[q->front]){            //當隊首元素不為空指針，做以下操作
             p=q->data[q->front];           //取隊首元素*p
             printf("%d ",p->data);        //打印*p結點的數據域信息
             ++flag;
             q->front=(q->front+1)%queuesize;
             q->count--;       //隊首元素出隊
             if (q->count==queuesize)//若隊列為隊滿，則打印隊滿信息，退出程序的執行
                 printf("the queue full!\n");
             else{            //若隊列不滿，將*p結點的左孩子指針入隊
                 q->count++;q->data[q->rear]=p->lchild;
                 q->rear=(q->rear+1)%queuesize;
             }                        //enf of if
             if (q->count==queuesize)        //若隊列為隊滿，則打印隊滿信息，退出程序的執行
                 printf("the queue full!\n");
             else{                      //若隊列不滿，將*p結點的右孩子指針入隊
                 q->count++;q->data[q->rear]=p->rchild;
                 q->rear=(q->rear+1)%queuesize;
             }                              //end of if
         }                                //end of if
         else{                          //當隊首元素為空指針，將空指針出隊
             q->front=(q->front+1)%queuesize;
             q->count--;
         }
         printf("\n");
         return OK;
}      //end of LevelOrder

int height(BiTree T)
{
    BiTree p=T;
    int a,b;
    if(p==NULL)
        return 0;
    else{
       if((p->lchild==NULL)&&(p->rchild==NULL))
            return 1;
    else{
          a=height(p->rchild);
          b=height(p->lchild);
          if(a>b)   return (a+1);
          else    return (b+1);
          }
    }
}

int judge(BiTree T)   //采用遞歸算法來實現判斷是否為完全二叉樹
{
      if(T ==NULL) 
          return   0; 
      if(T->lchild == NULL && T->rchild== NULL) 
          return   1;  
      if(T->lchild  == NULL  && T->rchild != NULL||T->lchild!=NULL &&T->rchild==NULL) 
          return   0; 
      return   judge(T->lchild) & judge(T->rchild); 

}

int exchange(BiTree T)
{
     BiTree p=T;
     int exch;
     if(p==NULL)
         return OK;
     else
     {
         if(p->lchild!=NULL && p->rchild!=NULL)
         {
             exch=p->lchild->data;
             p->lchild->data=p->rchild->data;
             p->rchild->data=exch;
             exchange(p->lchild);
             exchange(p->rchild);
         }
         else
         {
             if(p->lchild==NULL)
                 exchange(p->rchild);
             else
                 exchange(p->lchild);
         }
         return OK;
     }
}

void main()
{
    BiTree T;         //定義一個指向BiTNode結點的指針
    int choice;
    do{
    printf("\n");
    printf("請選擇操作：\n");
    printf("1.按照先序的次序生成一顆二叉樹\n");
    printf("2.遞歸算法實現二叉樹的先序遍歷，輸出各結點值\n");
    printf("3.用非遞歸算法實現二叉樹的遍歷，輸出各結點值\n");
    printf("4.求度分別為0、1、2的結點的數目（遞歸算法實現）\n");
    printf("5.求度分別為0、1、2的結點的數目（非遞歸算法實現）\n");
    printf("6.按層次遍歷二叉樹\n");
    printf("7.求二叉樹的高度(深度)\n");
    printf("8.判斷是否為完全二叉樹，輸出\"Yes!\"或\"No!\"\n");
    printf("9.交換每個結點的左右子樹\n");
    printf("10.對交換左右子樹后的二叉樹作中序遍歷\n");
    printf("11.退出\n");
    scanf("%d",&choice);
    switch(choice){
    case 1:
        CreateBiTree(&T);   //創建二叉樹
        break;
    case 2:
        PreOrderTraverse(T); //利用遞歸算法的先序遍歷，輸出結點值
        break;
    case 3:
        PreOrderTraverse2(T);//利用非遞歸算法的先序遍歷，輸出結點值
        break;
    case 4:
        get_node(T); //利用遞歸算法得到的各個結點的個數
        break;
    case 5:
        get_node_1(T);  //利用非遞歸算法得到的各個結點的個數
        break;
    case 6:
        LevelOrder(T);
        break;
    case 7:
        printf("二叉樹的高度為%d\n",height(T));
        break;
    case 8:
        if(judge(T)==0)
            printf("No\n");
        else
            printf("Yes\n");
        break;
    case 9:
         exchange(T);
         break;
    case 10:
         InorderTraverse(T);
         break;
    }   
    }while(choice!=11);   
}