有根树相关知识总结之遍历二叉树（C语言描述）

前言：二叉树的遍历方法主要有前序遍历、中序遍历、后续遍历和层序遍历。各算法又可分为递归算法和非递归算法两种，本文将进行区分讨论。从本质上来说，二叉树的深度优先搜索包括了前序遍历、中序遍历和后续遍历；广度优先搜索即是层序遍历。

1. 二叉树的数据结构定义（C语言版）

typedef struct BiNode
{
    char m_data;//数据域
    struct BiNode *plChild;//左孩子节点
    struct BiNode *prChild;//右孩子节点
}BiNode,*BiTree;

2.二叉树的前序遍历（递归版本）

算法思想：

因为遍历过程对每个节点都会访问一次，包括那些为空的节点。递归算法主要需要考虑递归出口的问题，如果二叉树节点为NULL（如最左下节点的左孩子即为空），则return即可；

源码描述：

void PreOrderWalkTree(BiNode *pRoot)
{
    if (pRoot==NULL) //递归出口，节点为NULL，则返回
        return; 
    else
    {
        printf("%c",pRoot->m_data);//遍历根节点
        PreOrderWalkTree(pRoot->plChild);//遍历左子树
        PreOrderWalkTree(pRoot->prChild);//遍历右子树
    }
    printf("\n");
}

3.二叉树的前序遍历（非递归版本）、

算法思想：

前序遍历即对每个节点首先将访问根节点，然后访问左子树，最后访问右子树。由于对于每个节点都遵循这样的顺序，最后访问右子树，所以必须先将根节点保存，即入栈；由于最先访问根节点，所以在入栈的时候就可以访问它。访问完左子树，即可出栈并获取其右子树，进而对右子树进行访问。

源码描述：

void PreOrderWalkTree(BiNode *pRoot)
{
    BiNodeStack NodeStack;
    InitStack(&NodeStack);//创建节点类型的栈

    BiNode *pCurNode=pRoot;//当前节点
    //1. 进入主循环
    while (pCurNode!=NULL||!IsStackEmpty(&NodeStack))
    {
        while (pCurNode)
        {
            Visit(pCurNode);//访问当前节点
            PushElement(&NodeStack,pCurNode);//将当前节点入栈
            pCurNode=pCurNode->plChild;//沿着一条路走到最左下节点,即碰到左孩子为空
        }

        if (!IsStackEmpty(&NodeStack))
        {
            pCurNode=PopElement(&NodeStack);//碰到左孩子为空就要出栈，此时栈顶元素是当前节点
            pCurNode=pCurNode->prChild;
        }
    }
}

4.二叉树的中序遍历（递归版本）

算法思想：

源码描述：

void InOrderWalkTree(BiNode *pRoot)
{
    if (pRoot==NULL) //递归出口，节点为NULL，则返回
        return; 
    else
    {
        PreOrderWalkTree(pRoot->plChild);//遍历左子树
        printf("%c",pRoot->m_data);//遍历根节点
        PreOrderWalkTree(pRoot->prChild);//遍历右子树
    }
    printf("\n");
}

5.二叉树的中序遍历（非递归版本）

算法思想

中序遍历是先访问节点的左子树，然后访问根节点，再访问右子树。和前序遍历类似，由于右子树是最后访问，所以必须要保存根节点以在左子树和根节点都访问完了之后获取右子树进而对其访问。具体的说，需要将根节点沿着左子树路径入栈，碰到左孩子为空–>出栈–>访问根节点–>获取右孩子。

源码描述：

void InOderWalkTree(BiNode *pRoot)
{
    BiNodeStack NodeStack;
    InitStack(&NodeStack);//创建节点类型的栈

    BiNode *pCurNode=pRoot;
    while (pCurNode!=NULL||!IsStackEmpty(&NodeStack))
    {
        while (pCurNode)
        {
            PushElement(&NodeStack,pCurNode);//当前节点入栈
            pCurNode=pCurNode->plChild;
        }//直到碰到左孩子为空为止

        if (!IsStackEmpty(&NodeStack))
        {
            pCurNode=PopElement(&NodeStack);
            Visit(pCurNode);//出栈的时候访问节点
            pCurNode=pCurNode->prChild;//处理右孩子
        }
    }
}

6.二叉树的后序遍历（递归版本）

算法思想：

源码描述：

void PostOrderWalkTree(BiNode *pRoot)
{
    if (pRoot==NULL) //递归出口，节点为NULL，则返回
        return; 
    else
    {
        PreOrderWalkTree(pRoot->plChild);//遍历左子树
        PreOrderWalkTree(pRoot->prChild);//遍历右子树
        printf("%c",pRoot->m_data);//遍历根节点
    }
    printf("\n");
}

7.二叉树的后序遍历（非递归版本）

算法思想

