#include<iostream>
using namespace std;

//链表结点
template<typename T>
struct ListNode {
	T data;
	ListNode* next;
	ListNode(T d):data(d),next(NULL){}
};

//树结点
template<typename T>
struct TreeNode {
	T data;
	ListNode<TreeNode<T>*>* childrenHead;

	TreeNode() {
		childrenHead = NULL;
	}
	// 添加子节点的函数
	void AddChild(TreeNode<T>* node) {
		ListNode<TreeNode<T>*>* childNode = new ListNode<TreeNode<T>*>(node);//子节点
		if (childrenHead == NULL) {
			childrenHead = childNode;//如果孩子链表为空
		}
		else {
			childNode->next = childrenHead;//childNode的后继记为childrenHead
			childrenHead = childNode;//把childrenHead变为插进来的那个节点
		}
	}
};

template<typename T>
class Tree {
private:
	TreeNode<T>* nodes;//树结点的节点集合，其实是个顺序表
	TreeNode<T>* root;//根节点的指针
public:
	Tree();//构造
	Tree(int maxNode);//指定最大节点数的构造函数
	~Tree();
	TreeNode<T>* GetTreeNode(int id);//通过id获取到实际树节点的指针
	void setRoot(int rootId);//设置一个根节点
	void AddChild(int parentId, int sonId);//指定父节点，和子节点，在父节点和子节点连一条边
	void AssignData(int nodeId, T data);//对该节点放入数据
	void Print(TreeNode<T>* node = NULL);//深入优先遍历打印

};

template<typename T>
Tree<T>::Tree() {
	nodes = new TreeNode<T>[100001];//默认有100001个元素的树节点
}

template<typename T>
Tree<T>::Tree(int maxNodes) {
	nodes = new TreeNode<T>[maxNodes];//设置有maxNodes个树节点
}


template<typename T>
Tree<T>::~Tree() {
	delete[] nodes;//把所有节点销毁
}

template<typename T>
TreeNode<T>* Tree<T>::GetTreeNode(int id) {
	return &nodes[id];//获取改id所对应的节点
}

template<typename T>
void Tree<T>::setRoot(int id) {
	root = GetTreeNode(id);//将该id的节点设置为成员变量
}

template<typename T>
void Tree<T>::AddChild(int parentId, int sonId) {
	TreeNode<T>* parentNode = GetTreeNode(parentId);
	TreeNode<T>* sonNode = GetTreeNode(sonId);
	//获得两个节点后
	parentNode->AddChild(sonNode);
}

template<typename T>
void Tree<T>::AssignData(int id, T data) {
	GetTreeNode(id)->data = data;
}

template<typename T>
void Tree<T>::Print(TreeNode<T>* node) {
	if (node == NULL) {
		node = root;
	}
	cout << node->data;
	ListNode<TreeNode<T>*>* tmp = node->childrenHead;
	while (tmp) {
		Print(tmp->data);
		tmp = tmp->next;
	}
}

int main() {
	Tree<char> T(9);
	T.setRoot(0);
	T.AssignData(0, 'a');
	T.AssignData(1, 'b');
	T.AssignData(2, 'c');
	T.AssignData(3, 'd');
	T.AssignData(4, 'e');
	T.AssignData(5, 'f');
	T.AssignData(6, 'g');
	T.AssignData(7, 'h');
	T.AssignData(8, 'i');

	T.AddChild(0, 2);
	T.AddChild(0, 1);
	T.AddChild(1, 3);
	T.AddChild(2, 5);
	T.AddChild(2, 4);
	T.AddChild(3, 8);
	T.AddChild(3, 7);
	T.AddChild(3, 6);

	T.Print();
}