#include<iostream>
#include<vector>
using namespace std;

/*首先用模板结构体的方式定义一般树的节点，这类树的节点采用双亲—孩子表示法来表示（将半线性结构转化为线性结构）*/
template<typename T>
struct NormalTreeNode
{
	T data;
	int parent;
	vector<unsigned> children;//使用一个向量来表示一个节点的孩子下标

	explicit NormalTreeNode(const T& data, const int& parent=-1) :data(data), parent(parent){}
	/*parent参数有默认值-1，表示将该节点作为一棵树的根节点*/
};

//此处为一个前向引用声明，因为接下来为了实现普通树转换成二叉树，需要将二叉树类声明为一般树类的友元类
template <typename T>
class BinTree;

/*同样采用模板类的形式来定义一棵一般树的类，借用STL中的向量结构来线性存储节点*/
template<typename T>
class NormalTree
{
private:
	vector<NormalTreeNode<T>> Nodes;//调用vector的好处之一就是可以只用一个数据成员来表示树结构
public:
	explicit NormalTree(const T& data) //一般树的构造函数，只负责构造一个根节点，并将其置入向量中
	{
		NormalTreeNode<T>* temp = new NormalTreeNode<T>(data);
		this->Nodes.push_back(*temp);
	}
	unsigned getSize(void)const//对外的接口函数，用于返回树中节点的个数，直接使用向量的size函数即可
	{
		return this->Nodes.size();
	}
	void insertNode(const T& data, const unsigned& parent)//插入节点的函数，做到了双向设置
	{
		Nodes[parent].children.push_back(this->Nodes.size());//首先让父节点记下自身的新的孩子的信息
		NormalTreeNode<T>* temp = new NormalTreeNode<T>(data, parent);//接着构造一个新的指定了父节点的节点，并将其插入向量中
		this->Nodes.push_back(*temp);
	}
	void show(void)const//这是一般树的遍历显示函数，用于显示树中所有节点的相关信息
	{
		cout << "该非二叉树的规模为：" << this->getSize() << endl;
		cout << "节点序号   " << "节点数据   " << "父节点   " << "孩子个数" << endl;
		for (unsigned i = 0; i < this->Nodes.size(); i++)
		{
			cout << i << "          " << Nodes[i].data << "      \t" << Nodes[i].parent << "\t" << Nodes[i].children.size() << endl;
		}
	}

	friend class BinTree<T>;//友元类的声明
};

/*这是二叉树的节点，采用长子-长兄表示法，同样也定义为模板结构体*/
template<typename T>
struct BinTreeNode
{
	//四个数据成员分别表示节点的数据域、父节点、长子和长兄
	T data;
	BinTreeNode<T>* parent;
	BinTreeNode<T>* first_child;
	BinTreeNode<T>* next_sibling;

	//二叉树节点的构造函数
	BinTreeNode(const T& val, BinTreeNode* p = nullptr) :data(val), parent(p), first_child(nullptr), next_sibling(nullptr) {}
	//同时，为了方便使用，保留一个默认构造函数
	BinTreeNode ()= default;
	//定义两个对外接口函数
	BinTreeNode<T> get_firstChild(void)const
	{
		return this->first_child;
	}
	BinTreeNode<T> get_nextSibling(void)const
	{
		return this->next_sibling;
	}
};

//再次定义一个前向引用声明，以便后序操作
template<typename T>
class ForestOfBinTrees;

//定义一个二叉树模板类，数据成员为指向根节点的指针，以及树中节点的个数
template<typename T>
class BinTree
{
private:
	BinTreeNode<T>* root;
	unsigned size;

