数据结构与算法 - 二叉树
啥是树
"树"这种数据结构和我们生活中的树很像。里面的每个元素我们都称为节点，用线来连线相邻节点之间的关系，我们叫做父子节点。
树的结构
跟 HTML 的结构是一样的。
比如下面这幅图，A 节点就是 B 节点的父节点，B 节点就是 A 的子节点。B C D 的节点都是同一个节点，所以他们之间互称为兄弟节点。我们把没有父节点的节点叫做跟节点，比如图中的 E。没有子节点的叫做叶子节点或者叶节点，比如图中的 G H I J K L 。
树的概念
树的高度、深度和层。
高度 从下往上测量的，就像我们要测量一个10层高的楼层，都是从地面开始计算，在这里树的结构也是一样的，从最底层开始计算，计算的起点是0。
深度从上向下测量，比如测量水中的深度，从水平面向下测量，树的结构也是这样的，从跟节点开始计算，计算的起点是0。
层 和深度计算的基本一样，只不过层是从 1开始计算。
二叉树
二叉树，每个节点最多有两个叉，也就是 2 个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点，都有 2 个子节点。所以下面的都是
不过上图中的 2 号 3号比较特殊些。
2 号二叉树中，叶子节点全部都在最底层，除了叶子节点之外，每个节点都是 2 个子节点，这种的叫做满二叉树。
3 号二叉树中，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都达到最大，这种的叫做完全二叉树。
存储二叉树
二叉树有 2 种方法可以存储，分别是基于指针或引用的二叉链式存储法和基于数组的顺序存储法。
链式存储法比较简单和直观，是常用的二叉树方式。每个节点都有 3 个字段，一个存储数据，另外 2 个是指左右子节点的指针。我们只要拎住根节点，就可以通过左右子节点的指针，把整颗树串起来。
顺序存储法基于数组的。
根节点存储在 i = 1 的位置。
左子节点存储在 2 * i (2 * 1 = 2) 的位置
右子节点存储在2 * i + 1(2 * 1 + 1 = 3) 的位置
上图中，B 节点的左子节点存储在 2 * i = 2 * 2 = 4 的位置
右子节点的存储在 2 * i + 1 = 2 * 2 + 1 = 5 的位置。
总结： 节点 X 存储在数组中的下标为 i 的位置，左子节点的位置就是下标为 2 * i，右子节点的位置就是下标为 2 * i + 1 的位置。返过来，下标为 i/2 的位置就是它的父节点，通过这种方式，我们只要知道根节点的存储位置，就可以通过下标计算，把整颗树串起来。
刚刚举例的是一个完全二叉树，所以只浪费了一个下标为 0 的存储位置，如果是非完全二叉树，会浪费更多的数组存储空间。比如图下。
遍历二叉树
前序遍历、中序遍历、后序遍历是遍历二叉树的三种经典方法。
前序遍历是指对于树的任意节点来说，先打印这个节点，然后在打印它的左子节点，最后打印右子节点。
中序遍历是指对于树的任意节点来说，先打印它的左子树，在打印它的本身，最后在打印右子树。
后序遍历是指对于树的任意节点来说，先打印它的左子树，在打印它的右子树，最后在打印这个节点本身。
未完待续…