#include "BirTree.h"


BiNode* BirTree::create(BiNode* bt)
{
	ElemType c;
	
	cin >> c;
	if (c == '#') {
		bt = nullptr;
	}
	else {
		bt = new BiNode;
		bt->data = c;
		bt->lchild = create(bt->lchild);
		bt->rchild = create(bt->rchild);
	}
	return bt;
}
//采用后续遍历的方式释放空间
void BirTree::release(BiNode*& bt)
{
	//线索二叉树后,通过给rtag和ltg赋值让原本为空的孩子结点有了前驱或后继,所以防止重复删除,需要当空结点处理
	if (bt == nullptr || bt->rtag == 1 || bt->ltag == 1) {
		return;
	}
	else {
		release(bt->lchild);
		release(bt->rchild);
		delete bt;
	}
}
//前序遍历
void BirTree::preOrder(BiNode* bt)
{
	if (bt == nullptr) {
		return;
	}
	else {
		visit(bt);
		preOrder(bt->lchild);
		preOrder(bt->rchild);
	}
}
//中序遍历
void BirTree::inOrder(BiNode* bt)
{
	if (bt == nullptr) {
		return;
	}
	else {
		inOrder(bt->lchild);
		visit(bt);
		inOrder(bt->rchild);
	}
}
//后序遍历
void BirTree::postOrder(BiNode* bt)
{
	if (bt == nullptr) {
		return;
	}
	else {
		postOrder(bt->lchild);
		postOrder(bt->rchild);
		visit(bt);
	}
}
//层序遍历
void BirTree::levelOrder(BiNode* bt)
{
	queue<BiNode*> q;
	if (bt != nullptr) {
		q.push(bt);
		while (q.size() != 0) {
			BiNode* t = q.front();
			visit(t);
			if (t->lchild != nullptr) {
				q.push(t->lchild);
			}
			if (t->rchild != nullptr) {
				q.push(t->rchild);
			}
			q.pop();
		}
	}
}
//访问
void BirTree::visit(BiNode* bt)
{
	cout << bt->data << " ";
}
/*构造函数
* 由于二叉排序树创建方式与普通不同
* 所以根据情况分别创建
*/
BirTree::BirTree()
{
	cout << "请选择你要创建的的二叉树的类型 ：" << endl;
	cout << "1.普通二叉树，2.二叉排序树" << endl;
	int select;
	cin >> select;
	if (select == 1) {
		cout << "创建的方式为前序：" << endl;
		root = create(root);
	}
}

//先(中)序遍历非递归
void BirTree::preOrder2()
{
	stack<BiNode*>s;
	BiNode* p = root;
	while (p != nullptr || !s.empty()) {
		while (p != nullptr) {
			visit(p);	//输出语句在这里就是前序遍历
			s.push(p);
			p = p->lchild;
		}
		if (!s.empty()) {
			p = s.top(); s.pop();
			//visit(p);		//输出语句在这里就是中序遍历
			p = p->rchild;
		}
	}
}
//后序遍历非递归
/*
* 根据后续遍历的特点，访问两次在后序遍历输出
*/
void BirTree::postOrder2() 
{
	stack<element*> s;
	BiNode* p = root;
	while (p != nullptr || !s.empty()) {
		if (p != nullptr) {
			element* elem = new element;
			elem->ptr = p;
			elem->flag = 1;
			s.push(elem);
			p = p->lchild;
		}
		else {
			element* elem = s.top(); s.pop();
			p = elem->ptr;
			if (elem->flag == 1) {	//说明只访问过左树
				elem->flag = 2;
				s.push(elem);
				p = p->rchild;
			}
			else {	//此时flag = 2; 就表明已经访问过右数
				visit(p);
				delete elem;	//访问后即可回收空间
				p = nullptr;	//访问后让指针指向空，确保循环继续【防止重复让入栈】
			}
		}
	}
	return;
}
//测试