#pragma once

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

using namespace std;

namespace child_sibling_tree
{
	// 所谓子女兄弟树，就是一棵特殊的二叉树
	template <class TData>
	struct ChildSiblingNode
	{
		// struct内属性、方法默认访问权限为public，class内属性、方法默认访问权限为private
		
		// 数据项
		TData data;
		// 长子结点（第一个子节点）
		ChildSiblingNode<TData>* first_child;
		// 长子结点在原多叉树的下一个兄弟结点
		ChildSiblingNode<TData>* next_sibling;


		explicit ChildSiblingNode(TData data,
			ChildSiblingNode<TData>* first_child = NULL,
			ChildSiblingNode<TData>* next_sibling = NULL)
			:data(data), first_child(first_child), next_sibling(next_sibling) {}
	};
}


// 每个节点的第一个子节点 作为该节点的 左孩子，其他子节点作为这个“第一个子节点”的右子树结点
  //     A										A
  //   / | \								   /	
  //  B  C  D			==========>			  B		
  // / \    |								 / \	
  //E   F   G								E   C
  //										 \	 \
  //										  F	  D
  //											 /				
  //											G
//
//通过这种方式，任何多叉树或者森林都能被表示为一个特殊的二叉树，即子女兄弟树。
//所谓孩子兄弟表示法，指的是用将整棵树用二叉链表存储起来，具体实现方案是：从树的根节点开始，依次存储各个结点的孩子结点和兄弟结点。

// 子女兄弟树的原树是多叉号树，多叉树只有先序（先根）和后序（后根）遍历
template <class TData>
class ChildSiblingTree
{
private:
	child_sibling_tree::ChildSiblingNode<TData>* root_;	// 根结点

	// 子树删除（递归）
	void removeSubtreeRecursive_(child_sibling_tree::ChildSiblingNode<TData>* subtree_root);

	// 子树先根遍历（递归），树的先根遍历是其子女二叉树的先根遍历
	// 树的先根遍历：先访问根节点，然后依次遍历每个子节点
	void preorderOfSubtreeRecursive_(child_sibling_tree::ChildSiblingNode<TData>* subtree_root, void (*visit)(child_sibling_tree::ChildSiblingNode<TData>*));

	// 子树后根遍历（递归），树的后根遍历是其子女二叉树的中根遍历
	// 树的后根遍历：先遍历所有子节点，然后访问根节点
	void postorderOfSubtreeRecursive_(child_sibling_tree::ChildSiblingNode<TData>* subtree_root, void (*visit)(child_sibling_tree::ChildSiblingNode<TData>*));

	// 子树层序遍历
	void levelorderOfSubtree_(child_sibling_tree::ChildSiblingNode<TData>* subtree_root,void (*visit)(child_sibling_tree::ChildSiblingNode<TData>*));

	// 使用字符串创建子女兄弟树
	void createSubtreeByPreorderStringRecursive_(child_sibling_tree::ChildSiblingNode<TData>*&,TData*& str);

	// 子树结点数量（递归）
	int nodeCountOfSubtreeRecursive_(child_sibling_tree::ChildSiblingNode<TData>* subtree_root);

	// 子树深度（递归）,针对森林的每棵树高度
	int maxHeightWithYoungerSiblingTreesRecursive_(child_sibling_tree::ChildSiblingNode<TData>* subtree_root);

	// 子树打印（递归）
	void printSubTreeRecursive_(child_sibling_tree::ChildSiblingNode<TData>* subtree_root);

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

	/// <summary>
	/// 使用带"()"的先根遍历字符串创建子女兄弟树
	/// </summary>
	/// <param name="str">带"()"的字符串</param>
	void createByPreorderStr(TData*& str) { this->createSubtreeByPreorderStringRecursive_(this->root_,str); }

	/// <summary>
	/// 判断是否是空树
	/// </summary>
	/// <returns>true为空</returns>
	bool empty() { return this->root_ == NULL; }

	/// <summary>
	/// 获取结点数（递归）
	/// </summary>
	/// <returns>结点数量</returns>
	int nodeCountRecursive() { return this->nodeCountOfSubtreeRecursive_(this->root_); }

	/// <summary>
	/// 获取高度（递归）
	/// </summary>
	/// <returns>返回树的高度</returns>
	int heightRecursive() { return this->maxHeightWithYoungerSiblingTreesRecursive_(this->root_); }

	/// <summary>
	/// 获取根结点
	/// </summary>
	/// <returns>获取到的根结点</returns>
	ChildSiblingTree<TData>* root() { return this->root_; }

	/// <summary>
	/// 先序遍历
	/// </summary>
	/// <param name="visit">函数指针</param>
	void preOrderRecursive(void (*visit)(child_sibling_tree::ChildSiblingNode<TData>*)) { this->preorderOfSubtreeRecursive_(this->root_, visit); }

	/// <summary>
	/// 后根遍历
	/// </summary>
	/// <param name="visit">函数指针</param>
	void postOrder(void (*visit)(child_sibling_tree::ChildSiblingNode<TData>*)) { this->postorderOfSubtreeRecursive_(this->root_,visit); }

	/// <summary>
	/// 层序遍历
	/// </summary>
	/// <param name="visit">函数指针</param>
	void levelOrder(void (*visit)(child_sibling_tree::ChildSiblingNode<TData>*)) { this->levelorderOfSubtree_(this->root_, visit); }

