二叉树前序、中序、后序（递归 / 非递归）遍历

前语

 二叉树的遍历是指按一定次序访问二叉树中的每一个结点，且每个节点仅被访问一次。

前序遍历

 若二叉树非空，则进行以下次序的遍历：
  根节点—>根节点的左子树—>根节点的右子树
  若要遍历左子树和右子树，仍然需要按照以上次序进行，所以前序遍历也是一个递归定义。

(1) 递归的前序遍历

//前序递归遍历
void PreOrder(BinTreeNode* pRoot)
{
    //根节点为空，直接返回
    if (pRoot == NULL)
        return;

    printf("%c ", pRoot->_data);//访问根节点
    PreOrder(pRoot->_left);//访问左子树
    PreOrder(pRoot->_right);//访问右子树
}

(2) 非递归前序遍历

 按照前序遍历的规则：访问根节点后，应根据根节点的left指针进入左子树进行遍历，遍历结束后在进入右子树进行遍历。那如果不使用递归算法时，访问根节点后，进入左子树遍历结束后，现在需要进入右子树，所以需要将右子树的结点信息保留下来，以便我后面遍历右子树使用。再有观察可以知道，根节点的右子树是遍历完整个左子树后，才去访问的，就发现了“ 先保存，后使用 ”，与我们所熟悉栈的特性“ 后进先出 ”一致，所以我们使用栈来保存右子树的信息。

分析步骤

1. 将根节点入栈，重复以下步骤
2. 访问栈顶元素（根节点），然后元素出栈
3. 将根节点的右子树入栈保存
4. 将根节点的左子树入栈保存（这样就再以左子树节点为根节点往下遍历重复）
5. 直至节点为NULL，栈为空，遍历结束

//非递归前序遍历
void PreOrderNor(BinTreeNode* pRoot)
{
    Stack s;
    BinTreeNode* cur = NULL;
    if (pRoot == NULL)
        return;
    InitStack(&s);
    //根节点入栈
    PushStack(&s, pRoot);
    //开始循环操作
    while (!EmptyStack(&s))
    {
        //访问栈顶元素(根节点)
        cur = TopStack(&s);
        printf("%c ", cur->_data);
        //根节点出栈
        PopStack(&s);
        //将根节点的右子树入栈(因为最后访问的右子树)
        if (cur->_right != NULL)
            PushStack(&s, cur->_right);
        //将根节点的左子树入栈
        if (cur->_left != NULL)
            PushStack(&s, cur->_left);
    }
}

中序遍历

 若二叉树非空，则进行以下次序的遍历：
  根节点的左子树—>根节点—>根节点的右子树

(1) 递归的中序遍历

void InOrder(BinTreeNode* pRoot)
{
    //根节点为空，直接返回
    if (pRoot == NULL)
        return;

    InOrder(pRoot->_left);//访问左子树
    printf("%c ", pRoot->_data);//访问根节点
    InOrder(pRoot->_right);//访问右子树
}

(2) 非递归的中序遍历

 中序遍历的第一个节点是最左侧的节点，所以需要遍历查找以cur为根的最左侧的结点（最左侧的节点无左孩子）。找到后循环跳出，取栈顶元素，因为没有左孩子，所以访问cur指向的根节点，然后遍历以cur为根的右子树。重复上述循环，直至根节点的左子树遍历完成后，栈为空，要进入根节点的右子树遍历，此时就断定大的循环条件不应该和前序遍历相同。
 因此应该再加一个条件和它是或的关系（二者至少一个成立就好），所以我们便发现比那里完左子树后和根节点后，虽然栈为空，但cur的指向不为空，且当二叉树都遍历结束后，cur为空、栈也为空，循环跳出，遍历结束。

