1、树的理解性定义

树是分组、层次结构：

分组
树由树根和其余节点组成，而其余节点分为m（m>0)个互不相交的有限集，所以把这些有限集合称为原树的子树。
可以把每个子树理解为一组，而子树内部又递归的分组下去

与分组有关的术语：
森林（Forest），Tree＝（root，F），其中F为森林

层次
树状图本身是有层次的，这样利于高效查找

与层次相关的术语：
结点的层次（Level）、树的深度（Depth）
遍历：层次遍历

2、树的用处

基本上有序列（广义）的地方就可以应用树，因为树结构即是一种序列索引结构
序列的核心接口就是三个cha：插、查、X（增查删）

对于这个三个接口，我们要解决的核心问题是：
①效率：怎么查得快
②稳定：如果不支持增删，那么序列就是静态结构，用处不大。而支持增删之后，需要考虑如何保证序列内部结构不会被增删操作破坏，导致查询效率受到影响。

树通过其结构来表达了一种划分查找方法，这一方法相比于遍历搜索的复杂度O(n)，一般情况下复杂度仅有O(logn)。
树则可以动态改变存储空间，且运用一些手段来保护自身索引结构。

3、树的实现和二叉树

树转换为二叉树

由于二叉树是有序的，为了避免混淆，对于无序树，我们约定树中的每个结点的孩子结点按从左到右的顺序进行编号。
将树转换成二叉树的步骤是：
（1）加线。就是在所有兄弟结点之间加一条连线；
（2）抹线。就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线；
（3）旋转。就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。

树的表示

由于树中的每个结点的度不统一，所以显然，首先我们想到的是结构体加链表的形式对其进行表示，如下图所示：

Paste_Image.png
note: 但这种是不正确的实现方式
我们知道，当一棵树具有n个节点时，它具有n-1条边，而上述的表示方式则需要3n（因为树的度为3）个存储单元来存放树的边。这样一样，2n＋1个存储单元就被浪费了。因此为了减少上述浪费，实际编码时我们一般采用儿子-兄弟的表示方法：