	/// <summary>
	/// 打印（递归）
	/// </summary>
	void printRecursive() { this->printSubTreeRecursive_(this->root_); }

};

template<class TData>
inline void ChildSiblingTree<TData>::removeSubtreeRecursive_(child_sibling_tree::ChildSiblingNode<TData>* subtree_root)
{
	// 空树处理
	if (!subtree_root)
		return;

	// 递归
	this->removeSubtreeRecursive_(subtree_root->first_child);
	this->removeSubtreeRecursive_(subtree_root->next_sibling);


	// 删除根结点
	delete subtree_root;
}

template<class TData>
inline void ChildSiblingTree<TData>::preorderOfSubtreeRecursive_(child_sibling_tree::ChildSiblingNode<TData>* subtree_root, void(*visit)(child_sibling_tree::ChildSiblingNode<TData>*))
{
	// 空树处理，递归出口
	if (!subtree_root)
		return;

	// 递归
	visit(subtree_root);

	this->preorderOfSubtreeRecursive_(subtree_root->first_child, visit);
	this->preorderOfSubtreeRecursive_(subtree_root->next_sibling,visit);
}

template<class TData>
inline void ChildSiblingTree<TData>::postorderOfSubtreeRecursive_(child_sibling_tree::ChildSiblingNode<TData>* subtree_root, void(*visit)(child_sibling_tree::ChildSiblingNode<TData>*))
{
	// 空树处理
	if (!subtree_root)
		return;

	// 递归
	this->postorderOfSubtreeRecursive_(subtree_root->first_child,visit);

	visit(subtree_root);

	this->postorderOfSubtreeRecursive_(subtree_root->next_sibling,visit);
}

template<class TData>
inline void ChildSiblingTree<TData>::levelorderOfSubtree_(child_sibling_tree::ChildSiblingNode<TData>* subtree_root, void(*visit)(child_sibling_tree::ChildSiblingNode<TData>*))
{
	// 空树处理
	if (!subtree_root)
		return;

	// 借助队列，队列初始化
	queue<child_sibling_tree::ChildSiblingNode<TData>*> node_queue;
	node_queue.push(subtree_root); // 根结点入队

	// 使用队列进行遍历
	while (!node_queue.empty())
	{
		child_sibling_tree::ChildSiblingNode<TData>* front_node = node_queue.front();
		node_queue.pop(); // 元素出栈

		visit(front_node);

		for (child_sibling_tree::ChildSiblingNode<TData>* cur = front_node->first_child; cur != NULL; cur = cur->next_sibling)
		{
			node_queue.push(cur);
		}
	}
}

template<class TData>
inline void ChildSiblingTree<TData>::createSubtreeByPreorderStringRecursive_(child_sibling_tree::ChildSiblingNode<TData>*& subtree_root, TData*& str)
{
	// 建树结束处理
	if (*str == TData('\0')) // 强制转换
		return;

	// 某子树结束处理
	if (*str == TData(')'))
	{
		str++;
		return;
	}

	// 新子树根结点开始处理
	while (*str == TData('('))
	{
		str++:
	}

	// 创建新子树根结点
	TData cur_data;
	// 若 TData 和 int 类型相同，value 为 true；否则为 false
	if (is_same<TData,int>::value)
		cur_data = (TData)(*str - '0')
	else if (is_same<TData,char>::value)
	{
		cur_data = *str;
	}

	str++;

	subtree_root = new child_sibling_tree::ChildSiblingNode<TData>(cur_data);
	if (!subtree_root)
		throw bad_alloc();

	this->createSubtreeByPreorderStringRecursive_(subtree_root->first_child,str);
	this->createSubtreeByPreorderStringRecursive_(subtree_root->next_sibling,str);
}

template<class TData>
inline int ChildSiblingTree<TData>::nodeCountOfSubtreeRecursive_(child_sibling_tree::ChildSiblingNode<TData>* subtree_root)
{
	// 空树处理
	if (!subtree_root)
		return 0;

	// 递归
	int node_count = 1; // subtree_root算一个

	node_count += this->nodeCountOfSubtreeRecursive_(subtree_root->first_child);
	node_count += this->nodeCountOfSubtreeRecursive_(subtree_root->next_sibling);

	// 返回结果
	return node_count;
}

template<class TData>
inline int ChildSiblingTree<TData>::maxHeightWithYoungerSiblingTreesRecursive_(child_sibling_tree::ChildSiblingNode<TData>* subtree_root)
{
	// 空树处理
	if (!subtree_root)
		return 0;

	// 递归
	int self_height = this->maxHeightWithYoungerSiblingTreesRecursive_(subtree_root->first_child) + 1;
	int max_younger_sibling_height = this->maxHeightWithYoungerSiblingTreesRecursive_(subtree_root->next_sibling);

	int max_height = (self_height > max_younger_sibling_height) ? self_height : max_younger_sibling_height;

	return max_height;
}

template<class TData>
inline void ChildSiblingTree<TData>::printSubTreeRecursive_(child_sibling_tree::ChildSiblingNode<TData>* subtree_root)
{
	// 空树处理
	if (!subtree_root)
		return;

	// 打印‘（’和子树根结点
	cout << '(';
	cout << subtree_root->data;

	// 递归打印所有孩子节点的子树
	for (child_sibling_tree::ChildSiblingNode<TData>* cur = subtree_root->first_child; cur != NULL; cur = cur->next_sibling)
	{
		this->printSubTreeRecursive_(cur);
	}

	cout << ')';
}