#pragma once
#include<iostream>
#include<queue>
#include<stack>

using namespace std;
//typedef char ElemType;	//测试普通二叉树和线索二叉树建议用char
typedef int ElemType;	//测试二叉排序树建议int
//二叉树结点的结构体
typedef struct BiNode {
	ElemType  data;
	struct BiNode* lchild, * rchild;
	bool ltag = 0, rtag = 0;		//用于本类的子类线索二叉树使用，初始化为0
}BiNode;

//用于非递归的后序遍历的结构体
typedef struct element {
	BiNode* ptr;
	int flag;	//用来标记入栈次数
}element;


class BirTree
{
protected:
	BiNode* root =nullptr;
	element* p = nullptr;
public:
	BirTree();
	~BirTree() { 
		cout << endl << "调用析构函数";
		release(root); }
	void preOrder() { preOrder(root); }	//前序遍历
	void inOrder() { inOrder(root); }	//中序遍历
	void postOrder() { postOrder(root); }	//后续遍历
	void levelOrder() { levelOrder(root); }	//层序遍历
	void preOrder2();	//前序(中序遍历)非递归遍历
	void postOrder2();	//后续遍历
private:
	BiNode* create(BiNode* bt);		//创建
	void release(BiNode*& bt);		//销毁，传引用，防止野指针
	void preOrder(BiNode* bt);
	void inOrder(BiNode* bt);
	void postOrder(BiNode* bt);
	void levelOrder(BiNode* bt);
protected:
	void visit(BiNode* bt);
};