以前我们学的线性结构是一对一的线性关系，但现实中，还有一对多的情况要处理，那就是树形结构。今天我们将学习树的概念及结构、和树的三种常见表示方法。

树是一种非线性的数据结构，它是由n（n >= 0）个有限结点组成的一个具有层次关系的集合。

答案是： 因为它的逻辑图看起来像一颗倒挂的树，根朝上，叶向下。如下图：

空树： n=0时称为空树。

根节点： 有且仅有一个特定的结点，称为根(Root)节点。（根节点没有前驱结点） 树是递归实现的： 当n>1时，除根节点外，其余结点可分为m（m>0）个互不相交的有限集T1,T2,……Tm，其中每一个集合Ti（1 PTNode* a;//指向堆区开辟的节点数组 int root;//根节点的位置 int size;//结点数 }PTree;

如下图中树结构和树双亲表示所示： 优缺点： 优点：①找双亲容易；②顺序存储。 缺点：找孩子难，需要遍历整个结构。

定义： 由于树中每个结点可能有多棵子树，可以考虑用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根节点，我们把这种方法叫做多重链表表示法。 因为树的每个结点的度，也就是它的孩子个数是不同的。所以我们有两种设计方案来解决。 方案一（树的度已知）：结点同构 ——已知树的度为d，指针域的个数就等于树的度。其结构如下图： 其中data是数据域，child1到childd是指针域，用来指向该结点的孩子结点。 代码示例：

如下左图的树，树的度是3，所以指针域的个数是3，孩子表示如下右图所示： 如图我们可知这种方法当树中很多结点的度小于d时，结点中有很多指针域为空，空间浪费。 方案二（树的度未知）：孩子表示法——理解两个结构：①孩子结点；②表头结点。然后使用顺序存储实现孩子表示法。 如图所示：

①孩子结点： 就是用单链表存储某个结点的所有孩子结点的地址（注：n个结点有n个孩子链表，如果是叶子结点则该链表为空。）结构如下所示： ②表头结点： 有两个成员：data成员存储某个结点的数据信息；firstchild成员存储该结点孩子链表的头指针。结构如图所示： ③树结构： 由三个成员组成：指向表头数组的指针a、保存根位置的root、保存节点数的size。 代码示例：

定义： 我们观察发现，任意一棵树，它的节点的第一个孩子如果存在就是唯一，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟，也可叫做左兄弟右孩子法。结构如图所示： 代码示例：

如下图树结构与孩子兄弟的表示： 总结：这三种表示方法就是分别从孩子、双亲、兄弟的角度设计的。