结合栈结构来实现二叉树的非递归遍历，首先将根节点入栈，然后对栈内元素进行循环，弹出栈顶元素，根据链表结点携带的标志位flag来判断是对于结点进行打印还是后续的入栈操作。入栈顺序决定着实际的遍历方式。

main.cpp

#include<iostream>
#include<stack>
using namespace std;struct BinaryNode
{char ch;BinaryNode* lchild;BinaryNode* rchild;
};pair<bool, BinaryNode*> makePair(BinaryNode* node)
{pair<bool, BinaryNode*> ret = make_pair(false, node);return ret;
}
void NoRecursion(BinaryNode* root)
{if (root == NULL){return;}pair<bool, BinaryNode*> flagroot = makePair(root);stack<pair<bool, BinaryNode*>> s;//根节点入栈s.push(flagroot);while (!s.empty()){pair<bool, BinaryNode*> node = s.top();s.pop();if (node.second == NULL){continue;}if (node.first == true){cout << node.second->ch << " ";}else{node.first = true;s.push(make_pair(false, node.second->rchild));s.push(make_pair(false, node.second->lchild));s.push(node);}}
}int main()
{//定义不同结点BinaryNode node1 = { 'A',NULL,NULL };BinaryNode node2 = { 'B',NULL,NULL };BinaryNode node3 = { 'C',NULL,NULL };BinaryNode node4 = { 'D',NULL,NULL };BinaryNode node5 = { 'E',NULL,NULL };BinaryNode node6 = { 'F',NULL,NULL };BinaryNode node7 = { 'G',NULL,NULL };BinaryNode node8 = { 'H',NULL,NULL };//建立结点关系node1.lchild = &node2;node1.rchild = &node6;node2.rchild = &node3;node3.lchild = &node4;node3.rchild = &node5;node6.rchild = &node7;node7.lchild = &node8;NoRecursion(&node1);system("pause");return 0;
}

main.c

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"LinkStack.h"#define MYFALSE 0
#define MYTRUE 1typedef struct BINARYNODE
{char data;struct BINARYNODE* lchild;struct BINARYNODE* rchild;}BinaryNode;//二叉树的递归遍历
void Recursion(BinaryNode* root)
{if (root == NULL){return;}Recursion(root->lchild);Recursion(root->rchild);printf("%c ", root->data);
}//二叉树的非递归遍历
typedef struct BITREESTACKNODE
{LinkNode node;BinaryNode* root;int flag;
}BiTreeStackNode;//创建栈中的结点
BiTreeStackNode* CreatBiTreeStackNode(BinaryNode* node,int flag)
{BiTreeStackNode* newnode = (BiTreeStackNode*)malloc(sizeof(BiTreeStackNode));newnode->root = node,newnode->flag = flag;return  newnode;
}void NonRecursion(BinaryNode* root)
{//创建栈LinkStack* stack = Init_LinkStack();//根结点入栈Push_LinkStack(stack, (LinkNode*)CreatBiTreeStackNode(root, MYFALSE));while (Size_LinkStack(stack) > 0){//弹出栈顶元素BiTreeStackNode* node =	Top_LinkStack(stack);Pop_LinkStack(stack);//弹出节点是否为空if (node->root == NULL){continue;}if (node->flag == MYTRUE){printf("%c ", node->root->data);}else{node->flag = MYTRUE;Push_LinkStack(stack, (LinkNode*)CreatBiTreeStackNode(node->root, MYTRUE));Push_LinkStack(stack, (LinkNode*)CreatBiTreeStackNode(node->root->rchild, MYFALSE));Push_LinkStack(stack, (LinkNode*)CreatBiTreeStackNode(node->root->lchild, MYFALSE));}}
}int main()
{//创建结点BinaryNode node1 = { 'A',NULL,NULL };BinaryNode node2 = { 'B',NULL,NULL };BinaryNode node3 = { 'C',NULL,NULL };BinaryNode node4 = { 'D',NULL,NULL };BinaryNode node5 = { 'E',NULL,NULL };BinaryNode node6 = { 'F',NULL,NULL };BinaryNode node7 = { 'G',NULL,NULL };BinaryNode node8 = { 'H',NULL,NULL };//建立结点关系node1.lchild = &node2;node1.rchild = &node6;node2.rchild = &node3;node3.lchild = &node4;node3.rchild = &node5;node6.rchild = &node7;node7.lchild = &node8;//二叉树的非递归打印NonRecursion(&node1);printf("\n");//二叉树的递归遍历Recursion(&node1);system("pause");return;
}

linkctack.c

#include"LinkStack.h"
//初始化函数
LinkStack* Init_LinkStack()
{LinkStack* stack = (LinkStack*)malloc(sizeof(LinkStack));stack->size = 0;stack->head.next = NULL;return stack;
}//入栈
void Push_LinkStack(LinkStack* stack, LinkNode* data)
{if (stack == NULL || data == NULL){return;}data->next = stack->head.next;stack->head.next = data;stack->size++;//大小的增加不要忘
}//出栈
void Pop_LinkStack(LinkStack* stack)
{if (stack == NULL){return;}if (stack->size == 0)//重点：没有元素的时候不需要操作了，无法出栈{return;}//第一个有效结点LinkNode* pDel = stack->head.next;stack->head.next = pDel->next;stack->size--;
}//返回栈顶元素
LinkNode* Top_LinkStack(LinkStack* stack)
{if (stack == NULL|| stack->size==0){return NULL;}return stack->head.next;
}//返回栈元素的个数
int Size_LinkStack(LinkStack* stack)
{if (stack == NULL){return -1;}return stack->size;
}//清空栈
void Clear_LinkStack(LinkStack* stack)
{if (stack == NULL){return;}stack->size = 0;stack->head.next = NULL;
}//销毁栈
void FreeSpace_LinkStack(LinkStack* stack)
{if (stack == NULL){return;}free(stack);
}

linkstack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//链式栈结点
typedef struct LINKNODE
{struct LINKNODE* next;
}LinkNode;//链式栈
typedef struct LINKSTACK
{LinkNode head;int size;
}LinkStack;//初始化函数
LinkStack* Init_LinkStack();//入栈
void Push_LinkStack(LinkStack* stack, LinkNode* data);//出栈
void Pop_LinkStack(LinkStack* stack);//返回栈顶元素
LinkNode* Top_LinkStack(LinkStack* stack);//返回栈元素的个数
int Size_LinkStack(LinkStack* stack);//清空栈
void Clear_LinkStack(LinkStack* stack);//销毁栈
void FreeSpace_LinkStack(LinkStack* stack);

测试结果：