	//定义一个从二叉树的某一个节点开始进行先序遍历并输出相关数据的函数
	void travers(BinTreeNode<T>* n)const
	{
		cout << n->data << "        ";//首先输出该节点的数据信息

		//接下来判断父节点是否为空，为空则输出表示父节点不存在的提示信息，否则输出父节点的数据
		if (n->parent == nullptr)
		{
			cout << "\\         ";
		}
		else
		{
			cout << n->parent->data << "         ";
		}

		//同理判断该节点是否存在长子，不存在则输出提示信息，否则输出孩子的数据
		if (n->first_child == nullptr)
		{
			cout << "\\     ";
		}
		else
		{
			cout << n->first_child->data << "     ";
		}

		//对于该节点的长兄，采用同样的思路
		if (n->next_sibling == nullptr)
		{
			cout << "\\" << endl;
		}
		else
		{
			cout << n->next_sibling->data << endl;
		}

		//对于该节点的信息输出完毕，按照先序遍历的顺序，递归判断是否遍历左右节点
		if (n->first_child != nullptr)
		{
			travers(n->first_child);
		}
		if (n->next_sibling != nullptr)
		{
			travers(n->next_sibling);
		}
	}

	//这是将已知节点插入二叉树的函数
	void insertNode(const BinTreeNode<T>& t)
	{
		this->insertNode(t.data, t.parent);
		this->size++;//最后将二叉树的规模自增1
	}

public:
	explicit BinTree(BinTreeNode<T>* root) :root(root), size(1) {}//一般的构造函数，通过指定根节点即可实现

	//这是将一般树转换成二叉树的函数，相当于一次类型转换
	explicit BinTree(const NormalTree<T>& temp) :root(nullptr), size(0)
	{
		//首先要做的一件事就是将一般树中的节点全部转化为二叉树的节点，并将这些节点储存在临时数组中备用（暂时只存储数据域）
		BinTreeNode<T>* tempPtr = new BinTreeNode<T>[temp.getSize()];
		for (unsigned i = 0; i < temp.getSize(); i++)
		{
			tempPtr[i] = *(new BinTreeNode<T>(temp.Nodes[i].data));
		}

		//接下来进行父节点的寻找操作，为临时向量中的每一个二叉树节点找到对应的父节点
		for (unsigned i = 0; i < temp.getSize(); i++)
		{
			if (temp.Nodes[i].parent != -1)
			{
				unsigned pos = temp.Nodes[i].parent;//首先找到节点的parent在临时指针中的存储位置
				tempPtr[i].parent = (&tempPtr[pos]);//对其父节点指针域进行赋值
			}
		}

		//最后将二叉树节点临时向量中的每一个节点插入到二叉树中即可
		for (unsigned i = 0; i < temp.getSize(); i++)
		{
			if (tempPtr[i].parent == nullptr)//这是根节点的情况，用来设置根节点
			{
				this->root = &tempPtr[i];
			}
			else//下面的步骤与insertNode函数的原理类似，不过多介绍
			{
				if (tempPtr[i].parent->first_child == nullptr)
				{
					tempPtr[i].parent->first_child = &tempPtr[i];
				}
				else
				{
					BinTreeNode<T>* Lookfor_LastSibling = tempPtr[i].parent->first_child;
					while (Lookfor_LastSibling->next_sibling != nullptr)
					{
						Lookfor_LastSibling = Lookfor_LastSibling->next_sibling;
					}
					Lookfor_LastSibling->next_sibling = &tempPtr[i];
				}
			}
			this->size++;
		}
	}

	//这是用二叉树森林合并成二叉树的构造函数
	explicit BinTree(ForestOfBinTrees<T>& f) :root(nullptr), size(0)
	{
		for (unsigned i = 0; i < f.getSize() - 1; i++)//对森林中的树进行遍历，并将每棵树的根节点的长兄设置为下一颗树的根节点
		{
			this->size += f.tp[i].getSize();//中间也需要更新树的规模，为森林中所有树的规模之和
			f.tp[i].root->next_sibling = f.tp[i + 1].root;
		}
		//最后将所得的根节点返回给构造函数本身
		this->root = f.tp[0].root;
		this->size += f.tp[f.getSize()-1].getSize();
	}

	//两个简单的对外接口函数，分别返回根节点和二叉树的规模
	BinTreeNode<T>* getRoot(void)const
	{
		return this->root;
	}
	unsigned getSize(void)const
	{
		return this->size;
	}

