数据结构（二叉树）——二叉树的建立、存储、遍历

Bertha 。 2022-12-24 11:50 261阅读 0赞

建立二叉树,并通过调用函数,，输出先序遍历、中序遍历与后序遍历的结果

#include <stdio.h>
    #include <stdlib.h>
    
    #define TRUE       1
    #define FALSE      0
    #define OK         1
    #define ERROR      0
    //DataType 是二叉树数据元素类型,此程序定义为char型
    typedef char DataType;
    
    typedef struct Node
    {
        
    	DataType data;
    	struct Node *LChild;
    	struct Node *RChild;
    }BiTNode, *BiTree;
    
    void CreateBiTree(BiTree *bt)
    {
        
    	char ch;
    	ch = getchar();
        if(ch=='.') *bt=NULL;
        else 
    	{
        
    		*bt=(BiTree)malloc(sizeof(BiTNode)); 
            (*bt)->data=ch;
            CreateBiTree(&((*bt)->LChild)); 
            CreateBiTree(&((*bt)->RChild)); 
    	}
    }
    
    int Create(BiTree *T)
    {
        
      printf("按先序遍历的结果输入二叉树\n");
      printf("请输入先序遍历二叉树的结果,程序据此建立二叉树。\n");
      printf("对于叶子结点以空格表示。\n");
      printf("例如:abc..de.g..f...(回车)，建立如下二叉树：\n");
      printf("           a      \n");
      printf("          /       \n");
      printf("         b        \n");
      printf("        / \\       \n");
      printf("       c   d      \n");
      printf("          / \\     \n");
      printf("         e   f    \n");
      printf("          \\       \n");
      printf("           g      \n");
      CreateBiTree(T);
      return OK;
    }
    
    int DestroyBiTree(BiTree *T){
        
      if(*T){
        
        if((*T)->LChild) DestroyBiTree(&((*T)->LChild)); //销毁左子树  
        if((*T)->RChild) DestroyBiTree(&((*T)->RChild)); //销毁右子树  
        free(*T);  //销毁根结点 
        *T=NULL;
      }
      return OK;
    }
    
    int Visit(char c)
    {
        
      printf("%c",c);  //显示结点数据域
      return OK;
    }
    
    void  PreOrder(BiTree root) 
    /*先序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/
    {
        
    	if(root!=NULL)
    	{
        
         Visit(root->data);
         PreOrder(root->LChild);
         PreOrder(root->RChild);	
    	}
    }
    
    void  InOrder(BiTree root)  
    /*中序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/
    {
        
    	if(root!=NULL)
    	{
        
        InOrder(root->LChild);
        Visit(root->data);
        InOrder(root->RChild);
    	}
    }
    
    void  PostOrder(BiTree root)  
    /* 后序遍历二叉树，root为指向二叉树(或某一子树)根结点的指针*/
    {
        
    	if(root!=NULL)
    	{
        
    	PostOrder(root->LChild);
    	PostOrder(root->RChild);
    	Visit(root->data);
    	}
    }
    
    void PrintTree(BiTree bt,int nLayer)  /* 按竖向树状打印的二叉树 */ 
    {
        
     if(bt==NULL) return;
     PrintTree(bt->RChild,nLayer+1);
     for(int i=0;i<nLayer;i++)
    	 printf(" ");
     printf("%c\n",bt->data);
     PrintTree(bt->LChild,nLayer+1);
    }
    
    void main(){
        
      BiTree T;
      int choice,flag=1;
      printf("本程序实现二叉树的操作:\n");
      printf("可以进行建立二叉树, 递归先序、中序、后序遍历等操作。\n");
      Create(&T);
      while(flag)
    {
        
        printf("请选择: \n");
        printf("1.递归先序遍历\n");
        printf("2.递归中序遍历\n");
        printf("3.递归后序遍历\n");
        printf("4.按树状输出二叉树\n");
        printf("5.重新构建二叉树\n");
        printf("6.退出程序\n");
        scanf("%d",&choice);
        switch(choice){
        
          case 1:
    	if(T){
        
    	  printf("先序遍历二叉树:");
    	  PreOrder(T); 
    	  printf("\n");
    	}
    	else
    	  printf("二叉树为空!\n");
    	break;
          case 2:
    	if(T){
        
    	  printf("中序遍历二叉树:");
    	  InOrder(T);
    	  printf("\n");
    	}
    	else
    	  printf("二叉树为空!\n");
    	break;
          case 3:
    	if(T){
        
    	  printf("后序遍历二叉树:");
    	  PostOrder(T);
    	  printf("\n");
    	}
    	else
    	  printf("二叉树为空!\n");
    	break;
          case 4:
    	PrintTree(T,0);
    	break;
           case 5:
    	DestroyBiTree(&T);
    	fflush(stdin);
    	CreateBiTree(&T);
    	break;
          default:
    	flag=0;
    	printf("程序运行结束，按任意键退出!\n");
    	getchar();
        }
      }
      DestroyBiTree(&T);
    }