#pragma once

#include <iostream>
#include <cstdlib>
#include <stack>
#include <queue>

using namespace std;

namespace binary_tree
{
	// 二叉树结点模板结构体
	template <class TData>
	struct BinaryTreeNode
	{
		TData data;
		BinaryTreeNode<TData>* left_child;
		BinaryTreeNode<TData>* right_child;

		BinaryTreeNode()
			:left_child(NULL),right_child(NULL){}

		explicit BinaryTreeNode(TData data, BinaryTreeNode<TData>* left_child = NULL, BinaryTreeNode<TData>* right = NULL)
			:data(data), left_child(left_child), right_child(right_child) {}

	};

	// （后序遍历）回溯栈结点模板结构体
	template <class TData>
	struct PostOrderBacktrackStackNode
	{
		BinaryTreeNode<TData>* node;
		// 0：左孩子回溯，1：右孩子回溯
		enum {LEFT_BACK_TRACKING = 0, RIGHT_BACK_TRACKING} tag;

		explicit PostOrderBacktrackStackNode(BinaryTreeNode<TData>* node = NULL)
			:node(node), tag(LEFT_BACK_TRACKING) {}
	};
}

template <class TData>
class BinaryTree
{
	// 重载==，判断两棵树是否相同
	friend bool operator== <>(const BinaryTree<TData>& binary_tree_1, const BinaryTree<TData>& binary_tree_2);
	// 重载<<，输出二叉树
	friend ostream& operator<< <>(ostream& out, BinaryTree<TData>& binary_tree);

public:
	// 判断两棵二叉树是否相同（递归）------ static修饰的变量或者方法受权限修饰符约束吗？会受权限修饰符限制
	static bool equal(binary_tree::BinaryTreeNode<TData>* root1, binary_tree::BinaryTreeNode<TData>* root2);

protected:
	binary_tree::BinaryTreeNode<TData>* root_; // 树根结点

	// 子树插入结点（递归）
	bool insertInSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>*& subtree_root, const TData& data);

	// 子树删除（递归）
	void deleteSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>*& subtree_root);

	// 子树是否存在数据（递归）
	bool existInSubTree_(binary_tree::BinaryTreeNode<TData>* subtree_root, TData data) const;

	// 复制（递归）
	bool duplicateSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* src_subtree_root, binary_tree::BinaryTreeNode<TData>*& target_subtree_root);

	// 求子树的高度（递归）
	int heightOfSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_node) const;

	// 求子树的节点个数（递归）
	int sizeOfSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root) const;

	// 子树获取节点的父节点
	binary_tree::BinaryTreeNode<TData>* getParentInSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root, binary_tree::BinaryTreeNode<TData>* node) const;


	// 子树前序遍历（递归）
	void preOrderTraversalOfSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root, void (*visit)(binary_tree::BinaryTreeNode<TData>*));
	// 子树前序遍历
	void preOrderTraversalOfSubTree_(binary_tree::BinaryTreeNode<TData>* subtree_root, void (*visit)(binary_tree::BinaryTreeNode<TData>*));

	// 子树中序遍历（递归）
	void inOrderTraversalOfSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root, void (*visit)(binary_tree::BinaryTreeNode<TData>*));
	// 子树中序遍历
	void inOrderTraversalOfSubTree_(binary_tree::BinaryTreeNode<TData>* subtree_root, void (*visit)(binary_tree::BinaryTreeNode<TData>*));

	// 子树后序遍历（递归）
	void postOrderTraversalOfSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root, void (*visit)(binary_tree::BinaryTreeNode<TData>*));
	// 子树后序遍历
	void postOrderTraversalOfSubTree_(binary_tree::BinaryTreeNode<TData>* subtree_root, void (*visit)(binary_tree::BinaryTreeNode<TData>*));

	// 子树层序遍历
	void levelOrderTraversalOfSubTree_(binary_tree::BinaryTreeNode<TData>* subtree_root, void (*visit)(binary_tree::BinaryTreeNode<TData>*));

	// 子树打印
	void printSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root);

	// 使用前序遍历和中序遍历结果，创建子树（递归）
	bool createSubTreeByPreOrderAndInOrderList_(const TData* preorder_sub_list,
		const TData* inorder_sub_list,
		int length,
		binary_tree::BinaryTreeNode<TData>*& subtree_root);

