C语言二叉树（先中后序遍历、层序遍历、非递归先中后序遍历）

浅浅的花香味﹌ 2022-12-28 13:00 170阅读 0赞

欢迎大家交流指正

#include<stdio.h>
    #include<stdlib.h>
    
    #define MAXSIZE_QUEUE 1000
    #define MAXSIZE_STACK 1000
    
    typedef char TElemType;
    typedef int Statistics;
    
    //树的结构体
    typedef struct BitNode 
    {
    	TElemType data;
    	Statistics count;  //非递归后续遍历使用,用于统计次数
    	struct BitNode *lchlid,*rchlid;
    }BitNode;
    
    //队列结构体
    typedef struct
    {
    	BitNode **base;
    	int front,rear;
    }Queue;
    
    //栈
    typedef struct
    {
    	BitNode **base;
    	int top;
    }Stack;
    
    //初始化队列
    void InitQueue(Queue *T)
    {
    	T->base=(BitNode **)malloc(sizeof(BitNode *)*MAXSIZE_QUEUE);
    	if(!T->base) exit(0);
    	T->front=T->rear=0;
    }
    
    //初始化栈
    void InitStack(Stack *L)
    {
    	L->base=(BitNode **)malloc(sizeof(BitNode *)*MAXSIZE_STACK);
    	if(!L->base) exit(0);
    	L->top=0;
    }
    
    //入栈
    void Pushstack(BitNode *T,Stack *L)
    {
    	L->base[L->top++]=T;
    }
    
    //出栈
    BitNode* Popstack(Stack *L)
    {
    	return L->base[--L->top];
    }
    
    //入队
    
    void Push(Queue *Q,BitNode *T)
    {
    	Q->base[Q->rear++]=T;
    }
    
    //出队
    BitNode* Pop(Queue *Q)
    {
    	return (Q->base[Q->front++]);
    }
    
    
    //先序遍历法创建树
    
    void Creat_tree(BitNode **T)
    {
    	char x;
    	scanf("%c",&x);
    	if(x=='#')*T=NULL;
    	else
    	{
    		*T=(BitNode *)malloc(sizeof(BitNode));
    		if(T==NULL) exit(-2);
    		(*T)->data=x;
    		Creat_tree(&(*T)->lchlid);
    		Creat_tree(&(*T)->rchlid);
    	}
    }
    
    /***********************
    
      先序遍历
    
    ***********************/
    
    void Print1(BitNode *T)
    {
        if(T!=NULL)
    	{
    		printf("%c",T->data);
    		Print1(T->lchlid);
    		Print1(T->rchlid);
    	}
    }
    
    /***********************
    
      中序遍历
    
    ***********************/
    
    void Print2(BitNode *T)
    {
        if(T!=NULL)
    	{
    		Print2(T->lchlid);
    		printf("%c",T->data);
    		Print2(T->rchlid);
    	}
    }
    
    /***********************
    
      后序遍历
    
    ***********************/
    
    void Print3(BitNode *T)
    {
        if(T!=NULL)
    	{
    		Print3(T->lchlid);
    		Print3(T->rchlid);
    		printf("%c",T->data);
    	}
    }
    
    /***********************
    
      层序遍历
    
    ***********************/
    
    void Print4(BitNode *T)
    {
    	Queue Q;
    	InitQueue(&Q);
    	Push(&Q,T);
    	while(Q.front!=Q.rear)
    	{
    	    printf("%c",Q.base[Q.front]->data);
    	    T=Pop(&Q);	
    		if(T->lchlid!=NULL)Push(&Q,T->lchlid);
    		if(T->rchlid!=NULL)Push(&Q,T->rchlid);
    	}
    }
    
    
    /***********************
    
      非递归的先序遍历
    
    ***********************/
    
    
    void Print5(BitNode *T)
    {
    	Stack L;
    	InitStack(&L);
    	while(T!=NULL || L.top!=0)
    	{
    		while(T!=NULL)
    		{
    		  printf("%c",T->data);
    		  Pushstack(T,&L);
    		  T=T->lchlid;
    		}
    		if(L.top!=0)
    		{
    			T=Popstack(&L);
    			T=T->rchlid;
    		}
    	}
    }
    
    /***********************
    
      非递归的中序遍历
    
    ***********************/
    
    void Print6(BitNode *T)
    {
    	Stack L;
    	InitStack(&L);
    	while(T!=NULL || L.top!=0)
    	{
    		while(T!=NULL)
    		{
    		  Pushstack(T,&L);
    		  T=T->lchlid;
    		}
    
    		if(L.top!=0)
    		{
    			T=Popstack(&L);
    			printf("%c",T->data);
    			T=T->rchlid;
    		}
    	}
    }
    
    /***********************
    
      非递归的后序遍历
    
    ***********************/
    
    void Print7(BitNode *T)
    {
    	Stack L;
    	InitStack(&L);
    	while(T!=NULL || L.top!=0)
    	{
    		while(T!=NULL)
    		{
    			T->count=1;
    			Pushstack(T,&L);
    			T=T->lchlid;
    		}
    		if(L.top!=0)
    		{
    			T=Popstack(&L);
    			if(T->count == 1)
    			{
    				T->count++;
    				Pushstack(T,&L);
    				T=T->rchlid;
    			}
    			else if(T->count == 2)
    			{
    				printf("%c",T->data);
    				T=NULL;
    			}
    		}
    	}
    		
    }
    
    void main()
    {
    	struct BitNode *T;
    	printf("空以'#'号代替，如AB##CD##E##\n请输入二叉树:");
    	Creat_tree(&T);
    	printf("先序遍历:");
    	Print1(T);
    	printf("\n中序遍历:");
    	Print2(T);
    	printf("\n后序遍历:");
    	Print3(T);
    	printf("\n层序遍历:");
    	Print4(T);
    	printf("\n非递归先序遍历:");
    	Print5(T);
    	printf("\n非递归中序遍历:");
    	Print6(T);
    	printf("\n非递归后序遍历:");
    	Print7(T);
    	printf("\n");
    }