大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

一、图示理解（图片是一位前辈所留，在此感谢）

1、先序遍历

先序遍历可以想象成，小仙儿从树根开始绕着整棵树的外围转一圈，经过结点的顺序就是先序遍历的顺序
先序遍历结果：ABDHIEJCFKG

让我们来看下动画，和小仙儿一起跑两遍就记住啦，记住是绕着外围跑哦

2、中序遍历

中序遍历可以想象成，按树画好的左右位置投影下来就可以了
中序遍历结果：HDIBEJAFKCG

下面看下投影的过程动画，其实就是按左右顺序写下来就行了

3、后序遍历

后序遍历就像是剪葡萄，我们要把一串葡萄剪成一颗一颗的。
还记得我们先序遍历绕圈的路线么？
就是围着树的外围绕一圈，如果发现一剪刀就能剪下的葡萄（必须是一颗葡萄），就把它剪下来，组成的就是后序遍历了。
后序遍历结果：HIDJEBKFGCA

让我们来看下动画

4、层序遍历

层序遍历太简单了，就是按照一层一层的顺序，从左到右写下来就行了。
后序遍历结果：ABCDEFGHIJK

不知道通过这种方式，有没有觉得闭着眼睛都能写出前序、中序、后序 、层序了呀，不过这只是为了大家好理解，我想出的一种形象思维，为了用代码实现，我们还需要具体了解一下前序、中序、后序遍历。

二、深入理解三种遍历

来，让我们先把所有空结点都补上。
还记得我们先序和后序遍历时候跑的顺序么？按照这个顺序再跑一次，就是围着树的外围跑一整圈。

让我们来理解一下绕着外围跑一整圈的真正含义是：遍历所有结点时，都先往左孩子走，再往右孩子走。

观察一下，你有什么发现？
有没有发现，除了根结点和空结点，其他所有结点都有三个箭头指向它。
一个是从它的父节点指向它，一个是从它的左孩子指向它，一个是从它的右孩子指向它。
一个结点有三个箭头指向它，说明每个结点都被经过了三遍。一遍是从它的父节点来的时候，一遍是从它的左孩子返回时，一遍是从它的右孩子返回时。

其实我们在用递归算法实现二叉树的遍历的时候，不管是先序中序还是后序，程序都是按照上面那个顺序跑遍所有结点的。

先序中序和后序唯一的不同就是，在经过结点的三次中，哪次访问（输出或者打印或者做其他操作）了这个结点。有点像大禹治水三过家门，他会选择一次进去。

先序遍历顾名思义，就是在第一次经过这个结点的时候访问了它。就是从父节点来的这个箭头的时候，访问了它。
中序遍历也和名字一样，就是在第二次经过这个结点的时候访问了它。就是从左孩子返回的这个箭头的时候，访问了它。
后序遍历，就是在第三次经过这个结点的时候访问了它。就是从右孩子返回的这个箭头的时候，访问了它。

其实不管是前序中序还是后序，在程序里跑的时候都是按照同样的顺序跑的，每个结点经过三遍，第几遍访问这个结点了，就叫什么序遍历。

下面做一个实例吧

四种遍历代码

https://www.cnblogs.com/bigsai/p/11393609.html

三、代码实现加以理解

基础实例图（下面代码均围绕此展开）

我们先用代码基本实现一下遍历

void TraverseBiTree(BiTree T)
{ 
   
    if (T == NULL)
        return ;
    TraverseBiTree(T->lChild);
    TraverseBiTree(T->rChlid);
}

这个递归就能实现当遇到空指针时候返回，记住，每个结点先往左孩子走，再往右孩子走这个顺序。

如果我们想实现先序遍历，只需要在第一次经过这个结点的时候访问（输出）他就可以了，只需要加上一句printf。

//先序遍历二叉树
void TraverseBiTree(BiTree T)
{ 
   
    if (T == NULL)
        return ;
    printf("%c ", T->data);
    TraverseBiTree(T->lChild);
    TraverseBiTree(T->rChlid);
}

中序遍历，就是在第二次经过这个结点的时候访问它。

//中序遍历二叉树
void InOrderBiTree(BiTree T)
{ 
   
    if (T == NULL)
        return ;
    InOrderBiTree(T->lChild);
    printf("%c ", T->data);
    InOrderBiTree(T->rChlid);
}

后序遍历，就是在第三次经过这个结点的时候访问它。

//后序遍历二叉树
void PostOrderBiTree(BiTree T)
{ 
   
    if (T == NULL)
        return ;
    PostOrderBiTree(T->lChild);
    PostOrderBiTree(T->rChlid);
    printf("%c ", T->data);
}