public:
	BinaryTree() :root_(NULL) {}

	explicit BinaryTree(const TData& data) { this->insertInSubTreeRecursive_(this->root_, data); }

	// 拷贝构造函数
	BinaryTree(const BinaryTree<TData>& src_binary_tree);

	~BinaryTree() { this->deleteSubTreeRecursive_(this->root_); }

	// 获取根节点
	binary_tree::BinaryTreeNode<TData>* root() const { return this->root_; }

	// 判断是否为空树
	bool isEmpty() { return this->root_ == NULL; }

	// 获取父节点
	binary_tree::BinaryTreeNode<TData>* parent(binary_tree::BinaryTreeNode<TData>* node) const
	{
		// == NULL 代表空树， == node代表是根节点，无父节点
		return (this->root_ == NULL || this->root_ == node) ? NULL : this->getParentInSubTreeRecursive_(this->root_, node);
	}

	// 获取高度
	int height() { return this->heightOfSubTreeRecursive_(this->root_); }

	// 获取节点数
	int size() { return this->sizeOfSubTreeRecursive_(this->root_); }

	// 插入节点（递归）
	bool insertRecursive(const TData& data) { return this->insertInSubTreeRecursive_(this->root_, data); }

	// 是否存在数据
	bool exist(TData data) { return this->existInSubTree_(this->root_, data); }

	// 前序遍历（递归）
	void preOrderTraversalRecursive(void (*visit)(binary_tree::BinaryTreeNode<TData>*))
	{
		this->preOrderTraversalOfSubTreeRecursive_(this->root_, visit);
	}

	// 前序遍历
	void preOrderTraversal(void (*visit)(binary_tree::BinaryTreeNode<TData>*))
	{
		this->preOrderTraversalOfSubTree_(this->root_, visit);
	}

	// 中序遍历（递归）
	void inOrderTraversalRecursive(void (*visit)(binary_tree::BinaryTreeNode<TData>* node))
	{
		this->inOrderTraversalOfSubTreeRecursive_(this->root_, visit);
	}

	// 中序遍历
	void inOrderTraversal(void (*visit)(binary_tree::BinaryTreeNode<TData>* node))
	{
		this->inOrderTraversalOfSubTree_(this->root_, visit);
	}

	// 后序遍历（递归）
	void postOrderTraversalRecursive(void (*visit)(binary_tree::BinaryTreeNode<TData>*))
	{
		this->postOrderTraversalOfSubTreeRecursive_(this->root_,visit);
	}

	// 后序遍历
	void postOrderTraversal(void (*visit)(binary_tree::BinaryTreeNode<TData>*))
	{
		this->postOrderTraversalOfSubTree_(this->root_,visit);
	}

	// 层序遍历
	void levelOrderTraversal(void (*visit)(binary_tree::BinaryTreeNode<TData>*))
	{
		this->levelOrderTraversalOfSubTree_(this->root_, visit);
	}

	bool createByPreOrderAndInOrderList(const TData* preorder_list, const TData* inorder_list, int length)
	{
		bool res = this->createSubTreeByPreOrderAndInOrderList_(preorder_list,inorder_list,length,this->root_);

		return res;
	}

	void print() { this->printSubTreeRecursive_(this->root_); }

};

template <typename TData>
bool operator==(const BinaryTree<TData>& binary_tree_1, const BinaryTree<TData>& binary_tree_2)
{
	return BinaryTree<TData>::equal(binary_tree_1.root_,binary_tree_2.root_);
}

template <typename TData>
inline ostream& operator<< <>(ostream& out, BinaryTree<TData>& binary_tree)
{
	binary_tree.print();
	return out;
}

template<class TData>
inline bool BinaryTree<TData>::equal(binary_tree::BinaryTreeNode<TData>* root1, binary_tree::BinaryTreeNode<TData>* root2)
{
	// 两个空树进行比较
	if (root1 == NULL && root2 == NULL)
		return true;

	// 递归处理左右子树
	if (root1 != NULL && root2 != NULL && root1->data == root2->data
		&& BinaryTree<TData>::equal(root1->left_child, root2->left_child)	// 处理左子树
		&& BinaryTree<TData>::equal(root1->right_child, root2->right_child))	// 处理右子树
		return true;

	return false;
}

