二叉树的非递归遍历

思路

无论是前中后序还是层序，均是需要借助栈来进行遍历，其中前中后序遍历均是模拟递归的过程。
递归遍历其实是函数在调用过程中调用自身，调用自身时将该层函数压栈，执行新的一层，以前序遍历为例

void BTreePrevOrder(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    printf("%d ", root->_data);
    BTreePrevOrder(root->_left);
    BTreePrevOrder(root->_right);
}

当函数执行BTreePrevOrder(root->_left);时，将开辟一片新的空间执行新的一层函数，上层函数将被压栈在新的这层函数执行结束后执行。
一层一层压栈、出栈实现了遍历的递归实现，而非递归就是模拟这个压栈、出栈的过程，下面就借助栈实现以下这个过程

接下来看一下访问节点的时机

完整的关于二叉树的代码下载

二叉树代码github地址
执行结果

前序遍历

前序遍历在入栈前访问，下面是实现代码

void BTreePrevOrderNonR(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    Stack* s = StackInit();
    BTNode* cur = root;
    while (cur || (StackEmpty(s) != 0))
    {
        while (cur)
        {
            printf("%d ", cur->_data);
            StackPush(s, cur);
            cur = cur->_left;
        }
        BTNode* front = StackTop(s);
        StackPop(s);
        cur = front->_right;
    }
    StackDestroy(s);
    printf("\n");
}

中序遍历

出栈时访问节点，不细讲

void BTreeInOrderNonR(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    Stack* s = StackInit();
    BTNode* cur = root;
    while (cur || (StackEmpty(s) != 0))
    {
        while (cur)
        {
            StackPush(s, cur);
            cur = cur->_left;
        }
        BTNode* front = StackTop(s);
        StackPop(s);
        printf("%d ", front->_data);
        cur = front->_right;
    }
    StackDestroy(s);
    printf("\n");
}

后序遍历

后序是最难控制的，访问条件和前序后序都不一样，后序访问顺序是左右根，出栈访问，同时需要记录访问的节点当做标记
和前序中序遍历不同，前中序遍历时，先出栈再判断右为不为空，不为空入栈，后序不同的地方是先判断右为不为空或者是否被访问过，如果没有，将右节点入栈，并不出栈父亲节点，否则才出栈父亲节点访问
因此只有在右节点为空或者右节点为上一个出栈的节点，则出栈目前的节点
同样是出栈访问节点，但是后序需要严格的条件才能出栈，总结一下：

1.右节点为空，可出栈
2.右节点不为空，但是为上一个访问的节点，可出栈

void BTreePostOrderNonR(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    Stack* s = StackInit();
    BTNode* cur = root;
    BTNode* last = NULL;//最后一个访问的节点
    while (cur || (StackEmpty(s) != 0))
    {
        while (cur)
        {
            StackPush(s, cur);
            cur = cur->_left;
        }
        BTNode* front = StackTop(s);
        if ((front->_right == NULL) || (front->_right == last))
        {
            printf("%d ", front->_data);
            StackPop(s);
            last = front;
        }
        else
        {
            cur = front->_right;
        }
    }
    printf("\n");
}

层序遍历

层序遍历借助的不是栈，栈的结构并不适合层序遍历，因为栈先进后出，而我们需要先进的先出，队列就很适合
思路是将头结点入队列，出栈的时候先访问，然后将出栈节点的左右节点入队列（如果左右节点不为空的话，为空不如队列），直至队列为空

void BTreePostOrderNonR(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    Stack* s = StackInit();
    BTNode* cur = root;
    BTNode* last = NULL;//最后一个访问的节点
    while (cur || (StackEmpty(s) != 0))
    {
        while (cur)
        {
            StackPush(s, cur);
            cur = cur->_left;
        }
        BTNode* front = StackTop(s);
        if ((front->_right == NULL) || (front->_right == last))
        {
            printf("%d ", front->_data);
            StackPop(s);
            last = front;
        }
        else
        {
            cur = front->_right;
        }
    }
    printf("\n");
}

本文使用的相关树结构体，队列，栈等结构代码

树结构体

typedef int BTreeDataType;

typedef struct BinaryTreeNode
{
    struct BinaryTreeNode* _left;
    struct BinaryTreeNode* _right;
    BTreeDataType _data;
}BTNode;

栈

使用前需要将STDataType的类型改成BTNode*
栈的头文件github地址

队列

使用前需要将QueueDataType的类型改成BTNode*
队列的头文件github地址