乐趣区

关于c:带你一文看懂二叉树的先中后序遍历以及层次遍历图解递归非递归代码实现

jiezi

@[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 int
int 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
// 初始化队头和队尾指针开始时都为 0
int 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 那些事”]

退出移动版