template<class TData>
inline bool BinaryTree<TData>::insertInSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>*& subtree_root, const TData& data)
{
	// 空子树处理，生成树根即可
	if (!subtree_root)
	{
		subtree_root = new binary_tree::BinaryTreeNode<TData>(data);
		if (!subtree_root)
			throw bad_alloc();

		return true;
	}

	// 分治递归
	int left_subtree_height = this->heightOfSubTreeRecursive_(subtree_root->left_child);
	int right_subtree_height = this->heightOfSubTreeRecursive_(subtree_root->right_child);

	//			为了平衡左右子树高度
	if (left_subtree_height > right_subtree_height)
	{
		bool res = this->insertInSubTreeRecursive_(subtree_root->right_child,data);
		if (!res)
			return false;
	}
	else
	{
		bool res = this->insertInSubTreeRecursive_(subtree_root->left_child,data);
		if (!res)
			return false;
	}

	// 退出
	return true;
}

template<class TData>
inline void BinaryTree<TData>::deleteSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>*& subtree_root)
{
	// 空子树就什么都不用处理
	if (!subtree_root)
		return;

	// 分治递归
	this->deleteSubTreeRecursive_(subtree_root->left_child);
	this->deleteSubTreeRecursive_(subtree_root->right_child);

	delete subtree_root;
	// 防止出现悬空指针
	subtree_root = NULL;
}

template<class TData>
inline bool BinaryTree<TData>::existInSubTree_(binary_tree::BinaryTreeNode<TData>* subtree_root, TData data) const
{
	// 空树返回false
	if (!subtree_root)
		return false;

	// 存在条件处理
	if (subtree_root->data == data)
		return true;

	// 分治递归
	//			左子树递归
	bool existed = this->existInSubTree_(subtree_root->left_child,data);
	if (existed)
		return true;

	//			右子树递归
	existed = this->existInSubTree_(subtree_root->right_child,data);
	if (existed)
		return true;

	// 退出函数
	return false;
}

template<class TData>
inline bool BinaryTree<TData>::duplicateSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* src_subtree_root, binary_tree::BinaryTreeNode<TData>*& target_subtree_root)
{
	// 源树为空
	if (!src_subtree_root)
	{
		target_subtree_root = NULL;
		return true;
	}
	
	// 目标子树根节点处理
	target_subtree_root = new binary_tree::BinaryTreeNode<TData>(src_subtree_root->data);
	if (!target_subtree_root)
		throw bad_alloc();

	// 分治递归
	//			左子树递归
	bool res = this->duplicateSubTreeRecursive_(src_subtree_root->left_child,
												target_subtree_root->left_child);
	if (!res)
		return false;

	//			右子树递归
	res = this->duplicateSubTreeRecursive_(src_subtree_root->right_child,
											target_subtree_root->right_child);
	if (!res)
		return false;

	return true;
}

template<class TData>
inline int BinaryTree<TData>::heightOfSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_node) const
{
	// 空子树高度为0
	if (!subtree_node)
		return 0;

	// 分治递归
	//			左子树递归
	int left_subtree_height = this->heightOfSubTreeRecursive_(subtree_node->left_child);
	//			右子树递归
	int right_subtree_height = this->heightOfSubTreeRecursive_(subtree_node->right_child);

	// 计算subtree_height，等于1 + 最高子树的高度
	int subtree_height = (left_subtree_height > right_subtree_height ? left_subtree_height : right_subtree_height) + 1;

	// 返回结果
	return subtree_height;
}

template<class TData>
inline int BinaryTree<TData>::sizeOfSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root) const
{
	// 空子树节点个数为0
	if (!subtree_root)
		return 0;

	// 分治递归
	//			左子树递归
	int left_subtree_size = this->sizeOfSubTreeRecursive_(subtree_root->left_child);
	//			右子树递归
	int right_subtree_size = this->sizeOfSubTreeRecursive_(subtree_root->right_child);

	int subtree_size = left_subtree_size + right_subtree_size + 1;

	// 返回结果
	return subtree_size;
}

