数据结构C语言版，二叉树的四种遍历方式（先序，中序，后序，层次遍历）

摘要：在我们学习数据结构的时候，树这章绝对算得上重点，而二叉树又是树的重点，二叉树的遍历就不得不好好把握了，今天我就带大家一起来看看，常用的四种二叉树的遍历。

关于二叉树的遍历方式，如题所说的四种中，它们是如何实现的，什么才叫先序，什么才叫中，后序呢，层次遍历又是什么呢？如下面有一颗二叉树，我们一起来看看。

         所谓先序，就是把先遍历根节点，再遍历左右孩子节点。

如上图，若我们用先序遍历就是A B C D E F GHK。

        中序遍历就是先遍历左孩子节点，再遍历根节点，最后遍历右孩子节点。

如上图，若我们用先序遍历就是B DC A E HGK F。

        后序遍历就是先遍历左孩子节点，再遍右孩子节点，最后遍历历根节点。

如上图，若我们用后序遍历就是DC B HKG FE A。

        最后的层次遍历，其实就是分层来遍历，按照从上往下，从左往右的规则进行遍历如上图，

若我们用层次遍历就是 A BE CF DG HK。

        代码实现如下；

头文件（函数声明）：terr.h

#ifndef _TREE_
#define _TREE_
#define N 64
typedef char data_t;
typedef struct tree_node{
	data_t data;
	struct tree_node *l;//左孩子指针
	struct tree_node *r;//右孩子指针
}Tree;


Tree *Create_tree();//创建二叉树

void Tlr(Tree *T);//先序遍历

void lTr(Tree *T);//左序遍历

void lrT(Tree *T);//后序遍历

void C_bianli(Tree *T);//层次遍历

#endif

实现函数 ：terr.c

#include 
#include 
#include 
#include 
#include "tree.h"

Tree *Create_tree()
{
	char ch;
	scanf("%c",&ch);
	Tree *T;
	if(ch == '#')
		{
		return NULL;
		}
	else
		{
		T =(Tree *)malloc(sizeof(Tree));
		if(NULL==T)
			{
			printf("T is NULLn");
			return NULL;
			}
		T->data= ch;	
		T->l=Create_tree();//递归创建左孩子
		T->r=Create_tree();//递归创建右孩子
		
		return T;
		}
}

void Tlr(Tree *T)//先序遍历
{
	
	if(T!=NULL)
	{
		printf("%c",T->data);
		
		Tlr(T->l);//递归遍历左孩子
		Tlr(T->r);//递归遍历右孩子
	}
	return;
	
}

void lTr(Tree *T)//中序遍历
{
	
	if(T!=NULL)
	{
		
		
		lTr(T->l);
		printf("%c",T->data);
		lTr(T->r);
	}
	return;
	
}
void lrT(Tree *T)//后序遍历
{
	
	if(T!=NULL)
	{
				
		lrT(T->l);		
		lrT(T->r);
		printf("%c",T->data);
	}
	return;
	
}

void C_bianli(Tree *T)//层次遍历
{
	int front,rear;
	Tree *Q[N];
	if(T==NULL)//若为空树 则直接返回
	{
		return;
	}
	for (rear=1;reardata);//打印出队内容
		if( T->l != NULL)//判断是否有左孩子
		{
			rear++;//对尾指针向后偏移
			Q[rear]=T->l;//左孩子入队
		}
		if(T->r != NULL)//判断是否有右孩子
		{
			rear++;//对尾指针向后偏移
			Q[rear]=T->r;//右孩子入队
		}
		front++;//出队一个对头指针向后偏移一个
		T=Q[front];	//把下一个元素作为新的根节点进行出入队	
	}
	return;
}

主函数：main.c

#include 
#include 
#include 
#include 
#include "tree.h"

int main()
{
	Tree *T=Create_tree();//创建二叉树

	Tlr(T);//先序遍历
	puts(" ");
	lTr(T);//左序遍历
	puts(" ");
        lrT(T);//后序遍历
	puts(" ");	
	C_bianli(T);//层次遍历
	puts(" ");
	return 0;
}

好！今天我就分享到这里，第一次分享，哪里写的不对的欢迎各位大佬多多指正，不吝赐教。