binary-tree.cpp

c语言描述的数据结构

     #include <string.h>
     #include <stdio.h>
     #include <malloc.h>
 #define  Maxsize  100
/* 定义DataType为char类型 */
typedef char DataType;
/* 二叉树的结点类型 */
typedef struct BitNode
{DataType data;
struct BitNode *lchild,*rchild;
}BitNode,*BitTree;


/* 初始化二叉树，即把树根指针置空 */
BitTree BinTreeInit();


/* 按先序次序建立一个二叉树*/
BitTree BinTreeCreat(BitTree &t);


/* 检查二叉树是否为空 */
int BinTreeEmpty(BitTree t);


/* 按任一种遍历次序（包括按先序、中序、后序、按层次）输出二叉树中的所有结点 */
void BinTraverse(BitTree t);

 void PreOrder(BitTree t);
 
 void PostOrder(BitTree t);
   

 void InOrder(BitTree t);
   
 void levelOrder(BitTree t);
   
 
/* 求二叉树的深度 */
int BinTreeDepth(BitTree t);


/* 求二叉树中所有结点数 */
int BinTreeCount(BitTree t);


/* 清除二叉树，使之变为空树 */
void BinTreeClear(BitTree &t);


void  print(BitTree t);




   main()
    {
     BitTree t;
     int choice,tip,i,x,j,count;
     do
     {
      printf("%15s%15s%15s%15s%15s%15s%15s%15s","\n\n\n\n\n\n","\t1:初始化二叉树\n","\t2:建立二叉树\n","\t3:二叉树判空\n","\t4:遍历二叉树\n",
      "\t5:求二叉树的深度\n", "\t6:求二叉树的所有结点数\n","\t7清空二叉树\n");
      printf("Your choice:");
      scanf("%d",&choice);
      switch(choice)
      {
       case 1: t=BinTreeInit();
       break;
      case 2:{printf("Please input element of Push:");BinTreeCreat(t);}
       break;
       case 3: i=BinTreeEmpty(t);
             if(i==1)
               printf("The BinTree is Empty!");
             else printf("The BinTree is not Empty!");
       break;
      case 4: BinTraverse(t);
       break;
      case 5: {j=BinTreeDepth(t); printf("Depth=%d",j);}
       break;
      case 6: {count=BinTreeCount(t); printf("Number of nodes is:%d",count);}
       break;
      case 7: BinTreeClear(t);
       break;
      default:printf("\nWrong select!Try again!");
     }
    }while(choice>0||choice<8);
    }





  /* 初始化二叉树，即把树根指针置空 */
  BitTree BinTreeInit()
  {
   BitTree t=NULL;
   return t;
  }
  
  
  
     /*按先序次序建立一个二叉树
 BitTree BinTreeCreat(BitTree &t)
   { char ch;
     BitTree p;
     p=(BitTree)malloc(sizeof(BitNode));
     if(!p)
      {
       printf("OverFlow!");
       exit(0);
      }
     //ch=getchar();
     scanf("%c\n",&ch);
     ch=getchar();
     if(ch!='#')
     {
      t=p;
      t->data=ch;
      BinTreeCreat(t->lchild);
      BinTreeCreat(t->rchild);
     }//if
   return t;
   }   /*creat*/
   
   

  /*按先序次序建立一个二叉树*/
  BitTree BinTreeCreat(BitTree &t)
{
 char ch;
 scanf("%c",&ch);
 ch=getchar();
 if(ch==' ') t=NULL;
 else
 {
  if(!(t=(BitTree)malloc(sizeof(BitNode))))
    exit(0);
  t->data=ch;
  BinTreeCreat(t->lchild);
  BinTreeCreat(t->rchild);
 }
  return t;
}

   
   
    /* 检查二叉树是否为空 */
int BinTreeEmpty(BitTree t)
{
 return(t==NULL);
}



/* 按任一种遍历次序（包括按先序、中序、后序、按层次）输出二叉树中的所有结点 */
void BinTraverse(BitTree t)
{
 int tip;
  printf("%15s%15s%15s%15s%15s","\n\n\n\n","\t1:先序遍历二叉树\n","\t2:中序遍历二叉树\n","\t3:后序遍历二叉树\n","\t4:层次遍历二叉树\n");
  scanf("%d",&tip);
  switch(tip)
 { case 1:PreOrder(t);
  break;
  case 2:InOrder(t);
   break;
  case 3:PostOrder(t);
   break;
  case 4:levelOrder(t);
 }
}

 //先序
 void PreOrder(BitTree t)
 {
  if(t)
  {
   print( t);
   PreOrder(t->lchild);
   PreOrder(t->rchild);
  }  //it
 }
 
 
 //中序
 void InOrder(BitTree t)
 {
  if(t)
  {
   InOrder(t->lchild);
   print(t);
   InOrder(t->rchild);

  }
 }
 
 
 //后序
 void PostOrder(BitTree t)
 {
  if(t)
  {
   PostOrder(t->lchild);
   PostOrder(t->rchild);
   print(t);
  }//if
 }



 void print(BitTree t)
 {
  printf("%5c",t->data);
 }
 
 
 
 void levelOrder(BitTree t)
 {
  BitTree Q[Maxsize];
  int r=0;
  int f=0;
  r=(r+1)%Maxsize;
  Q[r]=t;
  while(Q)
  {
   f=(f+1)%Maxsize;
   t=Q[f];
   printf("%5c",t->data);
   if(t->lchild)
    {
     r=(r+1)%Maxsize;
     Q[r]=t->lchild;
    }
   if(t->rchild)
   {
    r=(r+1)%Maxsize;
    Q[r]=t->rchild;
   }
  }

 }
 
 
 
 /* 求二叉树的深度 */
int BinTreeDepth(BitTree t)
{
 int dep1,dep2;
 if(t==NULL)
  return 0;
 else
  {
   dep1=BinTreeDepth(t->lchild);
   dep2=BinTreeDepth(t->rchild);
   return(dep1>dep2?dep1+1:dep2+1);
  }

}
 
 
 
 
 /* 求二叉树中所有结点数 */
int BinTreeCount(BitTree t)
{
 int num1,num2;
 if(t==NULL)
  return 0;
 else
  if(!t->lchild&&!t->rchild)
   return 1;
  else
   {
    num1= BinTreeCount(t->lchild);
    num2= BinTreeCount(t->rchild);
    return(num1+num2+1);
   }

}


void BinTreeClear(BitTree &t)
{  t=NULL;
}