#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
//定义一个二叉树结点结构体
typedef int ElemTpye;
typedef struct TreeNode
{
	ElemTpye data;
	struct TreeNode* left;
	struct TreeNode* right;
}TreeNode;
//创建结点
TreeNode* createTreenode(ElemTpye data)
{
	TreeNode* newnode = (TreeNode*)malloc(sizeof(TreeNode));
	assert(newnode);
	newnode->data = data;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}
//非递归的前序遍历
void preOrderTraversal(TreeNode* root)
{
	if (root == NULL)
	{
		return;
	}
	//设置一个栈
	TreeNode* Stack[100];
	int top = -1;
	Stack[++top] = root;
	while (top >= 0)
	{
		TreeNode* current = Stack[top--];
		printf("%d ", current->data);

		if (current->right!=NULL)
		{
			Stack[++top] = current->right;
		}
		if (current->left!=NULL)
		{
			Stack[++top] = current->left;
		}
	}
}
//非递归的中序遍历
void inOrderTraversal(TreeNode* root)
{
	if (root == NULL)
	{
		return;
	}
	//设置一个栈
	TreeNode* Stack[100];
	int top = -1;
	TreeNode* current = root;
	while (current!=NULL || top>=0)
	{
		while (current != NULL)
		{
			Stack[++top] = current;
			current = current->left;
		}
		current = Stack[top--];
		printf("%d ", current->data);
		current = current->right;
	}
}
//非递归的后序遍历
void postOrderTraversal(TreeNode* root)
{
	if (root == NULL)
	{
		return;
	}
	//设置两个栈
	TreeNode* Stack1[100],* Stacck2[100];
	int top1 = -1, top2 = -1;
	Stack1[++top1] = root;
	while (top1>=0)
	{
		TreeNode* current = Stack1[top1--];
		Stacck2[++top2] = current;

		if (current->left != NULL)
		{
			Stack1[++top1] = current->left;
		}
		if (current->right != NULL)
		{
			Stack1[++top1] = current->right;
		}
	}
	while (top2>=0)
	{
		TreeNode* current = Stacck2[top2--];
		printf("%d ", current->data);
	}
}
// 释放二叉树内存
void freeTree(struct TreeNode* root) {
	if (root == NULL)
		return;
	freeTree(root->left);
	freeTree(root->right);
	free(root);
}
int main()
{
	TreeNode* root = NULL;
	root = createTreenode(1);
	root->left = createTreenode(2);
	root->right = createTreenode(3);
	root->left->left = createTreenode(4);
	root->left->right = createTreenode(5);
	root->right->left = createTreenode(6);
	root->right->right = createTreenode(7);

	printf("非递归前序遍历如下\n");
	preOrderTraversal(root);
	printf("\n");

	printf("非递归中序遍历如下\n");
	inOrderTraversal(root);
	printf("\n");

	printf("非递归后序遍历如下\n");
	postOrderTraversal(root);
	printf("\n");

	freeTree(root);
	return 0;
}