[从今天开始修炼数据结构]树，二叉树，线索二叉树，霍夫曼树
前面我们已经提到了线性表，栈，队列等数据结构，他们有一个共同的特性，就是结构中每一个元素都是一对一的，可是在现实中，还有很多一对多的情况需要处理，所以我们需要研究这种一对多的数据结构 —— 树，并运用它的特性来解决我们在编程中遇到的问题。
一、树的定义
1，树Tree是n(n >= 0) 个结点的有限集。n = 0时称为空树 在任意一棵非空的树中，
（1）有且仅有一个特定的根结点
（2）当n>1时，其余节点可分为m（m > 0）个互不相交的有限集T1,T2,.....,Tm，其中每一个集合又是一棵树，并且称为根的子树。如下图所示
注意：1，根节点是唯一的 2，子树的个数没有限制，但它们一定是互不相交的
2，结点分类
（1）结点包含一个数据元素以及若干指向其子树的分支。
（2）结点拥有的子树数量称为结点的度
（3）度为0的结点称为叶节点或终端节点
（4）度不为0的结点称为非终端结点或分支结点
（5）一棵树的度是树内各节点的度的最大值
3，结点间的关系
结点的子树的根称为该结点的孩子，该结点称为孩子的双亲。同一个双亲的孩子之间互称兄弟。结点的祖先是从根到该结点所经分支上的所有结点。反之，以某结点为根的子树中的任一结点都成为该结点的子孙。
4，树的其他相关概念
（1）结点的层次从根开始定义，根为第一层，根的孩子为第二层，以此类推。
（2）其双亲在同一层的结点互为表兄弟
（3）树中结点的最大层次称为树的深度或高度
（4）如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。
（5）森林是m（m >= 0）棵互不相交的树的集合
二、树的存储结构
我们介绍三种不同的表示方法：双亲表示法、孩子表示法、孩子兄弟表示法。
1，双亲表示法
结点可能没有孩子，但一定有双亲。假设我们以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点在数组中的位置。由于根节点没有双亲，所以我们约定根节点的位置域设为-1.下面是示例
| 下标 | data | parent |
| 0 | A | -1 |
| 1 | B | 0 |
| 2 | C | 0 |
| 3 | D | 1 |
| 4 | E | 2 |
| 5 | F | 2 |
| 6 | G | 3 |
| 7 | H | 3 |
| 8 | I | 3 |
| 9 | J | 4 |
这样的存储结构，我们可以根据结点的parent指针很容易找到双亲，时间复杂度O(1)。但如果我们要知道结点的孩子呢？对不起，请遍历整个结构才行。那么能不能改进一下呢？
我们增加一个结点最左边孩子的域，不妨叫他长子域，这样很容易得到结点的孩子。如果没有孩子的叶结点，这个长子域就设为-1，如下表
| 下标 | data | parent | firstchild |
| 0 | A | -1 | 1 |
| 1 | B | 0 | 3 |
| 2 | C | 0 | 4 |
| 3 | D | 1 | 6 |
| 4 | E | 2 | 9 |
| 5 | F | 2 | -1 |
| 6 |