树
定义：树(Tree)是n(n>=0)个节点的有限集。当n=0时成为空树，在任意一棵非空树中：
- 有且仅有一个特定的称为根(Root)的节点；
- 当n>1时，其余节点可分为m(m>0)个互不相交的有限集T1、T2、...Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）
根节点
没有父节点的节点叫做根节点（图中的E）
叶节点
没有子节点的节点叫做叶子节点或者叶节点（图中的 G、H、I、J、K、L 都是叶子节点）
子树
子树由节点和它的后代构成。例如，节点F、K和L构成了图中树的一棵子树
树的高度（Height）、深度（Depth）、层（Level）
节点的高度：节点到叶子节点的最长路径（边数）
节点的深度：根节点到这个节点所经历的边的个数
节点的层：节点的深度+1
树的高度：根节点的高度
二叉树（Binary Tree）
二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。
这个图里面，有两个比较特殊的二叉树，分别是编号 2 和编号 3 这两个。
其中，编号 2 的二叉树中，叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫做满二叉树。
编号 3 的二叉树中，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。
存储一棵二叉树
两种方法，一种是基于指针或者引用的二叉链式存储法，一种是基于数组的顺序存储法。
比较简单、直观的链式存储法
每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。这种存储方式我们比较常用。大部分二叉树代码都是通过这种结构来实现的。
基于数组的顺序存储法
我们把根节点存储在下标 i = 1 的位置，那左子节点存储在下标 2 * i = 2 的位置，右子节点存储在 2 * i + 1 = 3 的位置。以此类推，B 节点的左子节点存储在 2 * i = 2 * 2 = 4 的位置，右子节点存储在 2 * i + 1 = 2 * 2 + 1 = 5 的位置。
总结：如果节点 X 存储在数组中下标为 i 的位置，下标为 2 * i 的位置存储的就是左子节点，下标为 2 * i + 1 的位置存储的就是右子节点。反过来，下标为 i/2 的位置存储就是它的父节点。通过这种方式，我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），这样就可以通过下标计算，把整棵树都串起来。
注意：如果是非完全二叉树，其实会浪费比较多的数组存储空间。所以，如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。这也是为什么完全二叉树会单独拎出来的原因，也是为什么完全二叉树要求最后一层的子节点都靠左的原因。
二叉树的遍历
经典的方法有三种，前序遍历、中序遍历和后序遍历。其中，前、中、后序，表示的是节点与它的左右子树节点遍历打印的先后顺序
前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
-
后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。
image.png
实际上，二叉树的前、中、后序遍历就是一个递归的过程。比如，前序遍历，其实就是先打印根节点，然后再递归地打印左子树，最后递归地打印右子树。
前序遍历的递推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
中序遍历的递推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
后序遍历的递推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r
PS:笔记内容来自 极客时间 数据结构与算法之美
