算法與資料結構-二叉樹的非遞歸前序，中序，後續周遊

#include<iostream>
#include<stack>
#include<vector>
using namespace std;

template<typename T>
struct TreeNode
{
	T value;
	TreeNode<T> * left;
	TreeNode<T> * right;
	bool visit;
	TreeNode(T v) :value(v), visit(false), left(nullptr), right(nullptr){}
};


template <typename T>
void CreateTree(TreeNode<T> * root)
{
	TreeNode<T> * node1 = new TreeNode<T>(1);
	TreeNode<T> * node2 = new TreeNode<T>(2);
	TreeNode<T> * node3 = new TreeNode<T>(3);
	TreeNode<T> * node4 = new TreeNode<T>(4);

	root->left = node1;
	root->right = node2;
	node1->left = node3;
	node3->right = node4;
}


template<typename T>
void PreTraverse(TreeNode<T> * root)
{
	stack<TreeNode<T>*> sta;
	vector<T> result;
	if (root == nullptr)
		return;
	sta.push(root);
	result.push_back(root->value);
	root->visit = 1;
	while (!sta.empty())
	{
		TreeNode<T>* temp = sta.top();
		if (temp->left != nullptr&&temp->left->visit==0)
		{
			result.push_back(temp->left->value);
			sta.push(temp->left);
			temp->left->visit = 1;
		}
		else
		{
			sta.pop();
			if (temp->right != nullptr)
			{
				result.push_back(temp->right->value);
				sta.push(temp->right);
				temp->right->visit = 1;
			}
		}

	}

	for (auto au:result)
	{
		cout << au << "\t";
	}
	cout << endl;
}


template<typename T>
void MidTraverse(TreeNode<T> * root)
{
	stack<TreeNode<T>*> sta;
	vector<T> result;
	if (root == nullptr)
		return;
	sta.push(root);
	while (!sta.empty())
	{
		TreeNode<T>* temp = sta.top();
		if (temp->left != nullptr&&temp->left->visit == 0)//左節點為空或已通路
		{
			sta.push(temp->left);
		}
		else
		{
				result.push_back(temp->value);
				temp->visit = 1;
				sta.pop();//當結點的右結點入棧後，該結點已經沒有用，可以進行删除。該節點已經輸出且右結點也儲存
				if (temp->right != nullptr)
				{
					sta.push(temp->right);
				}				
		}

	}

	for (auto au : result)
	{
		cout << au << "\t";
	}
	cout << endl;
}


template<typename T>
void PostTraverse(TreeNode<T> * root)
{
	stack<TreeNode<T>*> sta;
	vector<T> result;
	if (root == nullptr)
		return;
	sta.push(root);
	while (!sta.empty())
	{
		TreeNode<T>* temp = sta.top();
		if (temp->left != nullptr&&temp->left->visit == 0)//左節點不為空且沒有通路過
		{
			sta.push(temp->left);
		}
		else
		{
			if (temp->right!=nullptr&&temp->right->visit==0)//右結點不為空且沒有通路過
			{
				sta.push(temp->right);
			}
			else
			{//左右結點都為空，或左右結點都通路過
				sta.pop();
				result.push_back(temp->value);
				temp->visit = 1;
			}
		}

	}

	for (auto au : result)
	{
		cout << au << "\t";
	}
	cout << endl;
}

int main()
{
	TreeNode<int> * root=new TreeNode<int>(0);

	cout << "前序周遊結果:"<<"\t";
	CreateTree(root);
	PreTraverse(root);

	cout << "中序周遊結果:" << "\t";
	CreateTree(root);
	MidTraverse(root);

	cout << "後序周遊結果:" << "\t";
	CreateTree(root);
	PostTraverse(root);

	return 0;
}
           

測試結果：

測試二叉樹：

運作結果：