二叉樹的創(chuàng)建和操作

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100

typedef struct node{
 char data; /*此例中二叉樹的結(jié)點(diǎn)采用字符類型*/
 struct node *lchild,*rchild;
}NODE;
/*按先序遍歷序列創(chuàng)建二叉樹的二叉鏈表*/
NODE *crt_bt_pre(){  
 NODE *bt;
 char ch;
 flushall();
 scanf("%c",&ch);
 if(ch == '0')
  bt = NULL;
 else{
  bt = new NODE;
  bt -> data = ch;
  printf("\n\t請(qǐng)輸入%c結(jié)點(diǎn)的左孩子：",bt -> data);
  bt -> lchild = crt_bt_pre();
  printf("\n\t請(qǐng)輸入%c結(jié)點(diǎn)的右孩子:",bt -> data);
  bt -> rchild = crt_bt_pre();
 }
 return bt;
}
/*先序遍歷二叉樹*/
void Preorder(NODE *bt){
 if (bt != NULL){
  printf("%c",bt -> data);
  Preorder(bt -> lchild);
  Preorder(bt -> rchild);
 }
}
/*中序遍歷二叉樹*/
void Inorder(NODE *bt){
 if (bt != NULL){
  Inorder(bt -> lchild);
  printf("%c",bt -> data);
  Inorder(bt -> rchild);
 }
}
//后序遍歷二叉樹
void Postorder(NODE *bt){
 if (bt != NULL){
  Postorder(bt -> lchild);
  Postorder(bt -> rchild);
  printf("%c",bt -> data);
 }
}
/*統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)*/
int CountLeaf(NODE *bt){
 static int count;
 if(bt == NULL)
  return 0;
 else{
  if(bt -> lchild == NULL && bt -> rchild == NULL)
   count++;
  else{
   CountLeaf(bt -> lchild);
   CountLeaf(bt -> rchild);
  }
  return(count);
 }
}
/*統(tǒng)計(jì)二叉樹中根結(jié)點(diǎn)的總數(shù)*/
int CountNode(NODE *bt){
 static int count;
 if(bt == NULL)
  return 0;
 else{
  count++;
  CountNode(bt -> lchild);
  CountNode(bt -> rchild);
  return(count);
 }
}
/*求二叉樹的深度*/
int TreeDepth(NODE *bt){
 int ldep,rdep;
 if(bt == NULL)
  return 0;
 else{
  ldep = TreeDepth(bt -> lchild);
  rdep = TreeDepth(bt -> rchild);
  if(ldep > rdep)
   return(ldep+1);
  else
   return(rdep+1);     //有錯(cuò)誤
 }
}
//求二叉樹的寬度
int TreeWidth(NODE *b)
{
 struct 
 {
  int lno;
  NODE*p;     //節(jié)點(diǎn)指針
 }Qu[MaxSize];   //定義順序非循環(huán)隊(duì)列
 int front,rear;
 int lnum,max,i,n;
  front=rear=0;     //置隊(duì)列為空隊(duì)
 if (b!=NULL)
 {
  rear++;
  Qu[rear].p=b;   //根節(jié)點(diǎn)指針入隊(duì)
  Qu[rear].lno=1; //根節(jié)點(diǎn)的層次編號(hào)為1
  while (rear!=front) //次循環(huán)通過層次遍歷求每個(gè)節(jié)點(diǎn)的層次
  {
   front++;
   b=Qu[front].p;  //對(duì)頭出對(duì)
   lnum=Qu[front].lno;
   if (b->lchild!=NULL) //左孩子入隊(duì)
   {
    rear++;
    Qu[rear].p=b->lchild;
    Qu[rear].lno=lnum+1;
   }
   if (b->rchild!=NULL)  //右孩子入隊(duì)
   {
    rear++;
    Qu[rear].p=b->rchild;
    Qu[rear].lno=lnum+1;
   }
  }
  max=0;lnum=1;i=1;  //lnum從第一層開始
  while (i<=rear)    //通過比較相同層次的結(jié)點(diǎn)數(shù)求樹的寬度
  {
        n=0;
   while (i<=rear&&Qu[i].lno==lnum)
   {
    n++;
    i++;
   }
   lnum=Qu[i].lno;
   if (n>max)
   {
    max=n;
   }
  }
  return max;
 }
 else
  return 0;
}
//int system(const char *string); //自動(dòng)清屏代碼
//char Check()
//{
// printf("是否清屏：Y|N");
// char a;
// scanf("%c",&a);
// if (a=='y'||a=='Y')
// {
//  return a;
// }
// else
//  return 'N';
//}
//void clear()
//{
// printf("是否清屏（Y|N）:");
// char a;
// scanf("%c",&a);
// if (a=='y'||a=='Y')
// {
//  system("pause");
//  system("cls");
// }
//}
//菜單函數(shù)
void shoumenu(){
 printf("\n\n\n");
 printf("  --二叉樹的基本運(yùn)算--\n");
 printf("*****************************************\n");
 printf("*  1------建二叉樹         *\n");
 printf("*  2------先序遍歷         *\n");
 printf("*  3------中序遍歷         *\n");
 printf("*  4------后序遍歷         *\n");
 printf("*  5------統(tǒng)計(jì)葉子數(shù)       *\n");
 printf("*  6------統(tǒng)計(jì)結(jié)點(diǎn)數(shù)       *\n");
 printf("*  7------求二叉樹深度     *\n");
 printf("*  8------求二叉樹寬度     *\n");
 printf("*                                       *\n");
 printf("*  0------退出             *\n");
 printf("*****************************************\n");
 printf("請(qǐng)選擇菜單號(hào)(0--8):");
}
//選擇功能函數(shù)
void binaryOP(){
 NODE *bt = NULL;
 int count = 0;
 char choice = 'N';
 int x;
 while(choice != '0'){
  
  shoumenu();
  flushall();
  scanf("%c",&choice);
  switch(choice){
  case '1':
   printf("\n\t請(qǐng)輸入按先序建立二叉樹的結(jié)點(diǎn)序列：");
   printf("\n\t 說明：逐個(gè)輸入，'0'代表后繼結(jié)點(diǎn)為空，按回車輸入下一個(gè)結(jié)點(diǎn)");
   printf("\n\t請(qǐng)輸入根結(jié)點(diǎn)：");
   bt = crt_bt_pre();/*調(diào)用創(chuàng)建二叉樹的函數(shù)*/
   printf("\n\t二叉樹成功建立！\n");
   //clear();
   break;

  case '2':
   if (bt == NULL){
    printf("\n\t空樹");
   }
   else{
    printf("\n\t該二叉樹的先序遍歷的序列為：");
    Preorder(bt);/*調(diào)用先序遍歷函數(shù)*/
   }
   printf("\n");
   //clear();
   break;

  case '3':
   if (bt == NULL){
    printf("\n\t空樹");
   }
   else{
    printf("\n\t該二叉樹的中序遍歷序列：");
    Inorder(bt);/*調(diào)用中序遍歷函數(shù)*/
   }
   printf("\n");
   //clear();
   break;

  case '4':
   if (bt == NULL){
    printf("\n\t空樹");
   }
   else{
    printf("\n\t該二叉樹的后序遍歷序列為：");
    Postorder(bt);/*調(diào)用后序遍歷函數(shù)*/
   }
   printf("\n");
   //clear();
   break;

  case '5':
   count = CountLeaf(bt);/*調(diào)用統(tǒng)計(jì)葉子結(jié)點(diǎn)個(gè)數(shù)的函數(shù)*/
   printf("\n\t該二叉樹有%d個(gè)葉子結(jié)點(diǎn)。\n",count);
   printf("\n");
   //clear();
   break;

  case '6':
   count = CountNode(bt);/*調(diào)用統(tǒng)計(jì)結(jié)點(diǎn)總數(shù)的函數(shù)*/
   printf("\n\t該二叉樹共有%d個(gè)結(jié)點(diǎn) \n",count);
   printf("\n");
   //clear();
   break;

  case '7':
   x = TreeDepth(bt);/*調(diào)用求二叉樹深度的函數(shù)*/
   printf("\n\t 該二叉樹的深度為%d",x);
   printf("\n");
   //clear();
   break;
  case'8':
   int n;
   n=TreeWidth(bt);
   printf("\n\t 該二叉樹的寬度為%d\n",n);
   //clear();
   break;

  case '0':
   printf("\n\t 程序結(jié)束!\n");
   printf("\n");
   //clear();
   break;

  default :
   printf("\n\t輸入有誤，請(qǐng)重新輸入!\n");
   printf("\n");
   //clear();
  }
 }
}

void main()
{
 binaryOP();
}