C语言二叉树的创建与遍历（先序，中序，后序，层次）

╰+攻爆jí腚メ 2023-06-17 03:55 3阅读 0赞

为了方便理解二叉树，我简单的介绍一下树，树顾名思义有根和树杈，叶子，比如：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExOTUxNw_size_16_color_FFFFFF_t_70][]

这是一颗以 A为根结点（根节点：没有前驱），I,J,G,K 为叶子结点的树（叶子结点：没有后继，即没有孩子节点），在这树中B,C,D是根结点A的孩子结点，E为B的孩子结点，F,G为C的孩子结点，E,F,G,H为彼此兄弟结点，B为E的双亲结点，C为F，G的双亲结点，A为E,F,G,H的祖先，树的度：每一个结点的孩子结点个数，A的度为3，E的度为1，I的度为0；

二叉树：每一个结点的度为不大于2，每一棵子树分为左右，不能随意改变，以下就是一颗二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExOTUxNw_size_16_color_FFFFFF_t_70 1][]

根结点为A，A的左孩子为B，

右孩子为C，B的左孩子为D，右孩子为E，每一个结点最多有两个孩子。

遍历二叉树的方法有四种：

1.Preorder 先序遍历（先序递归遍历和先序非递归遍历）

2.Inorder 中序遍历（中序递归遍历和中序非递归遍历）

3.Postorder 后序遍历（后序递归遍历和后序非递归遍历）

4.Leverorder 层次遍历

先序遍历方式：

先访问根结点，按顺序遍历左孩子，按顺序遍历右孩子。

中序遍历：

按中序遍历左孩子，访问根结点，按中序遍历右孩子。

后序遍历：

按后序遍历左孩子，按后序遍历右孩子，访问根结点。

层次遍历：

先访问根结点，访问下一层的左孩子，右孩子，在访问下一层的左孩子，右孩子.....

上面的二叉树的这四种遍历序列分别为：

先序遍历：ABDHECFJIG

中序遍历：HDBEAJFICG

后序遍历：HDEBJIFGCA

层次遍历：ABCDEFGHJI

以下我介绍先中后序递归遍历和层次遍历

先序递归遍历：

void preorder(Bitree root)//递归先序遍历 
    {
    	if(root)	
    	{
    		printf("%c",root->data);
    		preorder(root->Lchild);
    		preorder(root->Rchild);
    	}
    }

中序递归遍历：

void Inorder(Bitree root)
    {
    	
    	if(root)	
    	{
    		Inorder(root->Lchild);
    		printf("%c",root->data);
    		Inorder(root->Rchild);
    	}
    }

后续递归遍历：

void PostOrder(Bitree root)	//后序递归遍历
    {
        if(root)
        {
            PostOrder(root->Lchild);
            PostOrder(root->Rchild);
            printf("%c", root->data);
        }
    }

层次遍历:

void Levelorder(Bitree root)//层次遍历 
    {
    	Bitree p;        
    	QueQue A;	                 //定义队列			
    	A=Create_QueQue();          //创建队列 
    	INPUT_QUEQUE(A,root); 		//入队 
    	while(!Empty_QUEQUE(A))     //队列非空时 
    	{
    		OUTPUT_QUEQUE(A,&p);   //出队 
    		printf("%c",p->data);
    		if(p->Lchild!=NULL) INPUT_QUEQUE(A,p->Lchild);//左孩子入队 
     		if(p->Rchild!=NULL) INPUT_QUEQUE(A,p->Rchild);//右孩子入队 
    	}
    }

完整代码：

