@[TOC]
先序遍历
先序遍历规定
先序遍历的核心思想：1.拜访根节点；2.拜访以后节点的左子树；3.若以后节点无左子树，则拜访以后节点的右子树；即考查到一个节点后，即刻输入该节点的值，并持续遍历其左右子树。(根左右)
先序遍历举例
如图所示，采纳先序遍历拜访这颗二叉树的具体过程为：
1.拜访该二叉树的根节点，找到 1；
2.拜访节点 1 的左子树，找到节点 2；
3.拜访节点 2 的左子树，找到节点 4；
4.因为拜访节点 4 左子树失败，且也没有右子树，因而以节点 4 为根节点的子树遍历实现。但节点 2 还没有遍历其右子树，因而当初开始遍历，即拜访节点 5；
5.因为节点 5 无左右子树，因而节点 5 遍历实现，并且由此以节点 2 为根节点的子树也遍历实现。当初回到节点 1 ，并开始遍历该节点的右子树，即拜访节点 3；
6.拜访节点 3 左子树，找到节点 6；
7.因为节点 6 无左右子树，因而节点 6 遍历实现，回到节点 3 并遍历其右子树，找到节点 7；
8.节点 7 无左右子树，因而以节点 3 为根节点的子树遍历实现，同时回归节点 1。因为节点 1 的左右子树全副遍历实现，因而整个二叉树遍历实现；
因而，图 中二叉树采纳先序遍历失去的序列为：1 2 4 5 3 6 7
先序遍历代码（递归）
/* * @Description: * @Version: * @Autor: Carlos * @Date: 2020-05-29 16:55:41 * @LastEditors: Carlos * @LastEditTime: 2020-05-30 17:03:23 */ #include <stdio.h>#include <string.h>#include <stdlib.h>#define TElemType int//结构结点的构造体typedef struct BiTNode{ TElemType data;//数据域 struct BiTNode *lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;/** * @Description: 初始化树的函数 * @Param: BiTree *T 构造体指针的指针 * @Return: 无 * @Author: Carlos */void CreateBiTree(BiTree *T){ *T=(BiTree)malloc(sizeof(BiTNode)); //根节点 (*T)->data=1; (*T)->lchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->rchild=(BiTree)malloc(sizeof(BiTNode)); //1节点的左孩子2 (*T)->lchild->data=2; (*T)->lchild->lchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->lchild->rchild=(BiTree)malloc(sizeof(BiTNode)); //2节点的右孩子5 (*T)->lchild->rchild->data=5; (*T)->lchild->rchild->lchild=NULL; (*T)->lchild->rchild->rchild=NULL; //1节点的右孩子3 (*T)->rchild->data=3; (*T)->rchild->lchild=(BiTree)malloc(sizeof(BiTNode)); //3节点的左孩子6 (*T)->rchild->lchild->data=6; (*T)->rchild->lchild->lchild=NULL; (*T)->rchild->lchild->rchild=NULL; (*T)->rchild->rchild=(BiTree)malloc(sizeof(BiTNode)); //3节点的右孩子7 (*T)->rchild->rchild->data=7; (*T)->rchild->rchild->lchild=NULL; (*T)->rchild->rchild->rchild=NULL; //2节点的左孩子4 (*T)->lchild->lchild->data=4; (*T)->lchild->lchild->lchild=NULL; (*T)->lchild->lchild->rchild=NULL;}/** * @Description: 模仿操作结点元素的函数，输入结点自身的数值 * @Param:BiTree elem 就构造体指针 * @Return: 无 * @Author: Carlos */void PrintBiT(BiTree elem){ printf("%d ",elem->data);}/** * @Description: 先序遍历 * @Param: BiTree T 构造体指针 * @Return: 无 * @Author: Carlos */void PreOrderTraverse(BiTree T){ if (T) { PrintBiT(T);//调用操作结点数据的函数办法 PreOrderTraverse(T->lchild);//拜访该结点的左孩子 PreOrderTraverse(T->rchild);//拜访该结点的右孩子 } //如果结点为空，返回上一层 return;}int main() { BiTree Tree; CreateBiTree(&Tree); printf("先序遍历: \n"); PreOrderTraverse(Tree);}先序遍历代码（非递归）
因为要在遍历完某个树的根节点的左子树后接着遍历节点的右子树，为了能找到该树的根节点，须要应用栈来进行暂存。中序和后序也都波及到回溯，所以都须要用到栈。
#include <stdio.h>#include <string.h>#include <stdlib.h>#define TElemType int//结构结点的构造体typedef struct BiTNode{ TElemType data;//数据域 struct BiTNode *lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;int top = -1;//定义一个程序栈BiTree a[20];/** * @Description: 初始化树 * @Param: BiTree *T 指针的指针 * @Return: 无 * @Author: Carlos */void CreateBiTree(BiTree *T){ *T=(BiTree)malloc(sizeof(BiTNode)); //根节点 (*T)->data=1; (*T)->lchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->rchild=(BiTree)malloc(sizeof(BiTNode)); //1节点的左孩子2 (*T)->lchild->data=2; (*T)->lchild->lchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->lchild->rchild=(BiTree)malloc(sizeof(BiTNode)); //2节点的右孩子5 (*T)->lchild->rchild->data=5; (*T)->lchild->rchild->lchild=NULL; (*T)->lchild->rchild->rchild=NULL; //1节点的右孩子3 (*T)->rchild->data=3; (*T)->rchild->lchild=(BiTree)malloc(sizeof(BiTNode)); //3节点的左孩子6 (*T)->rchild->lchild->data=6; (*T)->rchild->lchild->lchild=NULL; (*T)->rchild->lchild->rchild=NULL; (*T)->rchild->rchild=(BiTree)malloc(sizeof(BiTNode)); //3节点的右孩子7 (*T)->rchild->rchild->data=7; (*T)->rchild->rchild->lchild=NULL; (*T)->rchild->rchild->rchild=NULL; //2节点的左孩子4 (*T)->lchild->lchild->data=4; (*T)->lchild->lchild->lchild=NULL; (*T)->lchild->lchild->rchild=NULL;}/** * @Description: 打印二叉树 * @Param: BiTree elem 指针的指针 * @Return: 无 * @Author: Carlos */void PrintBiT(BiTree elem){ printf("%d ",elem->data);}/** * @Description: 二叉树压栈函数 * @Param: BiTree* a 构造体指针的指针（也能够了解为指针数组） BiTree elem 构造体指针 * @Return: 无 * @Author: Carlos */void Push(BiTree* a,BiTree elem){ a[++top]=elem;}/** * @Description: 二叉树弹栈函数 * @Param: 无 * @Return: 无 * @Author: Carlos */void Pop(){ if (top==-1) { return ; } top--;}/** * @Description: 获取栈顶元素 * @Param: BiTree*a 构造体指针数组 * @Return: 构造体指针 * @Author: Carlos */BiTree GetTop(BiTree*a){ return a[top];}/** * @Description: 先序遍历 * @Param: BiTree Tree 构造体指针 * @Return: 无 * @Author: Carlos */void PreOrderTraverse(BiTree Tree){ //长期指针 BiTree p; //根结点进栈 Push(a, Tree); while (top!=-1) { //取栈顶元素 p=GetTop(a); //弹栈 Pop(); while (p) { //调用结点的操作函数 PrintBiT(p); //如果该结点有右孩子，右孩子进栈 if (p->rchild) { Push(a,p->rchild); } p=p->lchild;//始终指向根结点最初一个左孩子 } }}int main() { BiTree Tree; CreateBiTree(&Tree); printf("先序遍历: \n"); PreOrderTraverse(Tree); }中序遍历
中序遍历规定
二叉树中序遍历的实现思维是：1.拜访以后节点的左子树；2.拜访根节点；3.拜访以后节点的右子树。即考查到一个节点后，将其暂存，遍历完左子树后，再输入该节点的值，而后遍历右子树。(左根右)
中序遍历举例
以上图为例，采纳中序遍历的思维遍历该二叉树的过程为：
1.拜访该二叉树的根节点，找到 1；
2.遍历节点 1 的左子树，找到节点 2；
3.遍历节点 2 的左子树，找到节点 4；
4.因为节点 4 无左孩子，因而找到节点 4，并遍历节点 4 的右子树；
5.因为节点 4 无右子树，因而节点 2 的左子树遍历实现，拜访节点 2；
6.遍历节点 2 的右子树，找到节点 5；
7.因为节点 5 无左子树，因而拜访节点 5 ，又因为节点 5 没有右子树，因而节点 1 的左子树遍历实现，拜访节点 1 ，并遍历节点 1 的右子树，找到节点 3；
8.遍历节点 3 的左子树，找到节点 6；
9.因为节点 6 无左子树，因而拜访节点 6，又因为该节点无右子树，因而节点 3 的左子树遍历实现，开始拜访节点 3 ，并遍历节点 3 的右子树，找到节点 7；
10.因为节点 7 无左子树，因而拜访节点 7，又因为该节点无右子树，因而节点 1 的右子树遍历实现，即整棵树遍历实现；
因而，上图中二叉树采纳中序遍历失去的序列为：4 2 5 1 6 3 7
中序遍历代码（递归）
/* * @Description: 递归实现的中序遍历 * @Version: V1.0 * @Autor: Carlos * @Date: 2020-05-18 14:53:29 * @LastEditors: Carlos * @LastEditTime: 2020-05-30 17:21:06 */ #include <stdio.h>#include <string.h>#include <stdlib.h>#define TElemType int//结构结点的构造体typedef struct BiTNode{ //数据域 TElemType data; //左右孩子指针 struct BiTreelchild,*rchild;}BiTNode,*BiTree;/** * @Description: 初始化树 * @Param: BiTree *T 构造体指针的指针（指针数组） * @Return: 无 * @Author: Carlos */void CreateBiTree(BiTree *T){ *T=(BiTree)malloc(sizeof(BiTNode)); (*T)->data=1; (*T)->lchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->rchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->lchild->data=2; (*T)->lchild->lchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->lchild->rchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->lchild->rchild->data=5; (*T)->lchild->rchild->lchild=NULL; (*T)->lchild->rchild->rchild=NULL; (*T)->rchild->data=3; (*T)->rchild->lchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->rchild->lchild->data=6; (*T)->rchild->lchild->lchild=NULL; (*T)->rchild->lchild->rchild=NULL; (*T)->rchild->rchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->rchild->rchild->data=7; (*T)->rchild->rchild->lchild=NULL; (*T)->rchild->rchild->rchild=NULL; (*T)->lchild->lchild->data=4; (*T)->lchild->lchild->lchild=NULL; (*T)->lchild->lchild->rchild=NULL;}/** * @Description: 显示函数 * @Param: BiTree elem 构造体指针 * @Return: 无 * @Author: Carlos */void PrintBiT(BiTree elem){ printf("%d ",elem->data);}/** * @Description: 中序遍历 * @Param: BiTree T 构造体指针 * @Return: 无 * @Author: Carlos */void INOrderTraverse(BiTree T){ if (T) { INOrderTraverse(T->lchild);//遍历左孩子 PrintBiT(T);//调用操作结点数据的函数办法 INOrderTraverse(T->rchild);//遍历右孩子 } //如果结点为空，返回上一层 return;}int main() { BiTree Tree; CreateBiTree(&Tree); printf("中序遍历算法: \n"); INOrderTraverse(Tree);}中序遍历代码（非递归）
和非递归先序遍历相似，惟一区别是考查到以后节点时，并不间接输入该节点。而是当考查节点为空时，从栈中弹出的时候再进行输入(永远先思考左子树，直到左子树为空才拜访根节点)。
/* * @Description: 二叉树的先序遍历（非递归） * @Version: V1.0 * @Autor: Carlos * @Date: 2020-05-17 16:35:27 * @LastEditors: Carlos * @LastEditTime: 2020-05-18 14:51:01 */ #include <stdio.h>#include <string.h>#include <stdlib.h>#define DBG_PRINTF(fmt, args...) \do\{\ printf("<<File:%s Line:%d Function:%s>> ", __FILE__, __LINE__, __FUNCTION__);\ printf(fmt, ##args);\}while(0)#define TElemType intint top=-1;//top变量时刻示意栈顶元素所在位置//结构结点的构造体typedef struct BiTNode{ //数据域 TElemType data; //左右孩子指针 struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;/** * @Description: 初始化树 * @Param: BiTree *T 构造体指针的指针 * @Return: 无 * @Author: Carlos */void CreateBiTree(BiTree *T){ *T=(BiTree)malloc(sizeof(BiTNode)); (*T)->data=1; (*T)->lchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->rchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->lchild->data=2; (*T)->lchild->lchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->lchild->rchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->lchild->rchild->data=5; (*T)->lchild->rchild->lchild=NULL; (*T)->lchild->rchild->rchild=NULL; (*T)->rchild->data=3; (*T)->rchild->lchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->rchild->lchild->data=6; (*T)->rchild->lchild->lchild=NULL; (*T)->rchild->lchild->rchild=NULL; (*T)->rchild->rchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->rchild->rchild->data=7; (*T)->rchild->rchild->lchild=NULL; (*T)->rchild->rchild->rchild=NULL; (*T)->lchild->lchild->data=4; (*T)->lchild->lchild->lchild=NULL; (*T)->lchild->lchild->rchild=NULL;}/** * @Description: 中序遍历应用的进栈函数 * @Param: BiTree* a 指向树的指针数组 BiTree elem 进栈的元素 * @Return: 无 * @Author: Carlos */void Push(BiTree* a,BiTree elem){ //指针进栈 a[++top]=elem;}/** * @Description: 前序遍历应用的弹栈函数 * @Param: 无 * @Return: 无 * @Author: Carlos */void Pop( ){ if (top==-1) { return; } top--;}/** * @Description: 显示函数 * @Param: BiTree elem 指向树的指针 * @Return: 无 * @Author: Carlos */void PrintBiT(BiTree elem){ printf("%d ",elem->data);}/** * @Description: 拿到栈顶元素 * @Param: BiTree*a 指针数组 * @Return: 栈顶元素的地址 * @Author: Carlos */BiTree GetTop(BiTree*a){ return a[top];}/** * @Description: 中序遍历非递归算法，先左，而后回退，而后右。从根结点开始，遍历左孩子同时压栈，当遍历完结，阐明以后遍历的结点没有左孩子， * 从栈中取出来调用操作函数，而后拜访该结点的右孩子，持续以上重复性的操作 * @Return: 栈顶元素的地址 * @Author: Carlos */void InOrderTraverse1(BiTree Tree){ //定义一个程序栈 BiTree a[20]; //长期指针 BiTree p; //根结点进栈 Push(a, Tree); //top!=-1阐明栈内不为空，程序持续运行 while (top!=-1) { //始终取栈顶元素，且不能为NULL while ((p=GetTop(a)) &&p){ //将该结点的左孩子进栈，如果没有左孩子，NULL进栈 Push(a, p->lchild); } //跳出循环，栈顶元素必定为NULL，将NULL弹栈。 打印的第一个元素没有右孩子，所以也会Pop掉，再取栈顶元素就是第一个元素的父节点 Pop(); if (top!=-1) { //取栈顶元素 p=GetTop(a); //栈顶元素弹栈 Pop(); //遍历完所有左孩子之后，打印栈顶的元素。 PrintBiT(p); //将p指向的结点的右孩子进栈 Push(a, p->rchild); } }}/** * @Description: 中序遍历非递归算法。中序遍历过程中，只需将每个结点的左子树压栈即可，右子树不须要压栈。 * 当结点的左子树遍历实现后，只须要以栈顶结点的右孩子为根结点，持续循环遍历即可 * @Param: 无 * @Return: 栈顶元素的地址 * @Author: Carlos */void InOrderTraverse2(BiTree Tree){ //定义一个程序栈 BiTree a[20]; //长期指针 BiTree p; p=Tree; //当p为NULL或者栈为空时，表明树遍历实现 while (p || top!=-1) { //如果p不为NULL，将其压栈并遍历其左子树 if (p) { Push(a, p); p=p->lchild; } //如果p==NULL，表明左子树遍历实现，须要遍历上一层结点的右子树 弹出时顺便拜访右子树 else{ p=GetTop(a); Pop(); PrintBiT(p); p=p->rchild; } }}int main(){ BiTree Tree; CreateBiTree(&Tree); printf("中序遍历: \r\n"); InOrderTraverse2(Tree); DBG_PRINTF("123456\r\n"); return 0;}后序遍历
后序遍历规定
二叉树后序遍历的实现思维是：1.拜访左子树；2.拜访右子树；3.实现该节点的左右子树的拜访后，再拜访该节点。即考查到一个节点后，将其暂存，遍历完左右子树后，再输入该节点的值。(左右根)
后序遍历举例
如上图中，对此二叉树进行后序遍历的操作过程为：
从根节点 1 开始，遍历该节点的左子树（以节点 2 为根节点）；
1.遍历节点 2 的左子树（以节点 4 为根节点）；
2.因为节点 4 既没有左子树，也没有右子树，此时拜访该节点中的元素 4，并回退到节点 2 ，遍历节点 2 的右子树（以 5 为根节点）；
3.因为节点 5 无左右子树，因而能够拜访节点 5 ，并且此时节点 2 的左右子树也遍历实现，因而也能够拜访节点 2；
4.此时回退到节点 1 ，开始遍历节点 1 的右子树（以节点 3 为根节点）；
5.遍历节点 3 的左子树（以节点 6 为根节点）；
6.因为节点 6 无左右子树，因而拜访节点 6，并回退到节点 3，开始遍历节点 3 的右子树（以节点 7 为根节点）；
7.因为节点 7 无左右子树，因而拜访节点 7，并且节点 3 的左右子树也遍历实现，能够拜访节点 3；节点 1 的左右子树也遍历实现，能够拜访节点 1；
由此，对上图 中二叉树进行后序遍历的后果为：4 5 2 6 7 3 1
后序遍历代码（递归）
/* * @Description: 二叉树的后序遍历（递归） * @Version: V1.0 * @Autor: Carlos * @Date: 2020-05-18 16:23:57 * @LastEditors: Carlos * @LastEditTime: 2020-05-30 17:29:38 */ #include <stdio.h>#include <string.h>#include <stdlib.h>#define TElemType int//结构结点的构造体typedef struct BiTNode{ //数据域 TElemType data; //左右孩子指针 struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;/*** @Description: 初始化树* @Param: BiTree *T 构造体指针* @Return: 无* @Author: Carlos*/void CreateBiTree(BiTree *T){ *T=(BiTree)malloc(sizeof(BiTNode)); (*T)->data=1; (*T)->lchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->rchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->lchild->data=2; (*T)->lchild->lchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->lchild->rchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->lchild->rchild->data=5; (*T)->lchild->rchild->lchild=NULL; (*T)->lchild->rchild->rchild=NULL; (*T)->rchild->data=3; (*T)->rchild->lchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->rchild->lchild->data=6; (*T)->rchild->lchild->lchild=NULL; (*T)->rchild->lchild->rchild=NULL; (*T)->rchild->rchild=(BiTree)malloc(sizeof(BiTNode)); (*T)->rchild->rchild->data=7; (*T)->rchild->rchild->lchild=NULL; (*T)->rchild->rchild->rchild=NULL; (*T)->lchild->lchild->data=4; (*T)->lchild->lchild->lchild=NULL; (*T)->lchild->lchild->rchild=NULL;}/*** @Description: 显示函数* @Param: BiTree elem 指向树的构造体指针* @Return: 无* @Author: Carlos*/void PrintBiT(BiTree elem){ printf("%d ",elem->data);}/*** @Description: 先序遍历* @Param: BiTree T 指针数组，寄存各个节点的指针* @Return: 无* @Author: Carlos*/void PreOrderTraverse(BiTree T){ if (T) { PreOrderTraverse(T->lchild);//拜访该结点的左孩子 PreOrderTraverse(T->rchild);//拜访该结点的右孩子 PrintBiT(T);//调用操作结点数据的函数办法 } //如果结点为空，返回上一层 return;}int main() { BiTree Tree; CreateBiTree(&Tree); printf("后序遍历: \n"); PreOrderTraverse(Tree);}后序遍历代码（非递归）
/* * @Description: 二叉树的后序遍历（非递归） * @Version: V1.0 * @Autor: Carlos * @Date: 2020-05-18 16:23:57 * @LastEditors: Carlos * @LastEditTime: 2020-05-18 16:24:29 */ #include <stdio.h>#include <string.h>#include <stdlib.h>#define TElemType int//top变量时刻示意栈顶元素所在位置int top=-1;//结构结点的构造体typedef struct BiTNode{ //数据域 TElemType data; //左右孩子指针 struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;/** * @Description: 初始化树 * @Param: BiTree *T 构造体指针数组 * @Return: 无 * @Author: Carlos */void CreateBiTree(BiTree *T){ *T=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->data=1; (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->lchild->data=2; (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->lchild->rchild->data=5; (*T)->lchild->rchild->lchild=NULL; (*T)->lchild->rchild->rchild=NULL; (*T)->rchild->data=3; (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->rchild->lchild->data=6; (*T)->rchild->lchild->lchild=NULL; (*T)->rchild->lchild->rchild=NULL; (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->rchild->rchild->data=7; (*T)->rchild->rchild->lchild=NULL; (*T)->rchild->rchild->rchild=NULL; (*T)->lchild->lchild->data=4; (*T)->lchild->lchild->lchild=NULL; (*T)->lchild->lchild->rchild=NULL;}/** * @Description: 后序遍历应用的弹栈函数 * @Param: 无 * @Return: 无 * @Author: Carlos */void Pop( ){ if (top==-1) { return ; } top--;}/** * @Description: 显示函数 * @Param: 无 * @Return: 无 * @Author: Carlos */void PrintBiT(BiTree elem){ printf("%d ",elem->data);}//减少左右子树的拜访标记typedef struct SNode{ BiTree p; int tag;}SNode;/** * @Description: 后序遍历应用的进栈函数 * @Param: SNode *a 指向树和标记位的构造体的指针 BiTree sdata 进栈的元素 * @Return: 无 * @Author: Carlos */void Push(SNode *a,SNode sdata){ a[++top]=sdata;}/** * @Description: 后序遍历非递归算法。后序遍历是在遍历完以后结点的左右孩子之后，才调用操作函数，所以须要在操作结点进栈时，为每个结点装备一个标记位。 * 当遍历该结点的左孩子时，设置以后结点的标记位为 0，进栈；当要遍历该结点的右孩子时，设置以后结点的标记位为 1，进栈。这样，当遍历实现，该结点弹栈时， * 查看该结点的标记位的值：如果是 0，示意该结点的右孩子还没有遍历；反之如果是 1，阐明该结点的左右孩子都遍历实现，能够调用操作函数。 * @Param: 构造体指针数组 * @Return: 无 * @Author: Carlos */void PostOrderTraverse(BiTree Tree){ //定义一个程序栈 SNode a[20]; //长期指针 BiTree p; int tag; SNode sdata; p=Tree; while (p||top!=-1) { //左孩子进栈 while (p) { //为该结点入栈做筹备 sdata.p=p; //因为遍历是左孩子，设置标记位为0 sdata.tag=0; //压栈 Push(a, sdata); //以该结点为根结点，遍历左孩子 p=p->lchild; } //取栈顶元素 取左孩子的父节点 sdata=a[top]; //栈顶元素弹栈 Pop(); p=sdata.p; tag=sdata.tag; //右孩子进栈 //如果tag==0，阐明该结点还没有遍历它的右孩子 if (tag==0) { sdata.p=p; sdata.tag=1; //更改该结点的标记位，从新压栈 Push(a, sdata); //以该结点的右孩子为根结点，反复循环 p=p->rchild; } //如果取出来的栈顶元素的tag==1，阐明此结点左右子树都遍历完了，能够调用操作函数了 else{ PrintBiT(p); p=NULL; } }}int main(){ BiTree Tree; CreateBiTree(&Tree); printf("后序遍历: \n"); PostOrderTraverse(Tree);}档次遍历
档次遍历规定
依照二叉树中的档次从左到右顺次遍历每层中的结点。通过应用队列的数据结构，从树的根结点开始，顺次将其左孩子和右孩子入队。而后每次队列中一个结点出队，都将其左孩子和右孩子入队，直到树中所有结点都出队，出队结点的先后顺序就是档次遍历的最终后果。
档次遍历举例
例如，档次遍历如上图中的二叉树：
1.根结点 1 入队；
2.根结点 1 出队，出队的同时，将左孩子 2 和右孩子 3 别离入队；
3.队头结点 2 出队，出队的同时，将结点 2 的左孩子 4 和右孩子 5 顺次入队；
4.队头结点 3 出队，出队的同时，将结点 3 的左孩子 6 和右孩子 7 顺次入队；
5.一直地循环，直至队列内为空。
档次遍历代码
/* * @Description: 二叉树的档次遍历 * @Version: V1.0 * @Autor: Carlos * @Date: 2020-05-20 14:52:38 * @LastEditors: Carlos * @LastEditTime: 2020-05-30 17:41:48 */ #include <stdio.h>#include <stdlib.h>#define TElemType int//初始化队头和队尾指针开始时都为0int front=0,rear=0;typedef struct BiTNode{ //数据域 TElemType data; //左右孩子指针 struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;//采纳程序队列，初始化创立队列数组BiTree a[20];/** * @Description: 初始化二叉树 * @Param: BiTree *T 二叉树的构造体指针数组 * @Return: 无 * @Author: Carlos */void CreateBiTree(BiTree *T){ *T=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->data=1; (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->lchild->data=2; (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->lchild->rchild->data=5; (*T)->lchild->rchild->lchild=NULL; (*T)->lchild->rchild->rchild=NULL; (*T)->rchild->data=3; (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->rchild->lchild->data=6; (*T)->rchild->lchild->lchild=NULL; (*T)->rchild->lchild->rchild=NULL; (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->rchild->rchild->data=7; (*T)->rchild->rchild->lchild=NULL; (*T)->rchild->rchild->rchild=NULL; (*T)->lchild->lchild->data=4; (*T)->lchild->lchild->lchild=NULL; (*T)->lchild->lchild->rchild=NULL;}/** * @Description: 入队 * @Param: BiTree *a 二叉树构造体指针 BiTree node 入队的节点 * @Return: 无 * @Author: Carlos */void EnQueue(BiTree *a,BiTree node){ a[rear++]=node;}/** * @Description: 出队 * @Param: BiTree *node 二叉树构造体指针数组 * @Return: 构造体指针 * @Author: Carlos */BiTree DeQueue(BiTree *node){ return a[front++];}/** * @Description: 二叉树输入函数 * @Param: BiTree node 输入的节点 * @Return: 无 * @Author: Carlos */void displayNode(BiTree node){ printf("%d ",node->data);}int main() { BiTree tree; //初始化二叉树 CreateBiTree(&tree); BiTree p; //根结点入队 EnQueue(a, tree); //当队头和队尾相等时，示意队列为空 while(front<rear) { //队头结点出队 p=DeQueue(a); displayNode(p); //将队头结点的左右孩子顺次入队 if (p->lchild!=NULL) { EnQueue(a, p->lchild); } if (p->rchild!=NULL) { EnQueue(a, p->rchild); } } return 0;} 总结：其实不论是哪种遍历形式，咱们最终的目标就是拜访所有的树（子树）的根节点，左孩子，右孩子。那么在拜访的过程中，必定不能一次拜访并打印结束。这个时候就须要栈来暂存咱们曾经拜访过的元素。在须要的时候将其打印进去即可（咱们以左孩子节点为基准，先序遍历是在拜访左孩子节点之前打印节点，中序遍历是在左孩子节点压栈之后打印节点，后序遍历是在拜访完左右孩子节点之后打印节点）。
文中代码均已测试，有任何意见或者倡议均可分割我。欢送学习交换！
如果感觉写的不错，请点个赞再走，谢谢！
如遇到排版错乱的问题，能够通过以下链接拜访我的CSDN。
**CSDN:[CSDN搜寻“嵌入式与Linux那些事”]