#pragma once

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

using namespace std;

template <class TData>
class PreOrderThreadedBinaryTree
{
private:
	ThreadedNode<TData>* root_;

	/// <summary>
	/// 子树创建前序线索
	/// </summary>
	/// <param name="node">当前结点</param>
	/// <param name="pre_node">前序遍历下该节点的前一个结点</param>
	void createThreadInSubTreeRecursive_(ThreadedNode<TData>*& node,ThreadedNode<TData>*& pre_node);

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

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

	/// <summary>
	/// 查找某个节点的父节点
	/// </summary>
	/// <param name="node">查找这个结点的父节点</param>
	/// <returns></returns>
	ThreadedNode<TData>* parent(ThreadedNode<TData>* node);

	// 前序线索二叉树的下一个节点
	ThreadedNode<TData>* next(ThreadedNode<TData>* node);

	//前序线索二叉树的前一个结点
	ThreadedNode<TData>* pre(ThreadedNode<TData>* node);

	//前序线索二叉树的最后一个结点
	ThreadedNode<TData>* last(ThreadedNode<TData>* subtree_root);
};

template<class TData>
inline void PreOrderThreadedBinaryTree<TData>::createThreadInSubTreeRecursive_(ThreadedNode<TData>*& node, ThreadedNode<TData>*& pre_node)
{
	// 结点为空，返回
	if (!node)
		return;

	if (!node->left_child)
	{
		node->left_child = pre_node;
		node->left_tag = THREADED_NODE_POINTER;
	}

	if (pre_node != NULL && pre_node->right_child == NULL)
	{
		pre_node->right_child = node;
		pre_node->right_tag = THREADED_NODE_POINTER;
	}

	pre_node = node;

	// 左子树分治 
	if (node->left_tag == CHILD_POINTER)
		this->createThreadInSubTreeRecursive_(node->left_child,pre_node);

	// 右子树分治
	this->createThreadInSubTreeRecursive_(node->right_child,pre_node);

}

template<class TData>
inline void PreOrderThreadedBinaryTree<TData>::createThreadRecursive()
{
	ThreadedNode<TData>* pre_node = NULL;

	// 不为空树时
	if (this->root_)
	{
		this->createThreadInSubTreeRecursive_(this->root_,pre_node);
		pre_node->right_child = NULL;
		pre_node->right_tag = THREADED_NODE_POINTER;
	}
}

template<class TData>
inline ThreadedNode<TData>* PreOrderThreadedBinaryTree<TData>::parent(ThreadedNode<TData>* node)
{
	// 如果树为空或者要查找的节点是根节点，则返回 NULL
	if (root == NULL || node == root) {
		return NULL;
	}

	ThreadedNode<TData>* current = root; // 从根节点开始
	ThreadedNode<TData>* parent_node = NULL; // 用来记录父节点

	// 遍历树，寻找目标节点 node
	while (current != NULL)
	{
		if (current == node) {
			// 找到了目标节点，返回其父节点
			return parent_node;
		}

		// 如果左子节点存在并且不是线索
		if (current->left_tag == CHILD_POINTER && current->left_child != NULL)
		{
			// 如果左子节点是目标节点，当前节点就是父节点
			if (current->left_child == node) {
				return current;
			}
			// 向左子树移动
			parent_node = current;
			current = current->left_child;
		}
		// 如果右子节点存在并且不是线索
		else if (current->right_tag == CHILD_POINTER && current->right_child != NULL)
		{
			// 如果右子节点是目标节点，当前节点就是父节点
			if (current->right_child == node) {
				return current;
			}
			// 向右子树移动
			parent_node = current;
			current = current->right_child;
		}
		else {
			// 如果没有孩子节点或孩子节点是线索，遍历结束
			break;
		}
	}

	// 如果遍历结束还没找到，返回 NULL
	return NULL;
}

template<class TData>
inline ThreadedNode<TData>* PreOrderThreadedBinaryTree<TData>::next(ThreadedNode<TData>* node)
{
	if (node->left_tag != THREADED_NODE_POINTER)
		return node->left_child;
	return node->right_child;
}

template<class TData>
inline ThreadedNode<TData>* PreOrderThreadedBinaryTree<TData>::pre(ThreadedNode<TData>* node)
{
	if (node->left_tag == THREADED_NODE_POINTER)
		return node->left_child;

	ThreadedNode<TData>* parent = this->parent(node);

	if (!parent)
		return NULL;

	if (parent->left_tag == 1 || parent->left_child == node)
		return parent;

	return this->last(parent->left_child);
}

template<class TData>
inline ThreadedNode<TData>* PreOrderThreadedBinaryTree<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;
}