template<class TData>
inline binary_tree::BinaryTreeNode<TData>* BinaryTree<TData>::getParentInSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root, binary_tree::BinaryTreeNode<TData>* node) const
{
	// 空子树父节点也为NULL
	if (!subtree_root)
		return NULL;

	// 找到父节点情况处理
	if (subtree_root->left_child == node || subtree_root->right_child == node)
		return subtree_root;

	// 分治递归
	binary_tree::BinaryTreeNode<TData>* parent = this->getParentInSubTreeRecursive_(subtree_root->left_child,node);

	if (!parent) // 左子树没找到对应节点的父节点
		parent = this->getParentInSubTreeRecursive_(subtree_root->right_child, node);

	return parent;
}

template<class TData>
inline void BinaryTree<TData>::preOrderTraversalOfSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root, void(*visit)(binary_tree::BinaryTreeNode<TData>*))
{
	// 空子树（节点）不需要遍历
	if (!subtree_root)
		return;

	// 分治递归
	visit(subtree_root);
	this->preOrderTraversalOfSubTreeRecursive_(subtree_root->left_child,visit);
	this->preOrderTraversalOfSubTreeRecursive_(subtree_root->right_child,visit);
}

template<class TData>
inline void BinaryTree<TData>::preOrderTraversalOfSubTree_(binary_tree::BinaryTreeNode<TData>* subtree_root, void(*visit)(binary_tree::BinaryTreeNode<TData>*))
{
	// 回溯栈
	stack<binary_tree::BinaryTreeNode<TData>*> backtrack_stack;
	backtrack_stack.push(subtree_root);

	while (!backtrack_stack.empty())
	{
		binary_tree::BinaryTreeNode<TData>* cur = backtrack_stack.top();
		backtrack_stack.pop();

		visit(cur);

		if (cur->right_child)
			backtrack_stack.push(cur->right_child);

		if (cur->left_child)
			backtrack_stack.push(cur->left_child);
	}
}

template<class TData>
inline void BinaryTree<TData>::inOrderTraversalOfSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root, void(*visit)(binary_tree::BinaryTreeNode<TData>*))
{
	// 空子树（节点）不需要递归
	if (!subtree_root)
		return;

	this->inOrderTraversalOfSubTreeRecursive_(subtree_root->left_child,visit);
	visit(subtree_root);
	this->inOrderTraversalOfSubTreeRecursive_(subtree_root->right_child,visit);
}

template<class TData>
inline void BinaryTree<TData>::inOrderTraversalOfSubTree_(binary_tree::BinaryTreeNode<TData>* subtree_root, void(*visit)(binary_tree::BinaryTreeNode<TData>*))
{
	stack<binary_tree::BinaryTreeNode<TData>*> backtrack_stack;
	binary_tree::BinaryTreeNode<TData>* cur = subtree_root;

	while (cur || !backtrack_stack.empty())
	{
		// 一直向左子树方向搜索，等于在做深度优先搜索DFS

		// 每次visit完一个节点，都要去找其左子树的各节点
		while (cur)
		{
			backtrack_stack.push(cur);
			cur = cur->left_child;
		}

		if (!backtrack_stack.empty())
		{
			cur = backtrack_stack.top();
			backtrack_stack.pop();

			visit(cur);

			cur = cur->right_child;
		}
	}
}

template<class TData>
inline void BinaryTree<TData>::postOrderTraversalOfSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root, void(*visit)(binary_tree::BinaryTreeNode<TData>*))
{
	// 空子树不需要后序遍历
	if (!subtree_root)
		return;

	// 分治递归
	this->postOrderTraversalOfSubTreeRecursive_(subtree_root->left_child,visit);
	this->postOrderTraversalOfSubTreeRecursive_(subtree_root->right_child,visit);
	visit(subtree_root);
}

