二叉树深度优先遍历的三种方式-先序，中序，后序遍历
本文将记录自己学习过程中的理解。将按顺序介绍先序、中序、及后序的递归及非递归实现，其实非递归是可以在对递归的理解上写出来的。“树的深度优先遍历”分为先、中、后序用的是栈，“树的广度优先遍历”即层次遍历，用的是队列，下一篇会讲。树不用判重，就是因为树比较特殊，不像是图，要考虑重复遍历。
目录
0.写在前面
对一个函数而言，其实就可以用栈的方式理解。比如如下一个简单函数：准备执行这个函数时，其实“我是栈底”这个动作其实是先入栈的，然后是“我是栈顶”这个动作再进栈，因此函数真正执行时，按照出栈的方式，就是先打印“我是栈顶”，再打印“我是栈底”。后面理解递归的运行会用到这里的理解方式
void my_printf()
{
printf("我是栈顶\n");
printf("我是栈底\n");
}
1.生成本文例子中的树
本文中创建的树如下：
其先、中、后序的遍历结果如下
//一棵树的先、中、后序遍历结果如下
int pre_value[] = {1,2,3,5,4,6,7,8};
int mid_value[] = {5,3,2,4,1,7,6,8};
int after_value[] = {5,3,4,2,7,8,6,1};创建树的代码，这里比较简单直接赋值的形式了，执行完tree就是一颗如上图的树
void Create_Tree(TREE_NODE_S* tree)
{
TREE_NODE_S* poll = (TREE_NODE_S*)malloc(8*sizeof(TREE_NODE_S));
int i = 0;
memset(poll,0,8*sizeof(TREE_NODE_S));
for(i = 0; i <= 7;i++)
{
poll[i].data = i+1;
}
memcpy(tree,&poll[0],sizeof(sizeof(TREE_NODE_S)));
tree->leftchild = &poll[1];
tree->rightchild = &poll[5];
poll[1].leftchild = &poll[2];
poll[1].rightchild = &poll[3];
poll[2].leftchild = &poll[4];
poll[5].leftchild = &poll[6];
poll[5].rightchild = &poll[7];
}2.先序遍历递归方式
代码如下。
void Pre_Print_Tree(TREE_NODE_S* tree)
{
if(tree == NULL)
return;
printf("%d ",tree->data);
Pre_Print_Tree(tree->leftchild);
Pre_Print_Tree(tree->rightchild);
}运用本文目录0处的理解，对着树看的话，其实简单。
开始执行时，栈如下（右边是栈底）：打印1,1的左孩2,1的右孩6
1.执行即出栈，打印1
此时栈：1的左孩2,1的右孩6
2.遍历1的左孩2
此时栈：打印2,2的左孩3,2的右孩4，1的右孩6
3.打印2
此时栈：2的左孩3,2的右孩4，1的右孩6
如上是详细版的过程，写着会很多，如下也贴上简写的其实也很繁杂，可见递归其实效率不高。
右是栈底
1.打印1，会对1的左孩2遍历，此时“遍历1的右孩6”的动作入栈
此时栈：遍历1的右孩6
2.对2遍历时，打印2，会对2的左孩3遍历，此时右孩4遍历的动作入栈
此时栈：遍历2的右孩4，遍历1的右孩6
3.对2的左孩3遍历时，打印3，会对3的左孩5遍历，此时“遍历3的右孩子空”入栈
此时栈：遍历3右孩空，遍历2的右孩4，遍历1的右孩6
4.对3的左孩5遍历，打印5，会对5的左孩空遍历，此时“遍历5的右孩空”入栈
此时栈：遍历5右孩空，遍历3右孩空，遍历2的右孩4，遍历1的右孩6
5.对5的左孩空遍历，直接返回，并出栈
此时栈：遍历5右孩空，遍历3右孩空，遍历2的右孩4，遍历1的右孩6
6.对5右孩空遍历，直接返回
此时栈：遍历3右孩空，遍历2的右孩4，遍历1的右孩6
7.对3右孩空遍历，直接返回
此时栈：遍历2的右孩4，遍历1的右孩6
8.对4遍历，会对4的左孩空遍历,打印4，此时“遍历4右孩空”入栈
此时栈:，遍历4右孩空，遍历1的右孩6
9.遍历4左孩空，直接返回
此时栈：遍历4右孩空，遍历1的右孩6
10. 遍历4左孩空，直接返回
此时栈：遍历1的右孩6
11.对6遍历，会对6的左孩 7遍历，此时“打印6”及“遍历6右孩8”入栈
此时栈：打印6，遍历6右孩8
12.对7遍历，会对7左孩空遍历，此时“打印7”及“遍历7右孩空”入栈
此时栈：打印7，遍历7右孩空，打印6，遍历6右孩8
13.对7左孩空遍历，直接返回，开始出栈
此时栈：打印7，遍历7右孩空，打印6，遍历6右孩8
14.打印7
此时栈：遍历7右孩空，打印6，遍历6右孩8
15.对7右孩空，直接返回，继续出栈
此时栈：打印6，遍历6右孩8
16.打印6
此时栈：遍历6右孩8
17.遍历8，会对8的左孩空遍历，“打印8”及“遍历8右孩空”入栈
此时栈：打印8，遍历8右孩空
18.遍历8的左孩空，直接返回，并开始出栈
此时栈：打印8，遍历8右孩空
19.打印8
此时栈：遍历8右孩空
20.遍历8右孩空，直接返回
21.至此，顺序：1,2,3,5,4，6,7,8
3.先序的非递归方式
代码如下:
void Pre_Printf_Tree_2_v1(TREE_NODE_S* tree)
{
STACK_S stack = {0};
TREE_NODE_S topnode = {0};
TREE_NODE_S* topnode_p = NULL;
Stack_Init(&stack,50);
//1.顶点入栈
(void)Stack_Pushback(&stack,tree);
while(Stack_Is_Empty(&stack)!=1)
{
//2.对于栈中的元素，出栈就调用操作函数
topnode_p = Stack_GetTop(&stack);//不判断为空是因为下面入栈的节点保证了不是空的，如果是下面注释的方法那么就这里需要判空
printf("%d ",topnode_p->data);
Stack_Pop(&stack);
//3.如果顶点元素有右孩子，右孩子优先入栈，因为栈的先入后出
if(topnode_p->rightchild != NULL)
{
(void)Stack_Pushback(&stack,topnode_p->rightchild);
}
if(topnode_p->leftchild != NULL)
{
(void)Stack_Pushback(&stack,topnode_p->leftchild);
}
/*if(topnode_p != NULL)
{
(void)Stack_Pushback(&stack,topnode_p->rightchild);
(void)Stack_Pushback(&stack,topnode_p->leftchild);
}*/
}
}知道递归的执行方式，借助栈结构写出非递归的方式也不是很难。看节点1、2、3，联系先序递归写法，可以知道其实出栈即可以打印，同时并先入栈右节点、再入栈左节点。
4.中序递归
代码如下：
void mid_print_tree(TREE_NODE_S* tree)
{
if(tree == NULL)
return;
mid_print_tree(tree->leftchild);
printf("%d ",tree->data);
mid_print_tree(tree->rightchild);
}同理，也可以知道其的递归运行方式
右是栈底
1.首先1开始，会对1的左孩子2进行遍历，此时“打印1”动作，及对“1的右孩子6遍历”的动作入栈，后者先压入。
此时栈：打印1，遍历6
2.对2继续，同理，会对2的左孩子3进行遍历，此时“打印2”动作及对“2的右孩子4遍历”动作入栈，后者先压入
此时栈：打印2，遍历4，打印1，遍历6
3.对3遍历，会对3的左孩子5进行遍历，此时，“打印3”动作及“对3的右孩子（空）遍历”动作入栈，后者先压入
此时栈：打印3，遍历3的右孩空，打印2，遍历4，打印1，遍历6
4.对5遍历，会继续对5的左孩子空遍历，此时“打印5”动作及对“5的右孩子（空）遍历”动作入栈，后者先压入
此时栈:打印5，遍历5的右孩空，打印3，遍历3的右孩空，打印2，遍历4，打印1，遍历6
5.对5的左孩子空遍历，则返回并开始出栈
6.打印5，
此时栈：遍历5的右孩空，打印3，遍历3的右孩空，打印2，遍历4，打印1，遍历6
7.遍历5的右孩空，直接返回
此时栈：打印3，遍历3的右孩空，打印2，遍历4，打印1，遍历6
8.打印3
此时栈：遍历3的右孩空，打印2，遍历4，打印1，遍历6
9.遍历3的右孩子空，直接返回
此时栈：打印2，遍历4，打印1，遍历6
10.打印2
此时栈：遍历4，打印1，遍历6
11.遍历4时，会对4的左孩子空遍历，此时“打印4”动作和“对4的右孩子空遍历”动作入栈
此时栈：打印4，遍历4的右空，打印1，遍历6
12.打印4
此时栈：遍历4的右空，打印1，遍历6
13.遍历4的右空，直接返回
此时栈：打印1，遍历6
14.打印1
此时栈：遍历6
15：对6遍历，会对6的左孩子7遍历，此时“打印6”动作及对6的右孩8 压栈，后者先压入
此时栈:打印6，遍历8
16：对7遍历，会对7的左孩子空遍历，此时“打印7”及遍历7的右孩空入栈
此时栈：打印7，遍历7右孩空，打印6，遍历8
17.打印7
此时栈：遍历7右孩空，打印6，遍历8
18.遍历7右孩空，直接返回
此时栈：打印6，遍历8
19:打印6
此时栈：遍历8
20：遍历8时，会对8的左孩子空遍历，此时“打印8”及遍历8的右孩空入栈
此时栈：打印8，遍历8右孩空
21.打印8
此时栈：遍历8右孩空
22：遍历8右孩空，直接返回
23.至此打印顺序是：5,3,2,4,1,7,6,8
5.中序非递归方式
代码如下：
void mid_print_tree_2(TREE_NODE_S* tree)
{
STACK_S stack = {0};
TREE_NODE_S topnode = {0};
TREE_NODE_S* topnode_p = NULL;
int i = 0;
Stack_Init(&stack,50);
//1.顶点入栈
(void)Stack_Pushback(&stack,tree);
while(Stack_Is_Empty(&stack)!=1)
{
//2.把左孩子全部压入
topnode_p = Stack_GetTop(&stack);
while(topnode_p != NULL)
{
Stack_Pushback(&stack,topnode_p->leftchild);
topnode_p = Stack_GetTop(&stack);
}
//把最后一个左孩子空的弹走
Stack_Pop(&stack);
topnode_p = Stack_GetTop(&stack);
if(topnode_p != NULL)//避免栈中最后一个空的被弹出后，此时栈已经空了再获取栈顶时就是空的
{
printf("%d ",topnode_p->data);
Stack_Pop(&stack);
Stack_Pushback(&stack,topnode_p->rightchild);
}
}
}知道递归的写法，并用原理，可以看到其实中序需要对节点的左节点遍历到底，才能对节点进行打印。打印之后，其右节点又入栈当做左节点方式继续遍历。
6.后序递归遍历
代码如下：
void after_print_tree(TREE_NODE_S* tree)
{
if(tree == NULL)
return ;
after_print_tree(tree->leftchild);
after_print_tree(tree->rightchild);
printf("%d ",tree->data);
}递归运行的方式其实是一样的，有兴趣的可以自行写出，然后写道评论区共同讨论（哈哈）。
7.后序非递归方式
代码如下：
void after_print_tree_2(TREE_NODE_S* tree)
{
STACK_S stack = {0};
TREE_NODE_S* topnode_p = NULL;
TREE_NODE_S* pre = NULL;
Stack_Init(&stack,50);
Stack_Pushback(&stack,tree);
while(Stack_Is_Empty(&stack)!=1)
{
topnode_p = Stack_GetTop(&stack);
//要打印节点：条件是该节点左右孩子为空，或者上次遍历的节点不是空的而且恰好是该节点的左孩子或者右孩子
if((topnode_p->leftchild == NULL && topnode_p->rightchild ==NULL) || (pre!=NULL && (pre == topnode_p->leftchild || pre == topnode_p->rightchild)))
{
printf("%d ",topnode_p->data);
Stack_Pop(&stack);
pre = topnode_p;
}
else
{
if(topnode_p->rightchild != NULL)
Stack_Pushback(&stack,topnode_p->rightchild);
if(topnode_p->leftchild != NULL)
Stack_Pushback(&stack,topnode_p->leftchild);
}
}
}通过后序递归的写法，及递归运行方式，对着图，可以知道打印节点的条件是该节点的左右孩子为空，或者上一次的节点是该节点的左孩子或者右孩子；
8.栈结构代码如下
//树节点
typedef struct Tree_node
{
int data;
struct Tree_node* leftchild;
struct Tree_node* rightchild;
}TREE_NODE_S;
//栈结构
typedef struct Stack
{
int cap;
int top;
TREE_NODE_S** treenode;
}STACK_S;
void Stack_Init(STACK_S* stack,int cap)
{
if(cap <= 0)
return;
stack->treenode = (TREE_NODE_S**)malloc(sizeof(TREE_NODE_S*)*cap);
memset((TREE_NODE_S*)stack->treenode,0,sizeof(TREE_NODE_S*)*cap);
stack->cap = cap;
stack->top = -1;
}
int Stack_Is_Full(STACK_S* stack)
{
return stack->cap == stack->top ? 1 :0;
}
int Stack_Is_Empty(STACK_S* stack)
{
return stack->top == -1 ? 1 : 0;
}
void Stack_Pushback(STACK_S* stack,TREE_NODE_S* treenode)
{
if(Stack_Is_Full(stack)!=1)
{
stack->top++;
stack->treenode[stack->top] = treenode;
}
return;
}
TREE_NODE_S* Stack_GetTop(STACK_S* stack)
{
if(Stack_Is_Empty(stack)!=1)
return stack->treenode[stack->top];
else
return NULL;
}
void Stack_Pop(STACK_S* stack)
{
if(Stack_Is_Empty(stack)!=1)
stack->top--;
}9.所有代码的链接，一个.c文件
https://pan.baidu.com/s/1eolitj44OgsgowM2T5aPOQ
10.结果
上一篇： 浅谈php和.net的区别，浅谈php.net区别_PHP教程
下一篇： 遍历对象属性的方法
推荐阅读
-
Python实现输入二叉树的先序和中序遍历，再输出后序遍历操作示例
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
【算法】二叉树的前序、中序、后序、层序遍历和还原。
-
PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例
-
Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】
-
二叉树的先序遍历、中序遍历、后序遍历
-
树与二叉树 树二叉树前序、中序、后序遍历先根遍历后根遍历
-
JavaScript实现二叉树的先序、中序及后序遍历方法详解
-
python实现二叉树的层序、前序、中序、后序、之字形遍历
-
C#使用前序遍历、中序遍历和后序遍历打印二叉树的方法