#pragma once

#include <iostream>
#include <cstdlib>
#include "threaded_node.hpp"

using namespace std;

template <class TData>
class InorderThreadedBinaryTree
{
private:
	// 根结点
	ThreadedNode<TData>* root_;
	/// <summary>
	/// 子树创建中序遍历
	/// </summary>
	/// <param name="subtree_root">子树根结点</param>
	/// <param name="pre_node">子树根结点的中序遍历的前一个结点</param>
	void createThreadInSubtreeRecursive_(ThreadedNode<TData>*& subtree_root, ThreadedNode<TData>*& pre_node);
	/// <summary>
	/// 子树插入
	/// </summary>
	/// <param name="subtree_root"></param>
	/// <param name="data"></param>
	/// <returns></returns>
	bool insertInSubtreeRecursive_(ThreadedNode<TData>*& subtree_root,const TData& data);

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

	ThreadedNode<TData>* root() { return this->root_; }

	bool insertRecursive(const TData& data) { return this->insertInSubtreeRecursive_(this->root_, data); }

	// 创建中序线索
	void createThreadRecursive();

	// 中序线索第一个线索结点
	ThreadedNode<TData>* first(ThreadedNode<TData>* subtree_root);

	// 中序线索最后一个线索结点
	ThreadedNode<TData>* last(ThreadedNode<TData>* subtree_root);

	// 获取中序线索的下一个结点
	ThreadedNode<TData>* next(ThreadedNode<TData>* node);

	// 获取中序线索的上一个结点
	ThreadedNode<TData>* pre(ThreadedNode<TData>* node);

	// 获取当前结点的父节点
	ThreadedNode<TData>* parent(ThreadedNode<TData>* node);

	// 中序线索二叉树中序遍历
	void inorderTraversal(void (*visit)(ThreadedNode<TData>*));

	// 中序线索二叉树前序遍历
	void preorderTraverse(void (*visit)(ThreadedNode<TData>*));

	// 中序线索二叉树后序遍历
	void postorderTraversal(void (*visit)(ThreadedNode<TData>*));

	// 子树获取后序遍历首个结点
	ThreadedNode<TData>* getFirstNodeForPostorder(ThreadedNode<TData>* subtree_root);
};

template<class TData>
inline void InorderThreadedBinaryTree<TData>::createThreadInSubtreeRecursive_(ThreadedNode<TData>*& subtree_root, ThreadedNode<TData>*& pre_node)
{
	// 空子树处理
	if (!subtree_root)
		return;

	// 左子树递归
	this->createThreadInSubtreeRecursive_(subtree_root->left_child,pre_node);
	
	// 创建线索

	// 当前结点到前驱结点
	if (subtree_root->left_child == NULL)
	{
		subtree_root->left_child = pre_node;
		subtree_root->left_tag = THREADED_NODE_POINTER;
	}
	// 前驱结点到当前结点
	if (pre_node != NULL && pre_node->right_child == NULL)
	{
		pre_node->right_child = subtree_root;
		pre_node->right_tag = THREADED_NODE_POINTER;
	}

	// 更新pre_node
	pre_node = subtree_root;

	// 右子树递归
	this->createThreadInSubtreeRecursive_(subtree_root->right_child,pre_node);
}

template <typename TData>
int heightOfSubTree(ThreadedNode<TData>* subtree_root)
{
	// 空树处理：空树高度为0
	if (!subtree_root)
		return 0;

	// 非空树处理
	int left_subtree_height = heightOfSubTree(subtree_root->left_child);
	int right_subtree_height = heightOfSubTree(subtree_root->right_child);

	return (left_subtree_height > right_subtree_height ? left_subtree_height : right_subtree_height) + 1;
}

template<class TData>
inline bool InorderThreadedBinaryTree<TData>::insertInSubtreeRecursive_(ThreadedNode<TData>*& subtree_root, const TData& data)
{
	// 插入到空子树中
	if (!subtree_root)
	{
		subtree_root = new ThreadedNode<TData>(data);
		if (!subtree_root)
			throw bad_alloc();

		return true;
	}

	// 非空子树插入
	int left_subtree_height = heightOfSubTree(subtree_root->left_child);
	int right_subtree_height = heightOfSubTree(subtree_root->right_child);

	// 平衡二叉树左右子树高度差
	if (left_subtree_height > right_subtree_height)
		return this->insertInSubtreeRecursive_(subtree_root->right_child,data);
	else
	{
		return this->insertInSubtreeRecursive_(subtree_root->left_child, data);
	}
}

template<class TData>
inline void InorderThreadedBinaryTree<TData>::createThreadRecursive()
{
	// 空树处理
	if (!this->root_)
		return;

	// 递归
	ThreadedNode<TData>* pre_node = NULL;

	this->createThreadInSubtreeRecursive_(this->root_,pre_node);

	// 最后一个叶子结点的线索指针置空
	pre_node->right_child = NULL;
	pre_node->right_tag = THREADED_NODE_POINTER;
}

template<class TData>
inline ThreadedNode<TData>* InorderThreadedBinaryTree<TData>::first(ThreadedNode<TData>* subtree_root)
{
	// 空子树处理
	if (!subtree_root)
		throw invalid_argument("NULL pointer");
	
	// 获取结点
	ThreadedNode<TData>* cur = subtree_root;

	// 找到二叉树的最左边的叶结点
	while (cur->left_child != NULL && cur->left_tag == CHILD_POINTER)
	{
		cur = cur->left_child;
	}

	// 返回结点
	return cur;
}

