1.将树的结点与一个FALSE标志位合一起压栈
2.判断栈中元素个数是否为空
3.栈顶元素出栈，将其标志位变成TRUE，同时将其左右树结点与FALSE标志位合一起压栈。
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "LinkStack.h"
#define MY_FALSE 0
#define MY_TRUE 1
//二叉树的结点
typedef struct BINARYNODE{
char ch;
struct BINARYNODE *lchild;
struct BINARYNODE *rchild;
}BinaryNode;
//二叉树结点的非递归遍历
typedef struct BITREESTACKNODE{
LinkNode node;
BinaryNode *root;
int flag;
}BitreeStackNode;
//非递归遍历
//创建栈中结点
BitreeStackNode* CreatBitreeStackNode(BinaryNode*node, int flag){
BitreeStackNode*newnode = (BitreeStackNode*)malloc(sizeof(BitreeStackNode));
newnode->flag = flag;
newnode->root = node;
return newnode;
}
void NonRecurision(BinaryNode*root){
LinkStack *stack = Init_LinkStack();
//把根结点扔到栈里
Push_LinkStack(stack, (LinkNode*)CreatBitreeStackNode(root, MY_FALSE));
while (Size_LinkStack(stack)>0)
{
BitreeStackNode*node = (BitreeStackNode*)Top_LinkStack(stack);
Pop_LinkStack(stack);
//判断弹出的结点是否为空
if (node->root==NULL)
{
continue;
}
if (node->flag==MY_TRUE)
{
printf("%c", node->root->ch);
}
else
{
//当前右结点入栈
Push_LinkStack(stack, (LinkNode*)CreatBitreeStackNode(node->root->rchild, MY_FALSE));
//当前左结点入栈
Push_LinkStack(stack, (LinkNode*)CreatBitreeStackNode(node->root->lchild, MY_FALSE));
node->flag = MY_TRUE;
//当前结点入栈
Push_LinkStack(stack, (LinkNode*)node);
}
}
}
void CreateBinaryTree(){
//生成结点
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;
//二叉树非递归打印
NonRecurision(&node1);
}
int main(void){
CreateBinaryTree();
printf("\n");
system("pause");
return 0;
}