前序遍历和中序都是最后访问右子树所以需要借助栈保存根节点，后序遍历是先访问左子树，其次访问右子树，最后访问根节点。由于是先左子树后右子树，所以仍然需要保存根节点以获取右子树。另一方面，当左子树为空时，此时根节点位于栈顶，需要判断右子树是否已经被访问过，如果右子树没有被访问，则根节点不出栈，继续访问右子树；如果右子树已经被访问，则根节点出栈，访问根节点。所以，根节点有两次位于栈顶，第二次时才出栈。

源码描述：

void PostOderWalkTree(BiNode *pRoot)
{
    BiNodeStack NodeStack;
    InitStack(&NodeStack);//创建节点类型的栈
    int i=;
    bool brChlidNotProced[MaxStackSize];

    BiNode *pCurNode=pRoot;
    while (pCurNode!=NULL||!IsStackEmpty(&NodeStack))
    {
        while (pCurNode)
        {
            PushElement(&NodeStack,pCurNode);//当前节点入栈
            brChlidNotProced[i++]=false;//表示右孩子还没有处理
            pCurNode=pCurNode->plChild;
        }//直到碰到左孩子为空为止

        if (!brChlidNotProced[i-]) //右孩子没有被处理
        {
            pCurNode=GetStackTop(&NodeStack);//获取栈顶元素，未出栈
            pCurNode=pCurNode->prChild;
            brChlidNotProced[i-]=true;
        }
        else
        {
            pCurNode=PopElement(&NodeStack);//右子树已经处理，可以出栈
            Visit(pCurNode);//访问
            i--;
            pCurNode=NULL;//栈顶元素弹出并访问后，还要进行一次出栈操作
        }
    }
}

8.二叉树的层序遍历（非递归版本）

算法思想：

由于对于每一层都需要从左向右遍历节点，因此有“先入先出”的意思，采用队列进行描述。首先将根节点入队列，其次进入主循环，当前节点出队列并访问，如果其左孩子不为空，则左孩子入队列，如果右孩子不为空，则右孩子入队列。

源码描述：

void LayerOderWalkTree(BiNode *pRoot)
{
    BiNodeQueue NodeQueue;
    InitQueue(&NodeQueue);//初始化队列

    BiNode *pCurNode=pRoot;
    EnQueue(&NodeQueue,pCurNode);//根节点入队列

    //进入主循环，直至队列为空
    while (!IsQueueEmpty(&NodeQueue))
    {
        pCurNode=DeQueue(&NodeQueue);
        Visit(pCurNode);//访问当前节点

        if (pCurNode->plChild!=NULL) //左孩子不为空，则进队列
        {
            EnQueue(&NodeQueue,pCurNode->plChild);
        }

        if (pCurNode->prChild!=NULL) //右孩子不为空，则进队列
        {
            EnQueue(&NodeQueue,pCurNode->prChild);
        }
    }
}

总结：以上四种遍历算法的实现均采用教科书上的思想，即：

前序遍历：当前节点是在入栈的时候被访问；
中序遍历：当前节点是在出栈的时候被访问；
后续遍历：当前节点是在第二次在栈顶的时候被访问；有两次出现的栈顶，第一次是右子树未处理的时候，第二次是右子树处理完了的时候。因此需要标记位bFlag用于标识右子树是否被处理：

3.1 bFlag=1,右子树未处理->不出栈，处理右子树;

3.2 bFlag=0,右子树已处理->出栈，访问当前节点;
层序遍历：当前节点出队列的时候被访问；同时将其不为空的孩子节点入队列。

树的深度优先搜索和广度优先搜索：

树的深度优先搜索是指首先从树的根节点出发，然后选择一个与其相邻的且未被访问的顶点（孩子节点），依次进行，直到某个节点与其相邻的所有节点都已经被访问或者为空为止。然后退回到已经被访问的顶点序列中最后一个拥有未被访问的邻接节点的节点。直至所有节点均已经被访问。
树的广度优先搜索是指首先从树的根节点出发，遍历与其相邻的所有节点，然后再遍历这些邻接节点的邻接节点，依次进行下去，直至所有节点均已经被访问。

有根树相关知识总结之遍历二叉树（C语言描述）

继续阅读

JAVA高效编程指南

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

【数据结构】医院选址

CRC32和CRC8校验代码，C语言版

241 Different Ways to Add Parentheses（C代码版）

[转]ISUP信令的IAM消息详细内容

C语言：初学者必定看懂的注释！！！猴子吃桃问题。猴子第一天摘下若干个桃子，每天都吃了前一天剩下的一半零一个，到第10天早上想再吃的时候，就剩下一个桃子. 求第一天共摘多少个桃子。

[转]九大排序算法——C语言实现及详解

笔试面试题目：滑动窗口(二)

while 循环、do- while 循环和 for 循环之间的那点事C语言自学之三种循环比较

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

结构体：typedef与struct的区别

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器

hdu7108哈希