template<class TData>
inline ThreadedNode<TData>* InorderThreadedBinaryTree<TData>::last(ThreadedNode<TData>* subtree_root)
{
	// 空子树处理
	if (!subtree_root)
		throw invalid_argument("NULL pointer");

	// 获取结点
	ThreadedNode<TData>* cur = subtree_root;
	
	// 找到二叉树的最右边叶子节点
	while (cur->right_child != NULL && cur->right_tag == CHILD_POINTER)
	{
		cur = cur->right_child;
	}

	// 返回结果
	return cur;
}

template<class TData>
inline ThreadedNode<TData>* InorderThreadedBinaryTree<TData>::next(ThreadedNode<TData>* node)
{
	// 如果右指针是线索，直接返回
	if (node->right_tag == THREADED_NODE_POINTER)
		return node->right_child;

	// 找右子树的最左侧叶子结点
	return this->first(node->right_child);
}

template<class TData>
inline ThreadedNode<TData>* InorderThreadedBinaryTree<TData>::pre(ThreadedNode<TData>* node)
{
	// 如果当前结点的左指针就是线索指针，直接返回
	if (node->left_tag == THREADED_NODE_POINTER)
		return node->left_child;

	// 找到左子树的最右边的叶子节点（左子树中序遍历的最后一个结点），返回
	return this->last(node->left_child);
}

template<class TData>
inline ThreadedNode<TData>* InorderThreadedBinaryTree<TData>::parent(ThreadedNode<TData>* node)
{
	// 空结点处理
	if (!node)
		throw invalid_argument("NULL pointer");

	// 根结点没有父节点
	if (node == this->root_)
		return NULL;

	// 通过前驱寻找父节点
	ThreadedNode<TData>* cur = node;
	while (cur->left_tag == CHILD_POINTER && cur->left_child != NULL)
	{
		cur = cur->left_child;
	}

	// 初始化upper_level_pre_node (上层前驱结点) 指向cur->left_child(指向上层前驱)
	ThreadedNode<TData>* upper_level_pre_node = cur->left_child;

	if (upper_level_pre_node)
	{
		if (upper_level_pre_node->right_child != node)
			upper_level_pre_node = upper_level_pre_node->right_node;

		if (upper_level_pre_node != NULL &&
			(upper_level_pre_node->left_child == node ||
				upper_level_pre_node->right_child == node))
			return upper_level_pre_node;
	}

	// 通过后继寻找父节点
	cur = node;
	while (cur->right_tag == CHILD_POINTER)
	{
		cur = cur->right_child;
	}

	// upper_level_post_node (上层后继结点) 指向cur的右孩子(指向上层后继)
	ThreadedNode<TData>* upper_level_post_node = cur->right_child;

	return upper_level_post_node;
}

template<class TData>
inline void InorderThreadedBinaryTree<TData>::inorderTraversal(void(*visit)(ThreadedNode<TData>*))
{
	for (ThreadedNode<TData>* cur = this->first(this->root_); cur != NULL; cur = this->next(cur))
	{
		visit(cur);
	}
}

template<class TData>
inline void InorderThreadedBinaryTree<TData>::preorderTraverse(void(*visit)(ThreadedNode<TData>*))
{
	ThreadedNode<TData>* cur = this->root_;

	while (cur)
	{
		visit(cur);

		if (cur->left_tag == CHILD_POINTER)
			cur = cur->left_child;
		else if (cur->right_tag == CHILD_POINTER)
			cur = cur->right_child;
		else // 当cur指向叶子结点时
		{
			// 使用中序线索回溯至第1个有右孩子的结点
			while (cur != NULL && cur->right_tag == THREADED_NODE_POINTER)
			{
				cur = cur->right_child;
			}

			// cur移动
			if (cur)
				cur = cur->right_child;
		}
	}
}

template<class TData>
inline void InorderThreadedBinaryTree<TData>::postorderTraversal(void(*visit)(ThreadedNode<TData>*))
{
	// 空树处理
	if (!this->root_)
		return;

	// 访问后序遍历的第一个结点
	ThreadedNode<TData>* cur = this->getFirstNodeForPostorder(this->root_);
	ThreadedNode<TData>* cur_parent = this->parent(cur);

	visit(cur);

	// 递归
	while (cur_parent)
	{
		if (cur_parent->right_child == cur || cur_parent->right_tag == THREADED_NODE_POINTER)
			cur = cur_parent;
		else
		{
			cur = this->getFirstNodeForPostorder(cur_parent->right_child);
		}

		visit(cur);

		cur_parent = this->parent(cur);
	}
}

template<class TData>
inline ThreadedNode<TData>* InorderThreadedBinaryTree<TData>::getFirstNodeForPostorder(ThreadedNode<TData>* subtree_root)
{
	ThreadedNode<TData>* cur = subtree_root;

	// 找到左子树的最左侧的叶子节点即可
	while (cur->left_tag == CHILD_POINTER || cur->right_tag == CHILD_POINTER)
	{
		if (cur->left_tag == CHILD_POINTER && cur->left_child != NULL)
			cur = cur->left_child;
		else if (cur->right_tag == CHILD_POINTER && cur->right_child != NULL)
		{
			cur = cur->right_child;
		}
	}

	return cur;
}