数据结构与算法-二叉树(一)
二叉树的理解
在理解树的基本概念和结构后接下来我们学习最常用的一种树——二叉树，如下图所示：
从图中可以观察到，每个节点最多有两个分支，也就是两个节点，一般称为左子节点和右子节点。注意，是最多有两个节点，而不是必须有两个节点。像上图中的C节点只有一个节点（右子节点）。
完全二叉树和满二叉树
在二叉树中有两种特殊的二叉树，分别是完全二叉树和满二叉树。
完全二叉树
如上图所示，节点F、G、H、I和J是叶子节点，这些叶子节点都在最后的两层，最后一层的叶子节点靠左排列，并且除最后一层外，其他层的节点个数达到最大，这样的二叉树即为完全二叉树。
满二叉树
如上图所示，节点D、E、F和G是叶子节点，这些叶子节点都在最后一层，且除了叶子节点外其他的节点都有左右两个子节点，这样的二叉树即为满二叉树。
二叉树的存储方式
对于二叉树的存储，可以通过链式存储法和顺序存储法分别存储。
链式存储法
观察上图可以知道，对于每个节点有三个字段，其中 data表示存储数据， left表示指向左子节点的指针， right表示指向右子节点的指针。如果我们知道了一颗二叉树的根节点，则我们可以通过左右子节点的指针进行查找。大部分的二叉树的代码都是通过链式存储法来实现的。
顺序存储法
观察上图可以知道，当二叉树中的某一个节点 index为i，则它的左子节点的 index为 2*i+1，它的右子节点的 index为 2*i+2，它的父节点的 index为 i/2。因此，我们只要知道根节点的 index，则可以通过上述表达式进行查找。对于使用顺序存储法时，需要申请连续的内存空间，因此对于节点个数不多完全二叉树和满二叉树比较合适，但是对于不完全二叉树就会造成大量的空间浪费。
二叉树的前序遍历、中序遍历和后序遍历
在对二叉树遍历时，前序、中序和后序是指当前节点与它的左右子节点的打印现后顺序。
- 前序遍历：先打印当前节点，然后打印左子树，最后打印右子树。当前节点 -> 左子树 -> 右子树；
- 中序遍历：先打印左子树，然后打印当前节点，最后打印右子树。左子树 -> 当前节点 -> 右子树；
- 后序遍历：先打印左子树，然后打印右子树，最后打印当前节点。左子树 -> 右子树 -> 当前节点。
对上面二叉树的打印顺序分别为：
- 前序遍历：A -> B -> D -> E -> C -> F -> G
- 中序遍历：D -> B -> E -> A -> F -> C -> G
- 后序遍历：D -> E -> B -> F -> G -> C -> A