正文
树是 n(n >= 0) 个结点的有限集合，当 n = 0 时称为空树。在任一非空树 (n > 0) 中，有且仅有一个称为根的结点；其余结点可分为 m(m >= 0) 个互不相交的有限子集 T1, T2, ..., Tm，其中，每个 T1 又都是一棵树，并且称为根结点的子树。
树的定义是递归的，它表明了树本身的固有特性，也就是一棵树由若干棵子树构成，而子树又由更小的子树构成。
从数据结构的逻辑关系角度来看，树中元素之间有严格的层次关系。对于树中的某个结点，它最多只和上一层的一个结点（即其双亲结点）有直接的关系，而与其下一层的多个结点（其孩子结点）有直接关系，如下图所示。通常，凡是分等级的分类方案都可以用具有严格层次关系的树结构来描述。
1. 树的重要概念
- 结点的度。一个结点的子树的个数记为该结点的度。 如上图所示，A、B 的度为 2，C 的度为 0，D 的度为 1。
- 叶子节点。叶子结点也成为了终端结点，指度为 0 的结点。
- 树的高度。一棵树的最大层数记为树的高度（或深度）。
2. 二叉树的存储结构
- 二叉树的顺序存储结构。用一组地址连续的存储单元存储二叉树中的结点，必须把结点排成一个适当的线性序列。并且结点在这个序列中的相互位置能反映出结点之间的逻辑关系。对于深度为 k 的完全二叉树，除第 k 层外，其余各层中含有最大的结点数，即每一层的结点数恰为其上一层结点数的两倍，由此从一个结点的编号可推知其双亲、左孩子和右孩子的编号。
- 二叉树的链式存储结构。由于二叉树的结点中包含有数据元素、左子树的根、右子树的根及双亲等信息，因此可以用三叉链表或二叉链表（即一个结点含有 3 个指针或两个指针）来存储二叉树，链表的头指针指向二叉树的根结点。