#include<stdio.h>
    #include<malloc.h>
    #include<string.h>
    #define MAXSIZE 30
    
    typedef struct bitree{
    	char data;
    	struct bitree *Lchild;
    	struct bitree *Rchild;
    }*Bitree,BiTree;  //二叉树 
    
    typedef struct node{
    	Bitree data;
    	struct node *Next;
    }NODE,*Node;   //队列数据域 
    
    typedef struct{
    	Node front;
    	Node rear;
    }QUEQUE,*QueQue; //队列指针域 
    
    Bitree Create_Bitree();//创建二叉树 
    void Create_Bitree_input(Bitree *root);//初始化二叉树
    QueQue Create_QueQue();//创建队列
    void INPUT_QUEQUE(QueQue A,Bitree root);//出队 
    int Empty_QUEQUE(QueQue A);//队列判空 
    void OUTPUT_QUEQUE(QueQue A,Bitree *root); //入队
    void preorder(Bitree root);//先序递归遍历 
    void PostOrder(Bitree root);//后序递归遍历
    void Inorder(Bitree root);//中序递归遍历
    void Levelorder(Bitree root);//层次遍历
    
    main()
    {
    	Bitree root;
    	root=Create_Bitree();
    	Create_Bitree_input(&root); 
    	preorder(root);//先序递归遍历 
    	printf("\n"); 
    	PostOrder(root);//后序递归遍历
    	printf("\n");
    	Inorder(root);//中序递归遍历
    	printf("\n");
    	Levelorder(root);//层次遍历
    	//AB#DG###CE##FH###   测试样例 
    } 
    
    
    Bitree Create_Bitree()//创建二叉树 
    {
    	Bitree root=(Bitree)malloc(sizeof(BiTree));
    	root->Lchild=root->Rchild=NULL;	
    	return root;
    }
    
    void Create_Bitree_input(Bitree *root)//初始化二叉树 
    {
    	char ch;
    	ch=getchar();
    	if(ch=='#')  *root=NULL;
    	else
    	{
    		(*root)=(Bitree)malloc(sizeof(BiTree));
    		(*root)->data=ch;
    		Create_Bitree_input(&((*root)->Lchild));
    		Create_Bitree_input(&((*root)->Rchild));
    	}
    }
    
    
    QueQue Create_QueQue()//创建队列
    {
    	QueQue A=(QueQue)malloc(sizeof(QUEQUE));
    	Node   B=(Node)malloc(sizeof(NODE)); 
    	B->Next=NULL;
    	A->front=A->rear=B;
    	return A;	
    }
    
    void INPUT_QUEQUE(QueQue A,Bitree root)//出队 
    {
    	Node B;
    	B=(Node)malloc(sizeof(NODE));
    	B->data=root;
    	B->Next=NULL;
    	A->rear->Next=B;
    	A->rear=B;	
    }
    
    int Empty_QUEQUE(QueQue A)//队列判空 
    {
    	if(A->front==A->rear)
    	return 1;
    	else 
    	return 0;	
    }
    
    void OUTPUT_QUEQUE(QueQue A,Bitree *root) //入队
    {
    	Node B;
    	if(!Empty_QUEQUE(A))
    	{ 
    		B=A->front->Next;
    		A->front->Next=B->Next;
    		*root=B->data;
    		if(A->front->Next==NULL)
    		{
    			A->rear = A->front; 
    		}
    		
    	}
    } 
     
    void preorder(Bitree root)//递归先序遍历 
    {
    	if(root)	
    	{
    		printf("%c",root->data);
    		preorder(root->Lchild);
    		preorder(root->Rchild);
    	}
    }
    
    void Inorder(Bitree root)//中序递归 
    {
    	
    	if(root)	
    	{
    		Inorder(root->Lchild);
    		printf("%c",root->data);
    		Inorder(root->Rchild);
    	}
    }
    
    
    void PostOrder(Bitree root)	//后序递归遍历
    {
        if(root)
        {
            PostOrder(root->Lchild);
            PostOrder(root->Rchild);
            printf("%c", root->data);
        }
    }
    
    void Levelorder(Bitree root)//层次遍历 
    {
    	Bitree p;        
    	QueQue A;	                 //定义队列			
    	A=Create_QueQue();          //创建队列 
    	INPUT_QUEQUE(A,root); 		//入队 
    	while(!Empty_QUEQUE(A))     //队列非空时 
    	{
    		OUTPUT_QUEQUE(A,&p);   //出队 
    		printf("%c",p->data);
    		if(p->Lchild!=NULL) INPUT_QUEQUE(A,p->Lchild);//左孩子入队 
     		if(p->Rchild!=NULL) INPUT_QUEQUE(A,p->Rchild);//右孩子入队 
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExOTUxNw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191127132151829.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExOTUxNw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExOTUxNw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2019112713453470.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExOTUxNw==,size_16,color_FFFFFF,t_70