	//这是接口式的插入节点函数，需要指定节点的数据域与父节点的指针域
	BinTreeNode<T>* insertNode(const T& val, BinTreeNode<T>* parent)
	{
		BinTreeNode<T>* temp = new BinTreeNode<T>(val, parent);//首先通过数据域与父节点指针域创建一个新的节点
		if (parent->first_child == nullptr)//对父节点的长子指针域进行判定，如果为空，则进行修改
		{
			parent->first_child = temp;
		}
		else//当父节点的长子指针域不为空时，说明父节点已经有了孩子，则新插入的节点就是父节点的孩子的兄弟
		{
			BinTreeNode<T>* Lookfor_LastSibling = parent->first_child;
			while (Lookfor_LastSibling->next_sibling != nullptr)//通过遍历的方法找到父节点最小的一个孩子，再设置它的长兄为新节点
			{
				Lookfor_LastSibling = Lookfor_LastSibling->next_sibling;
			}
			Lookfor_LastSibling->next_sibling = temp;
		}
		this->size++;//最后更新树的规模
		return temp;
	}

	//这是用于显示二叉树所有信息的函数
	void show(void)const
	{
		cout << "二叉树的规模为：" << this->getSize() << endl;
		cout << "数据值   父节点   长子   长兄" << endl;
		this->travers(this->root);
	}
};

//这是一个二叉树森林类
template<typename T>
class ForestOfBinTrees
{
private:
	vector<BinTree<T>> tp;//用一个向量来存储森林中的所有二叉树，操作方便且容易理解
public:
	//此处采用默认构造函数对森林进行初始化即可
	ForestOfBinTrees() = default;

	//这是向森林中添加新二叉树的函数，直接使用向量的push_back方法即可
	void addTree(const BinTree<T>& t)
	{
		tp.push_back(t);
	}
	//这是对森林判空的函数，也可以直接调用向量的函数
	bool empty(void)const
	{
		if(this->tp.size() != 0)
		{
			return false;
		}
		return true;
	}
	//这是求森林中二叉树的个数的函数，直接调用向量函数
	unsigned getSize(void)const
	{
		return tp.size();
	}

	friend class BinTree<T>;//将二叉树类声明为友元类，方便调用函数
};

int main(void)
{
	//首先构造第一棵树，使用二叉树的方法构造，同时输出结果
	cout << "正在构造第一棵树...(二叉树）" << endl;
	BinTreeNode<char>* root1 = new BinTreeNode<char>('A');
	BinTree<char> myTree1(root1);
	BinTreeNode<char>* temp1 = myTree1.insertNode('B', root1);
	BinTreeNode<char>* temp2 = myTree1.insertNode('C', root1);
	BinTreeNode<char>* temp3 = myTree1.insertNode('E', temp1);
	BinTreeNode<char>* temp4 = myTree1.insertNode('F', temp1);
	BinTreeNode<char>* temp5 = myTree1.insertNode('G', temp2);
	BinTreeNode<char>* temp6 = myTree1.insertNode('D', temp2);
	cout << "构造完毕，输出构造结果：" << endl;
	myTree1.show();

	cout << endl;

	//接下来构造第二棵树，采用一般树的构造方法构造，同时输出结果
	cout << "正在构造第二棵树...（非二叉树）" << endl;
	NormalTree<char> tempTree('a');
	tempTree.insertNode('b', 0);
	tempTree.insertNode('c', 0);
	tempTree.insertNode('d', 0);
	tempTree.insertNode('e', 1);
	tempTree.insertNode('f', 1);
	tempTree.insertNode('g', 2);
	cout << "构造完毕，输出构造结果：" << endl;
	tempTree.show();

	cout << endl;

	//合并之前需要首先将第二棵树（非二叉树），转化成为二叉树，同时输出结果
	cout << "将第二棵树转化为二叉树..." << endl;
	BinTree<char> myTree2 = BinTree<char>(tempTree);
	myTree2.show();

	//将得到的两棵二叉树添加进入森林中
	ForestOfBinTrees<char> myForest;
	myForest.addTree(myTree1);
	myForest.addTree(myTree2);

	cout << endl;

	//合并两棵二叉树，得到一棵新的二叉树，输出结果
	cout << "下面将森林转化成为二叉树..." << endl;
	BinTree<char> myTree3 = BinTree<char>(myForest);
	myTree3.show();

	return 0;
}