一、树的定义
- 由节点和线组成
- 每个节点只有一个父节点，可以有若干个子节点
- 有一个节点没有父节点，此节点被称为根节点
二、树的术语解释
- 父节点：节点上面紧挨着的一个节点
- 子节点：一个节点生出来的节点
- 子孙节点：一个节点的后代
- 兄弟节点：同一个父节点的节点
- 深度：从根节点到最底层节点的层数称为深度，根节点称为第一层。
- 叶子结点：没有子节点的结点
- 非终端节点：也就是非叶子节点
- 度：子孙结点的个数
三、树的分类
一般树
任何一个节点的子节点的个数都不受限制
二叉树
任意一个节点的子节点个数最多是两个，且子节点的位置不能交换
一般二叉树
满二叉树
在不增加树的层数的情况下，无法再添加节点的树称之为满二叉树。（或者说，除最底层外，每个节点都有两个子节点）
完全二叉树
在一颗满二叉树的最底层的最右端开始删除若干个节点，形成的树就是完全二叉树。（满二叉树是完全二叉树的一种特例）
森林
n 个不相交的树的集合。
四、二叉树的连续存储
树的结构是非线性的，而计算机的存储是线性的，为了将树存储到计算机内部，人们规定了三种遍历的方法：先序遍历，中序遍历，后序遍历。
二叉树用连续存储的方式只能存储完全二叉树，如果不是完全二叉树，需要补充成完全二叉树。
如果不补充成完全二叉树，遍历的结果只有几个有效元素，根据数组里的这几个元素是没办法还原出原来的树的，所以必须要转化成完全二叉树。
- 优点：很容易找到一个节点的父节点，或者判断一个节点有没有子节点并找到子节点。
- 缺点：内存浪费大，因为可能要补充很多垃圾元素。
五、二叉树的链式存储
每个节点都是一个结构体，包含左、右结点指针域和数据域，指针域可以指向子节点，最底层节点的指针域用 NULL 表示。
- 优点：内存浪费小
- 缺点：不容易找到父节点
六、一般树的存储
双亲表示法
每个节点存储它父节点的下标。（找父节点方便）
孩子表示法
每个节点都有指针域来指向它的子节点。（找子节点方便）
孩子双亲表示法
每个节点既存储了父节点的下标，也有指针域指向它的子节点。（找父节点和子节点都很方便）
二叉树表示法
将一般树转换成二叉树来进行存储。
设法保证每一个节点的左指针域指向它的第一个子节点，右指针域指向它的第一个兄弟节点
七、森林的存储
将 n 棵树转换成二叉树来进行存储，具体做法跟一般树转换成二叉树相似。