#include <iostream>

#include <vector>

#include <stack>

using namespace std;

struct TreeNode{

	int val;

	TreeNode* left;

	TreeNode* right;

	TreeNode(int _val) :val(_val){

		left = NULL; right = NULL;

	}

};

TreeNode* BuildTree()

{

	TreeNode* root = new TreeNode(6);

	int array[] = { 2, 7, 1, 4, 9, 3, 5, 8 };

	vector<TreeNode*>  list;

	//cout << sizeof(array) / sizeof(array[0]) << endl;

	for (size_t i = 0; i <sizeof(array)/sizeof(array[0]); i++)

	{

		TreeNode* t = new TreeNode(array[i]);

		list.push_back(t);

	}

	root->left = list[0];

	root->right = list[1];

	list[0]->left = list[2];

	list[0]->right = list[3];

	list[1]->right = list[4];

	list[3]->left = list[5];

	list[3]->right = list[6];

	list[4]->left = list[7];

	return root;

}

void preorderRecursive(TreeNode* t)

{

	if (t == NULL)

		return;

	cout << t->val << " ";

	preorderRecursive(t->left);

	preorderRecursive(t->right);

}

void preorderIterative(TreeNode* root)

{

	if (root == NULL)

		return;

	stack<TreeNode*> stk;

	TreeNode* cur = root;

	while (cur || !stk.empty())

	{

		while (cur)

		{

			cout << cur->val << " ";

			stk.push(cur);

			cur = cur->left;

		}

		if (!stk.empty())

		{

			cur = stk.top();

			stk.pop();

			cur = cur->right;

		}

	}

}

void preorderMorris(TreeNode* root)

{

	if (root == NULL)

		return;

	TreeNode* cur = root;

	TreeNode* pre = NULL;//前驱节点

	while (cur)

	{

		if (cur->left == NULL){

			cout << cur->val << " ";

			cur = cur->right;

		}

		else{

			pre = cur->left;

			while (pre->right != NULL &&  pre->right != cur)

				pre = pre->right;

			if (pre->right == NULL){

				cout << cur->val << " ";

				pre->right = cur;

				cur = cur->left;

			}

			else{

				pre->right = NULL;

				cur = cur->right;

			}

		}

	}

}

void inorderRecursive(TreeNode* root)

{

	if (root == NULL)

		return;

	inorderRecursive(root->left);

	cout << root->val << " ";

	inorderRecursive(root->right);

}

void inorderIterative(TreeNode* root)

{

	stack<TreeNode* > stk;

	TreeNode* cur = root;

	while (cur || !stk.empty())

	{

		while (cur){

			stk.push(cur);

			cur = cur->left;

		}

		if (!stk.empty()){

			cur = stk.top();

			cout << cur->val << " ";

			stk.pop();

			cur = cur->right;

		}

	}

}

void inorderMorris(TreeNode* root)

{

	TreeNode* cur = root;

	TreeNode* pre = NULL;  //前驱节点

	while (cur)

	{

		if (cur->left == NULL){

			cout << cur->val << " ";

			cur = cur->right;

		}

		else{

			pre = cur->left;

			while (pre->right != NULL && pre->right != cur)

				pre = pre->right;

			if (pre->right == NULL){

				pre -> right = cur;

				cur = cur->left;

			}

			else{

				cout << cur->val << " ";

				pre->right = NULL;

				cur = cur->right;

			}

		}

	}

}

void postorderRecursive(TreeNode* root)

{

	if (root == NULL)

		return;

	postorderRecursive(root->left);

	postorderRecursive(root->right);

	cout << root->val << " ";

}

void postorderIterative(TreeNode* root)

{

	stack<TreeNode*> stk;

	TreeNode* cur = root;

	TreeNode* pre = NULL;

	while (cur || !stk.empty()){

		while (cur){

			stk.push(cur);

			cur = cur->left;

		}

		if (!stk.empty()){

			cur = stk.top();

			if (cur->right != NULL && cur->right != pre){

				cur = cur->right;

			}

			else{

				cout << cur->val<<" ";

				pre = cur;

				stk.pop();

				cur = NULL;

			}

		}

	}

}

void reverse(TreeNode *begin, TreeNode *end) {

	if (begin == end)

		return;

	TreeNode *pre = begin;

	TreeNode *cur = begin->right;

	TreeNode *next;

	while (pre != end) {

		TreeNode* temp = cur->right;

		cur->right = pre;

		pre = cur;

		cur = temp;

	}

}

void traversalReversal(TreeNode *begin, TreeNode *end) {

	reverse(begin, end);

	TreeNode *it = end;

	while (true) {

		cout << it->val << " ";

		if (it == begin)

			break;

		it = it->right;

	}

	reverse(end, begin);

}

void postorderMorris(TreeNode *root) {

	if (!root)

		return;

	TreeNode dump(0);

	dump.left = root;

	TreeNode *cur = &dump;

	TreeNode *pre = NULL;

	while (cur) {

		if (cur->left == NULL) {

			cur = cur->right;

		}

		else {

			pre = cur->left;

			while (pre->right != NULL && pre->right != cur)

				pre = pre->right;

			if (pre->right == NULL) {

				pre->right = cur;

				cur = cur->left;

			}

			else {

				traversalReversal(cur->left, pre);

				pre->right = NULL;

				cur = cur->right;

			}

		}

	}

}

int main(void)

{

	TreeNode* root = BuildTree();

	cout << "----------Preorder Recursive--------------" << endl;

	preorderRecursive(root);

	cout <<endl;

	cout << "----------Preorder Iterative---------------" << endl;

	preorderIterative(root);

	cout << endl;

	cout << "----------Preorder Morris---------------" << endl;

	preorderMorris(root);

	cout << endl;

	cout << endl;

	cout << "----------Inorder Recursive--------------" << endl;

	inorderRecursive(root);

	cout << endl;

	cout << "----------Inorder Iterative--------------" << endl;

	inorderIterative(root);

	cout << endl;

	cout << "----------Inorder Morris-----------------" << endl;

	inorderMorris(root);

	cout << endl;

	cout << endl;

	cout << "----------Postorder Recursive--------------" << endl;

	postorderRecursive(root);

	cout << endl;

	cout << "----------Postorder Iterative--------------" << endl;

	postorderIterative(root);

	cout << endl;

	cout << "----------Postorder Morris-----------------" << endl;

	postorderMorris(root);

	cout << endl;

}