我们可以看到，差别仅仅是printf出现的位置，也就是我们访问结点的位置，在递归算法中其他并没有差别。
怎么样，是不是觉得很简单！！！！！！

以下是C语言全部代码实现

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef char  ElemType; //数据类型
//定义二叉树结构
typedef struct BiTreeNode
{ 

ElemType  data; //数据域
struct BiTreeNode *lChild;
struct BiTreeNode *rChlid;
} BiTreeNode, *BiTree;
//先序创建二叉树
void CreateBiTree(BiTree *T)//要改变指针，所以要把指针的地址传进来
{ 

ElemType ch;
scanf("%c", &ch);//注意数据类型
getchar();//吸收空格或者回车
if (ch == '#')
*T = NULL;
else
{ 

*T = (BiTree)malloc(sizeof(BiTreeNode));
if (!(*T))//检查是否分配成功
exit(-1);
(*T)->data = ch;
CreateBiTree(&(*T)->lChild);//printf("输入%d的左孩子：", ch);
CreateBiTree(&(*T)->rChlid);//printf("输入%d的右孩子：", ch);
}
}
//先序遍历二叉树
void TraverseBiTree(BiTree T)
{ 

if (T == NULL)
return ;
printf("%c ", T->data);
TraverseBiTree(T->lChild);
TraverseBiTree(T->rChlid);
}
//中序遍历二叉树
void InOrderBiTree(BiTree T)
{ 

if (T == NULL)
return ;
InOrderBiTree(T->lChild);
printf("%c ", T->data);
InOrderBiTree(T->rChlid);
}
//后序遍历二叉树
void PostOrderBiTree(BiTree T)
{ 

if (T == NULL)
return ;
PostOrderBiTree(T->lChild);
PostOrderBiTree(T->rChlid);
printf("%c ", T->data);
}
//主函数
int main(void)
{ 

BiTree T;
printf("请输入先序遍历顺序下各个结点的值,#表示没有结点:\n");
CreateBiTree(&T);
printf("先序遍历二叉树:\n");
TraverseBiTree(T);
printf("\n");
printf("中序遍历二叉树:\n");
InOrderBiTree(T);
printf("\n");
printf("后序遍历二叉树:\n");
PostOrderBiTree(T);
printf("\n");
return 0;
}

（其中初始化时候，以输入‘#’作为空）
结果：

下面是同样的例子用c++实现，大家可以参考一下

#include<iostream>
using namespace std;
typedef char  ElemType; //数据类型
typedef struct BiTreeNode//定义结构体
{ 

ElemType  data; //数据域
struct BiTreeNode *lChild;//左孩子
struct BiTreeNode *rChlid;//右孩子
} BiTreeNode, *BiTree;
//先序创建二叉树
void CreateBiTree(BiTree &T)//要改变指针，C++可以把指针的引用传进来
{ 

ElemType ch;
cin >> ch;
if (ch == '#')
T = NULL;
else
{ 

T = new BiTreeNode;
T->data = ch;
CreateBiTree(T->lChild);//cout<<"输入"<<ch<<"的左孩子：" ;
CreateBiTree(T->rChlid);//cout<<"输入"<<ch<<"的右孩子：" ;
}
}
//先序遍历二叉树
void TraverseBiTree(BiTree T)
{ 

if (T == NULL)
return ;
cout << T->data <<" ";
TraverseBiTree(T->lChild);
TraverseBiTree(T->rChlid);
}
//中序遍历二叉树
void InOrderBiTree(BiTree T)
{ 

if (T == NULL)
return ;
InOrderBiTree(T->lChild);
cout << T->data <<" ";
InOrderBiTree(T->rChlid);
}
//后序遍历二叉树
void PostOrderBiTree(BiTree T)
{ 

if (T == NULL)
return ;
PostOrderBiTree(T->lChild);
PostOrderBiTree(T->rChlid);
cout << T->data <<" ";
}
int main(void)
{ 

BiTree T;
cout << "请输入先序遍历顺序下各个结点的值,#表示没有结点:" << endl;
CreateBiTree(T);
cout<<"先序遍历二叉树:"<<endl;
TraverseBiTree(T);
cout<<endl;
cout<<"中序遍历二叉树:"<<endl;
InOrderBiTree(T);
cout<<endl;
cout<<"后序遍历二叉树:"<<endl;
PostOrderBiTree(T);
cout<<endl;
return 0;
}