树的简单理解

• 树的理解性定义
• 树的用处
• 树的实现和二叉树
• 树的遍历

1、树的理解性定义

树是分组、层次结构：

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

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

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

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

2、树的用处

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

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

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

3、树的实现和二叉树

树转换为二叉树

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

树的表示

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

• 树的结构体中包含：一个存放结点元素的单元，一个指向第一个儿子的指针和一个指向第一个兄弟的指针。

  
  

• 这样一来，我们表示一颗树，则只需要2n个存储单元来存储树的边，仅仅浪费n+1个存储单元。

当我们把上述树进行旋转45度时，发现这就是一颗二叉树了，因此大部分的树都可以转化为二叉树的形式进行表示。综上所述，树的算法大多围绕二叉树进行。

未完待续