实验目的：

  通过上机实验进一步掌握栈、队列、二叉树的存储结构及基本操作的实现方法。

实验内容与要求：

  基于二叉链表存储结构实现二叉树的基本运算，要求：

  ⑴能建立非空二叉树；

  ⑵实现二叉树的先、中、后序递归遍历算法；

  ⑶实现二叉树的非递归的先（或中、或后）序遍历算法及层序遍历算法；

  ⑷记录运行结果并对递归算法和非递归算法的效率加以分析。

第四点未实现。

注意:

在先序输入创建上述二叉树时应输入:AB##CDF##G##E##

(每个叶子节点后都需两个#字符来表示它们是叶子节点)

 而不是:ABCDFGE.

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

template<typename T>
class BinTree {
private:
	struct BinNode {
		T data;		//数值
		struct BinNode* lchild, * rchild;	//左右孩子指针
	};
	BinNode* root;	//根节点
	vector<T>res;	//记录先序、中序、后序遍历的结果

public:
	//初始化
	BinTree() {
		root =NULL;
	}

	//以先序输入创建二叉树，若树为空则输入#字符(注意:叶子节点后面需跟两个#字符)
	BinNode *init() {
		BinNode* p = NULL;
		T n;				//存放临时数据	
		cin >> n;
		if (root == NULL) {
			root = new BinNode;
			root->data = n;
			root->lchild = init();
			root->rchild = init();
		}
		else {
			if (n == '#')return NULL;
			else {
				p = new BinNode;
				p->data = n;
				p->lchild = init();
				p->rchild = init();
				return p;
			}
		}
		return NULL;
}

	//先序递归遍历
	vector<T>first_recursion(BinNode *root) {
		if (root != NULL) {
			res.push_back(root->data);
			first_recursion(root->lchild);
			first_recursion(root->rchild);
		}
		return res;
	}

	//中序递归遍历
	vector<T>middle_recursion(BinNode* root) {
		if (root != NULL) {
			middle_recursion(root->lchild);
			res.push_back(root->data);
			middle_recursion(root->rchild);
		}
		return res;
	}

	//后序递归遍历
	vector<T>after_recursion(BinNode* root) {
		if (root != NULL) {
			after_recursion(root->lchild);
			after_recursion(root->rchild);
			res.push_back(root->data);
		}
		return res;
	}

	//先序非递归,利用栈实现
	vector<T>first_non_recursion(BinNode* root) {
		if (root == NULL) {
			return res;
		}
		stack<BinNode*>st;
		st.push(root);
		while (!st.empty()) {
			auto m = st.top();
			st.pop();
			res.push_back(m->data);
			
			//因为栈的后进先出，所以先序遍历先压右节点再压左节点
			if (m->rchild) {
				st.push(m->rchild);
			}
			if (m->lchild) {
				st.push(m->lchild);
			}
		}
		return res;
	}

	//中序非递归,利用栈实现
	vector<T>middle_non_recursion(BinNode* root) {
		stack<BinNode*>st;
		while (!st.empty() || root) {
			while (root) {
				st.push(root);
				root = root->lchild;
			}
			if (!st.empty()) {
				root = st.top();
				st.pop();
				res.push_back(root->data);
				root = root->rchild;		//判断当前节点是否有右孩子;
			}
		}
		return res;
	}

	//后序非递归,利用先序非递归结果，只需先序遍历时先进栈左节点后进栈右节点，然后逆置即可
	vector<T>after_non_recursion(BinNode* root) {
		if (root == NULL) {
			return res;
		}
		stack<BinNode*>st;
		st.push(root);
		while (!st.empty()) {
			auto m = st.top();
			st.pop();
			res.push_back(m->data);

			//此时先压左节点，再压右节点
			if (m->lchild) {
				st.push(m->lchild);
			}
			if (m->rchild) {
				st.push(m->rchild);
			}
		}
		//结果逆置
		reverse(res.begin(),res.end());
		return res;
	}

	//层次遍历，利用队列实现
	vector<T>level_recursion(BinNode* root) {
		queue<BinNode*>que;
		if (root == NULL)return res;
		que.push(root);
		while (!que.empty()) {
			auto x = que.front();
			res.push_back(x->data);
			que.pop();
			if (x->lchild != NULL) {
				que.push(x->lchild);
			}
			if (x->rchild != NULL) {
				que.push(x->rchild);
			}
		}
		return res;
	}


	//将遍历结果传递给res
	vector<T>out(int n) {
		vector<T>().swap(res);
		//先序递归
		if (n == 1) {
			res = first_recursion(root);
		}
		//先序非递归
		if (n == -1) {
			res = first_non_recursion(root);
		}

		//中序递归
		else if(n==2){
			res = middle_recursion(root);
		}
		//中序非递归
		else if (n == -2) {
			res = middle_recursion(root);
		}

		//后序递归
		else if (n == 3) {
			res = after_recursion(root);
		}
		//后序非递归
		else if (n == -3) {
			res = after_non_recursion(root);
		}

		//层次遍历
		else if (n == 4) {
			res = level_recursion(root);
		}

		return res;
	}
	
};

int main() {
	BinTree<char>T;
	cout << "以先序输入创建二叉树，若树为空则输入#字符(注意:叶子节点后面需跟两个#字符):"<<endl;
	T.init();
	vector<char>a;
	cout << endl << endl;

	cout << endl<<"先序递归:";
	vector<char>().swap(a);
	a = T.out(1);
	for (unsigned int i = 0; i < a.size(); i++) {
		cout << a[i];
	}
	cout << endl << "中序递归:";
	vector<char>().swap(a);
	a = T.out(2);
	for (unsigned int i = 0; i < a.size(); i++) {
		cout << a[i];
	}
	cout << endl << "后序递归:";
	vector<char>().swap(a);
	a = T.out(3);
	for (unsigned int i = 0; i < a.size(); i++) {
		cout << a[i];
	}

	cout << endl << endl;
	cout << endl << "先序非递归:";
	vector<char>().swap(a);
	a = T.out(-1);
	for (unsigned int i = 0; i < a.size(); i++) {
		cout << a[i];
	}
	cout << endl << "中序非递归:";
	vector<char>().swap(a);
	a = T.out(-2);
	for (unsigned int i = 0; i < a.size(); i++) {
		cout << a[i];
	}
	cout << endl << "后序非递归:";
	vector<char>().swap(a);
	a = T.out(-3);
	for (unsigned int i = 0; i < a.size(); i++) {
		cout << a[i];
	}
	
	cout << endl;
	cout << endl << "层次遍历";
	vector<char>().swap(a);
	a = T.out(4);
	for (unsigned int i = 0; i < a.size(); i++) {
		cout << a[i];
	}
	cout << endl << endl;
}