template<class TData>
inline void BinaryTree<TData>::postOrderTraversalOfSubTree_(binary_tree::BinaryTreeNode<TData>* subtree_root, void(*visit)(binary_tree::BinaryTreeNode<TData>*))
{
	stack<binary_tree::PostOrderBacktrackStackNode<TData>> backtarck_stack;
	binary_tree::BinaryTreeNode<TData>* cur_tree_node = subtree_root;

	do
	{
		// 一直向左子树方向搜索，等于在做深度优先搜索dfs
		while (cur_tree_node != NULL)
		{
			binary_tree::PostOrderBacktrackStackNode<TData> stack_node(cur_tree_node);
			backtarck_stack.push(stack_node);
			cur_tree_node = cur_tree_node->left_child;
		}

		bool cur_tree_node_left_backtrack_unfinished = true;
		while (cur_tree_node_left_backtrack_unfinished && !backtarck_stack.empty())
		{
			binary_tree::PostOrderBacktrackStackNode<TData> cur_backtrack_node = backtarck_stack.top();
			backtarck_stack.pop();

			cur_tree_node = cur_backtrack_node.node;

			if (cur_backtrack_node.tag == binary_tree::PostOrderBacktrackStackNode<TData>::LEFT_BACK_TRACKING)
			{
				cur_backtrack_node.tag = binary_tree::PostOrderBacktrackStackNode<TData>::RIGHT_BACK_TRACKING;
				backtarck_stack.push(cur_backtrack_node);
				cur_tree_node = cur_tree_node->right_child;

				cur_tree_node_left_backtrack_unfinished = false;
			}
			else
			{
				visit(cur_tree_node);
			}
		}
	} while (!backtarck_stack.empty());

}

template<class TData>
inline void BinaryTree<TData>::levelOrderTraversalOfSubTree_(binary_tree::BinaryTreeNode<TData>* subtree_root, void(*visit)(binary_tree::BinaryTreeNode<TData>*))
{
	// 初始化遍历队列
	queue<binary_tree::BinaryTreeNode<TData>*> traversal_queue;
	traversal_queue.push(subtree_root);

	// 遍历
	while (!traversal_queue.empty())
	{
		binary_tree::BinaryTreeNode<TData>* cur = traversal_queue.front();
		traversal_queue.pop();

		visit(cur);

		if (cur->left_child)
			traversal_queue.push(cur->left_child);

		if (cur->right_child)
			traversal_queue.push(cur->right_child);
	}
}

template<class TData>
inline void BinaryTree<TData>::printSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root)
{
	// 空子树处理
	if (!subtree_root)
		return;

	// 打印子树根节点
	cout << subtree_root->data;

	// 递归处理左右子树
	if (subtree_root->left_child != NULL || subtree_root->right_child != NULL)
	{
		cout << '(';

		this->printSubTreeRecursive_(subtree_root->left_child);

		cout << ',';

		this->printSubTreeRecursive_(subtree_root->right_child);

		cout << ')';
	}
}

template<class TData>
inline bool BinaryTree<TData>::createSubTreeByPreOrderAndInOrderList_(const TData* preorder_sub_list,const TData* inorder_sub_list, int length, binary_tree::BinaryTreeNode<TData>*& subtree_root)
{
	// 空子序列处理，就是一棵空树
	if (length == 0)
		return true;

	// 中序序列找到轴（根节点），并生成子树根节点
	int inorder_sub_list_pivot = 0;
	// 取出前序遍历序列首元素，即根结点
	TData cur_subtree_root_data = *preorder_sub_list;

	while (cur_subtree_root_data != inorder_sub_list[inorder_sub_list_pivot])
	{
		inorder_sub_list_pivot++;
	}

	// 找到根结点后生成子根节点
	subtree_root = new binary_tree::BinaryTreeNode<TData>(cur_subtree_root_data);
	if (!subtree_root)
		throw bad_alloc();

	// 递归构造左子树和右子树

	// 构造sub_tree的左子树
	bool res = this->createSubTreeByPreOrderAndInOrderList_(preorder_sub_list + 1,
													inorder_sub_list,
													inorder_sub_list_pivot,
													subtree_root->left_child);

	if (!res) // 构造失败
		return false;

	// 构造sub_tree的右子树
	res = this->createSubTreeByPreOrderAndInOrderList_(preorder_sub_list + inorder_sub_list_pivot + 1,
														inorder_sub_list + inorder_sub_list_pivot + 1,
														length - inorder_sub_list_pivot - 1,
														subtree_root->right_child);
	return res;
}

template<class TData>
inline BinaryTree<TData>::BinaryTree(const BinaryTree<TData>& src_binary_tree)
{
	bool res = this->duplicateSubTreeRecursive_(src_binary_tree.root(),this->root_);

	if (!res)
		throw logic_error("DuplicateSubTreeRecursive_ error");
}