一、概念
1、定义
树是n个结点的有限结合。
n = 0 时
树为空树。
当n > 0 时
1、有且仅有一个特定的结点，称为根节点Root
2、 当 n > 1 时，其余结点分为m个互不相交的有限结合， T1、 T2、T3、....... Tm，其中每一个Ti又是一棵树，并且为Root的子树
子树的个数没有限制，但他们一定是不相交的。
2、结点
概念
树的结点包含一个数据域和m个指针域，指针域用来指向它的子树。
结点的类型分为：根节点，叶子节点，内部结点。
①一个树的根节点只有一个
②度为0的结点被称为叶子结点，叶子结点不能指向任何子树
③除了根节点和叶子结点以外，都被称为内部节点
结点拥有的子树的个数称为结点的度。
树中各个结点的度的最大值称为树的度。
3、结点的关系
1、孩子节点
对于某个结点，它的子树的根结点被称为该节点的孩子结点
2、父节点
上述的那个结点被称为父结点
3、兄弟结点
同一个父结点下的孩子结点互相称为兄弟结点
4、树的深度
结点的层次，从根节点开始记为第1层，如果某个结点在第i层，则它子树的根节点在第i+1层。
树中结点的最大层次称为树的深度。
5、森林
定义
森林是m棵互不相交的树的集合。对于树的每个结点而言，其子树的集合就是森林。
二、树的数据结构表示
1、结点id
为了方便树的数据的读取和修改，一般用一个数字来代表树的结点，这个数字就是树的结点id。
2、结点池
结点一般是有限的，所以我们可以事先将所有的结点储存在一个顺序表中，然后通过 结点id 索引的方法，快速获取到对应的结点，这个顺序表就是结点池。
3、结点数据
树的结点数据可以是任意的。
4、孩子结点列表
每个结点都要保存一个孩子结点列表（叶子结点的孩子结点列表是空的），可以通过顺序表或链表来实现对孩子结点的存储。
5、添加树边
可以通过树的结点id先获取到实际的树节结点，然后将孩子结点添加到父结点的孩子结点列表来完成。
6、树的遍历
递归来遍历
代码演示
#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指针类型的链表头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;childrenHead = childNode;}}
};//定义一棵树
template<typename T>
class Tree {
private:TreeNode<T>* nodes; //树结点的结点集合TreeNode<T>* root; //根结点的指针
public:Tree(); //构造函数Tree(int maxNodes);~Tree();TreeNode<T>* GetTreeNode(int id); //获得这个id代表的结点void SetRoot(int rootId); //设置一个根结点void AddChild(int parentId, int sonId); // 指定跟结点id 以及子结点idvoid AssignData(int nodeId, T data); // 为这个结点id置上数据域void Print(TreeNode<T>* node = NULL); // 用深度优先打印这个树
};//树的构造
template<typename T>
Tree<T> ::Tree(int maxNodes) {nodes = new TreeNode<T>[maxNodes]; //先把结点申请出来,指定maxNodes个结点}//树的析构函数
template<typename T>
Tree<T> :: ~Tree() {delete[] nodes; //把所有的结点都销毁掉
}//获取树结点的操作, 根据这个id获取到树的结点
template<typename T>
TreeNode<T>* Tree<T> :: GetTreeNode(int id) {return &nodes[id]; //取地址，然后返回
}//设置根结点
template<typename T>
void Tree<T> ::SetRoot(int id) { root = GetTreeNode(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); //传进的最大结点数是9T.SetRoot(0); //把第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, 6);T.Print();return 0;
}