概念
树的结构就很像生活中的树，一个枝干上分出很多的树杈。 在数据结构中，我们将树中的每个元素称为节点。没有父节点的叫做根节点。没有子节点的节点叫做叶子节点。如果多个节点的父节点是同一个节点，那么我们就将它们称为兄弟节点。
树还有 高度、深度、层。这三个概念
- 节点的高度： 节点到叶子节点的最长路径，也就是边数
- 节点的深度： 根节点到这个节点所经历的边的个数
- 节点的层数： 节点的深度+1
- 树的的高度： 根节点的高度
二叉树
每个节点上最多有两个叉。
满二叉树
除了叶子节点之外，每个节点都有左右两个子节点。
完全二叉树
最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大。
存储方式。
- 链式存储法。 每个节点有三个字段，一个存储数据，另外两个是指向左右节点的指针。
- 数组存储法。根节点在i=1的位置，左节点存储在2 i的位置，右节点存储在2 i + 1的位置。反过来 i/2存储的就是父节点的位置。 如果是完全二叉树，数组存储方式是最不占空间的。堆就是一种完全二叉树。
二叉树的遍历
- 前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
- 中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
- 后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。