二叉树的非递归遍历，必须借助栈的辅助。必须采用栈的这种先进后出的特性。

算法实现思路：

• 我们先将根节点压入栈中。然后往外弹出元素。直到栈中元素弹完为止。
• 1、将根节点压入栈中。（但是压入栈中，并不知简单的将根节点压入栈中就完事，我们必须引入一个标记信息。Flag：标识这个节点第几次压入栈中。）(标识：每个结点都要往栈中压两次。第二次再弹出来时，我们取数据。第一次压入栈中，我们将其标注为FALSE，标注是否取值。)
• 所有节点在第一次弹出时都是false。

重新第一步：

• 第一步：将根节点压入栈中，将标志位只为FALSE。
• 第二步：启动while循环：循环条件：栈不为空。
  • 先从栈中弹出栈顶元素。判断元素的标志位：
    • 如果标志位为True则：
      • 该节点值弹出：出栈，然后当前本次循环结束。
  • 如果标志位为false则：

     

    • 将该节点的左子树和右子树压入栈中。（先判断是否为空）
    • 此时入栈就要由顺序要求了。如果想要先序遍历，那么就需要反序压入。确保从栈中弹出元素时，先根后左右。
    • 根节点是二次入栈，将该标志位置为True。
• 继续执行循环：
  • A先出栈，然后是B，B为false,将左右节点压入栈中，将标志位改为True。
  • 先入B，然后再入C。然后结束本次循环。
  • 先弹出B，然后C的标识位只为True，然后压入DE。不断循环。

我们继续采用前面是用的栈的代码。 

#pragma once#include
#include#ifdef __cplusplus
extern "C"{
#endif#define MAX 1024//顺序栈数据结构struct SStack{void *data[MAX]; //存放数据的数组int size;//栈中元素的个数};typedef void * SeqStack;//数组高下标的位置当做栈顶，因为不需要移动数组中的元素在插入和删除中//初始化SeqStack Init_SeqStack();//入栈void Push_SeqStack(SeqStack stack, void *data);//出栈void Pop_SeqStack(SeqStack stack);//获得栈顶元素void *Top_SeqStack(SeqStack stack);//获得栈的大小int Size_SeqStack(SeqStack stack);//销毁栈void Destroy_SeqStack(SeqStack stack);#ifdef __cplusplus
}
#endif

采用栈的辅助

#include"SeqStack.h"//初始化
SeqStack Init_SeqStack()
{struct SStack *stack = malloc(sizeof(struct SStack));if (NULL == stack){return NULL;}//memset(stack->data, 0, sizeof(struct SStack));stack->size = 0;for (int i = 0; i < MAX; ++i){stack->data[i] = NULL;}return stack;
}
//入栈
void Push_SeqStack(SeqStack stack, void *data)
{if (NULL == stack){return;}if (NULL == data){return;}struct SStack *s = (struct SStack *)stack;if (s->size == MAX){return;}s->data[s->size] = data;s->size++;
}
//出栈
void Pop_SeqStack(SeqStack stack)
{if (NULL == stack){return;}struct SStack *s = (struct SStack *)stack;if (s->size == 0){return;}s->data[s->size - 1] = NULL;s->size--;
}
//获得栈顶元素
void *Top_SeqStack(SeqStack stack)
{if (NULL == stack){return NULL;}struct SStack *s = (struct SStack *)stack;if (s->size == 0){return NULL;}return s->data[s->size - 1];}
//获得栈的大小
int Size_SeqStack(SeqStack stack)
{if (NULL == stack){return -1;}struct SStack *s = (struct SStack *)stack;return s->size;
}
//销毁栈
void Destroy_SeqStack(SeqStack stack)
{if (NULL == stack){return;}free(stack);
}

为了实现二叉树的非递归遍历：

节点结构体：除了节点，还需要一个标识位。

struct Info
{struct BiNode *node;bool flag;
};

 因为引入bool量，所以引用：

struct BiNode
{char ch;struct BiNode *lchild;struct BiNode *rchild;
};

初始化根节点：返回根节点，然后输入为

struct Info* createInfo(struct BiNode *node, bool flag)
{struct Info *info = malloc(sizeof(struct Info));info->flag = flag;info->node = node;return info;
}

初始化栈：

void nonRecursion(struct BiNode *root)
{//初始化栈SeqStack stack = Init_SeqStack();//先把根节点压入栈中Push_SeqStack(stack, createInfo(root, false));while (Size_SeqStack(stack) > 0){//获得栈顶元素	struct Info *info = (struct Info *)Top_SeqStack(stack);//弹出栈顶元素Pop_SeqStack(stack);if (info->flag){printf("%c ",info->node->ch);free(info);continue;}// 这个地方的压栈顺序，就影响了后续的输出顺序。压入栈顺序不同，最后出栈顺序也不同。//将根节压入栈中info->flag = true;Push_SeqStack(stack, info);//将右子树压入栈中if (info->node->rchild != NULL){Push_SeqStack(stack, createInfo(info->node->rchild, false));}//将左子树压入栈中if (info->node->lchild != NULL){Push_SeqStack(stack, createInfo(info->node->lchild, false));}}//销毁栈Destroy_SeqStack(stack);
}

 整体实现：

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include"SeqStack.h"struct BiNode
{char ch;struct BiNode *lchild;struct BiNode *rchild;
};struct Info
{struct BiNode *node;bool flag;
};struct Info* createInfo(struct BiNode *node, bool flag)
{struct Info *info = malloc(sizeof(struct Info));info->flag = flag;info->node = node;return info;
}void nonRecursion(struct BiNode *root)
{//初始化栈SeqStack stack = Init_SeqStack();//先把根节点压入栈中Push_SeqStack(stack, createInfo(root, false));while (Size_SeqStack(stack) > 0){//获得栈顶元素	struct Info *info = (struct Info *)Top_SeqStack(stack);//弹出栈顶元素Pop_SeqStack(stack);if (info->flag){printf("%c ",info->node->ch);free(info);continue;}//将根节压入栈中info->flag = true;Push_SeqStack(stack, info);//将右子树压入栈中if (info->node->rchild != NULL){Push_SeqStack(stack, createInfo(info->node->rchild, false));}//将左子树压入栈中if (info->node->lchild != NULL){Push_SeqStack(stack, createInfo(info->node->lchild, false));}}//销毁栈Destroy_SeqStack(stack);
}void test()
{struct BiNode nodeA = { 'A', NULL, NULL };struct BiNode nodeB = { 'B', NULL, NULL };struct BiNode nodeC = { 'C', NULL, NULL };struct BiNode nodeD = { 'D', NULL, NULL };struct BiNode nodeE = { 'E', NULL, NULL };struct BiNode nodeF = { 'F', NULL, NULL };struct BiNode nodeG = { 'G', NULL, NULL };struct BiNode nodeH = { 'H', NULL, NULL };nodeA.lchild = &nodeB;nodeA.rchild = &nodeF;nodeB.rchild = &nodeC;nodeC.lchild = &nodeD;nodeC.rchild = &nodeE;nodeF.rchild = &nodeG;nodeG.lchild = &nodeH;nonRecursion(&nodeA);}int main(){test();system("pause");return EXIT_SUCCESS;
}