//非递归的中序遍历：左子树-->根-->右子树
//--->中序遍历的便利的第一个节点是最左下的结点
//因此需要找最坐下的节点，并将查找最坐下根节点路径上的结点压入栈中保存起来
void InOrderNor(BinTreeNode* pRoot)
{
    Stack s;
    BinTreeNode* cur = NULL;
    if (pRoot == NULL)
        return;
    InitStack(&s);
    cur = pRoot;
    while (!EmptyStack(&s) || cur)
    {
        //1.找最左下的结点-->需要将所经过路径的结点压入栈中保存-->最左下的根节点没有左孩子
        while (cur)
        {
            PushStack(&s, cur);
            cur = cur->_left;
        }
        //2.取栈顶元素，遍历以cur为根的节点
        cur = TopStack(&s);
        PopStack(&s);
        //遍历以cur为根的二叉树的根节点
        printf("%c ", cur->_data);
        //遍历以cur为根的二叉树的左节点
        cur = cur->_right;
    }
}

后序遍历

 若二叉树非空，则进行以下次序的遍历：
  根节点的左子树—>根节点的右子树—>根节点

(1) 递归的后序遍历

//递归的后序遍历
void PostOrder(BinTreeNode* pRoot)
{
    if (pRoot == NULL)
        return;

    PostOrder(pRoot->_left);
    PostOrder(pRoot->_right);
    printf("%c ", pRoot->_data);
}

(2) 非递归的后序遍历

 后序遍历的第一个节点也是最左侧的节点（左孩子为空）。要先找到最左侧的元素并保存其所经路径的所有节点，以便于后面的遍历。
 只有在遍历完左子树和右子树后，才能访问根节点。所以如何判断是够遍历完左右子树成为关键。因此我们会想到设置一个标志pFlag指向最近的被遍历的节点。当栈顶指针指向的元素的右子树（因为相对于左右子树来说，只要访问过右子树，左子树一定已经访问过了）与标记指针相同时，该节点已经被遍历。

//非递归的后序遍历：左子树-->右子树-->根节点
void PostOrderNor(BinTreeNode* pRoot)
{
    BinTreeNode* cur = pRoot;
    BinTreeNode* pFlag = NULL;
    BinTreeNode* pTop = NULL;
    Stack s;
    if (pRoot == NULL)
        return;
    InitStack(&s);

    while (cur || !EmptyStack(&s))
    {
        //仍然是找最左下的元素（无左孩子），并保存其所经路径中最左侧的结点（入栈）
        while (cur)
        {
            PushStack(&s, cur);
            cur = cur->_left;
        }
        //pTop为根的二叉树的根节点，根节点不能直接遍历，除非pTop的右子树为空
        pTop = TopStack(&s);
        //如果它没有右孩子或者节点已遍历过了-->元素出栈，直接访问其根节点-->返回上一层
        //因为返回上一层后，会继续遍历其左右子树，会发生死循环，所以需要标记其最近访问的一个元素
        if (pTop->_right == NULL || pTop->_right == pFlag)
        {
            PopStack(&s);

            printf("%c ", pTop->_data);
            pFlag = pTop;
        }
        else  //如果它有右孩子-->以其右孩子为根节点重复以上步骤
            cur = pTop->_right;
    }
}

头文件、测试函数、代码运行结果

//BinTree.h
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

typedef char DataType;

typedef struct BinTreeNode
{
    struct BinTreeNode* _left;  //当前节点的左子树
    struct BinTreeNode* _right; //当前节点的右子树
    DataType _data; //当前节点的数据域
}BinTreeNode;


//test.c
void test()
{
    BinTreeNode* pRoot = NULL;
    char* str = "ABD###CE##F";
    CreateBinTree(&pRoot, str, strlen(str), '#');
    printf("递归前序遍历为:");
    PreOrderBinTree(pRoot);
    printf("\n非递归前序遍历为:");
    PreOrderNor(pRoot);
    printf("\n递归中序遍历为:");
    InOrderBinTree(pRoot);
    printf("\n非递归中序遍历为:");
    InOrderNor(pRoot);
    printf("\n递归后序遍历为:");
    PostOrderBinTree(pRoot);
    printf("\n非递归后序遍历为:");
    PostOrderNor(pRoot);
    printf("\n\n");
}