binarytree.cpp

数据结构综合实验-抽象数据类型二叉树的实现

  #include<stdio.h>    
  #include<stdlib.h>     
  #include<conio.h>        
  
typedef struct Binarytree     
  { char data;     
    struct Binarytree *lchild,*rchild;   
  }BiTNode,*Bitree;      

void BuildBiTree(Bitree &T, char *s, int &i);     
void Travel(Bitree &T);
void Printleaves(Bitree &T);
void PrintTree(Bitree &T,int Level);
void Cleartree(Bitree &T);

void main()
{int i=0,n;
 char a[30];
struct Binarytree *T;
while(1){
  printf("\n*******************************************************************"); 
  printf("\n    1.  创建二叉树");     
  printf("    2.  遍历二叉树");     
  printf("    3.  输出叶子结点\n");     
  printf("    4.  打印二叉树");     
  printf("    5.  清空二叉树");     
  printf("    6.  退出\n");   
  printf("*******************************************************************\n"); 
  printf("\n请输入你的选择(1-6):");     
  scanf("%d",&n);  
   if(n<1&&n>6)break;   
   else printf("\n操作结果:\n");  
 switch(n)     
  { case 1:  
      printf("\n以广义表形式输入二叉树的结点序列：");
      scanf("%s",a);
      printf("\n以广义表形式已输入二叉树的结点序列是：");
      printf("%s \n",a);
      BuildBiTree(T,a,i);break;
    
    case 2:  Travel(T);break;     
    case 3:  Printleaves(T);break;     
    case 4:  PrintTree(T,0);break;     
    case 5:  Cleartree(T);printf("This Bitree is empty!\n");break;     
    case 6:  printf("欢迎使用本软件!\n\n"); exit(0);  
    default: break;   
   }     
  } 
}


void BuildBiTree(Bitree &T, char *s, int &i)
  {if(s[i]!='\0')
	{if(s[i]=='#')
		{T=NULL; i++;
        }
     else{ T=(Bitree)malloc(sizeof(BiTNode));
           T->data=s[i];i++;
         }
       if(s[i]=='(')
	   	{i++;BuildBiTree(T->lchild,s,i);i++;
       if(s[i]==',')
        {i++;BuildBiTree(T->rchild,s,i);i++;}
         }      
       else{
	   	   if(T){T->lchild=NULL;
                 T->rchild=NULL;
	   	         }
           i--;
		   }
    }
 }


void Preordertree(Bitree &T)   
  { if(T)     
  {printf("%c",T->data);     
  Preordertree(T->lchild);     
  Preordertree(T->rchild);     
  }     
  }     
    
    
void Inordertree(Bitree &T)    
  { if(T)     
  {Inordertree(T->lchild);     
  printf("%c",T->data);     
  Inordertree(T->rchild);     
  }     
  }     
    
    
void Postordertree(Bitree &T)   
  { if(T)     
  {Postordertree(T->lchild);     
  Postordertree(T->rchild);     
  printf("%c",T->data);     
  }     
  }     


void Travel(Bitree &T)     
  { int m;     
  printf("\n   1.先序遍历二叉树\n   2.中序遍历二叉树   \n   3.后序遍历二叉树\n\n");     
  do{     
  printf("请输入选择(1-3):");     
  scanf("%d",&m);     
  }while(m<1||m>3);     
  switch(m)     
  {
  case(1):Preordertree(T);break;     
  case(2):Inordertree(T);break;     
  case(3):Postordertree(T);break;     
  }     
  }     
 
  
void Printleaves(Bitree &T)    
  {if(T)     
  {if(T->lchild==NULL&&T->rchild==NULL)printf("%c",T->data);     
   Printleaves(T->lchild);     
   Printleaves(T->rchild);     
  }     
  }     

     
void PrintTree(Bitree &T,int Level)/*按竖向树状打印的二叉树*/
 {  int i;
    if(T==NULL) return ;
    PrintTree(T->lchild,Level+1);
    for(i=0;i<Level-1;i++)
    {
        printf(" ");
    }
    if(Level>=1)
    {
        printf("--");
    }
    printf("%c\n",T->data);
    PrintTree(T->rchild,Level+1);
 }


void Cleartree(Bitree &T)   
  {if(T)     
  {Cleartree(T->lchild);     
   Cleartree(T->rchild);     
   free(T);     
  }     
  }