非递归方式遍历二叉树

#include <iostream>
#include <queue>
#include <stack>
#include <unordered_set>
using namespace std;

struct TreeNode {
	TreeNode(int val) :val(val), left(NULL), right(NULL) {}
	int val;
	TreeNode* left;
	TreeNode* right;
};

int main() {
	int n;
	cin >> n;
	TreeNode* root = new TreeNode(1);
	queue<TreeNode*> q;
	q.push(root);
	int tnum = 0;
	for (int i = 0; i < n; ++i) {
		cin >> tnum;
		if (tnum)
		{
			q.front()->left = new TreeNode(tnum);
			q.push(q.front()->left);
		}
		cin >> tnum;
		if (tnum)
		{
			q.front()->right = new TreeNode(tnum);
			q.push(q.front()->right);
		}
		q.pop();
	}

	//前序遍历：根->左->右
	stack<TreeNode*> st;
	TreeNode* tmp = NULL;

	st.push(root);
	while (!st.empty()) {
		tmp = st.top();
		st.pop();
		cout << tmp->val << " ";
		if (tmp->right)
			st.push(tmp->right);
		if (tmp->left)
			st.push(tmp->left);
	}
	cout << endl;
	stack<TreeNode*>().swap(st);

	//中序遍历：左->根->右
	tmp = root;
	while (tmp || !st.empty()) {
		if (tmp) {
			st.push(tmp);
			tmp = tmp->left;
		}
		else
		{
			cout << st.top()->val << " ";
			tmp = st.top()->right;
			st.pop();
		}
	}
	cout << endl;
	stack<TreeNode*>().swap(st);
	stack<TreeNode*> st2;

	//后序遍历：左->右->根
	st.push(root);
	while (!st.empty()) {
		tmp = st.top();
		st.pop();
		st2.push(tmp);
		if (tmp->left)
			st.push(tmp->left);
		if (tmp->right)
			st.push(tmp->right);
	}
	while (!st2.empty())
	{
		cout << st2.top()->val << " ";
		st2.pop();
	}

	//层序遍历
	cout << endl;
	queue<TreeNode*>().swap(q);
	q.push(root);
	while (!q.empty()) {
		cout << q.front()->val << " ";
		if (q.front()->left)
			q.push(q.front()->left);
		if (q.front()->right)
			q.push(q.front()->right);
		q.pop();
	}
}

//没想出好方法，代码有点长

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int>val(n + 1);
	vector<int>le(n + 1, 0);
	vector<int>ri(n + 1, 0);

	for (int i = 0; i <= n; i++)
		val[i] = i;
	for (int i = 1; i <= n; i++) {
		cin >> le[i] >> ri[i];
	}
	vector<int>lef(le);
	vector<int>rif(ri);
	stack<int>zhan;

	//前序遍历
	lef.assign(le.begin(), le.end());
	rif.assign(ri.begin(), ri.end());
	
	zhan.push(1);//根节点为1
	cout << 1 << " ";//前序遍历在节点加入进来时输出
	while (!zhan.empty()) {
		int tmp = zhan.top();
		if (lef[tmp]) {
			zhan.push(lef[tmp]);
			cout << lef[tmp] << " ";
			lef[tmp] = 0;
		}
		else if (rif[tmp]) {
			zhan.push(rif[tmp]);
			cout << rif[tmp] << " ";
			rif[tmp] = 0;
		}
		else
			zhan.pop();
	}
	cout << endl;

	//中序遍历，入栈中左右，输出左中右，没有左右值的出栈
	lef.assign(le.begin(), le.end());
	rif.assign(ri.begin(), ri.end());
	//stack<int>zhan2;
	zhan.push(1);
	while (!zhan.empty()) {
		int tmp = zhan.top();
		if (lef[tmp]) {
			zhan.push(lef[tmp]);
			lef[tmp] = 0;
		}
		else if (rif[tmp]) {//将入栈顺序的中右改为右中
			zhan.pop();
			zhan.push(rif[tmp]);
			zhan.push(tmp);
			rif[tmp] = 0;
		}
		else {
			cout << tmp << " ";
			zhan.pop();
		}
	}
	cout << endl;


	//后序遍历
	lef.assign(le.begin(), le.end());
	rif.assign(ri.begin(), ri.end());
	zhan.push(1);
	while (!zhan.empty()) {
		int tmp = zhan.top();
		if (lef[tmp]) {
			zhan.push(lef[tmp]);
			lef[tmp] = 0;
		}
		else if (rif[tmp]) {
			zhan.push(rif[tmp]);
			rif[tmp] = 0;
		}
		else {
			cout << tmp << " ";
			zhan.pop();
		}
	}
	cout << endl;

	//层序遍历使用队列
	lef.assign(le.begin(), le.end());
	rif.assign(ri.begin(), ri.end());
	queue<int>que;
	que.push(1);//第一层根节点1
	while (!que.empty()) {
		int tmp = que.front();
		que.pop();
		if (lef[tmp]) {
			que.push(lef[tmp]);
		}
		if (rif[tmp]) {
			que.push(rif[tmp]);
		}
		cout << tmp << " ";
	}
	cout << endl;



	system("pause");
	return 0;
}