二叉树详解：概念、存储、遍历及算法应用
二叉树详解：概念、存储、遍历及算法应用
二叉树的概念
二叉树是一种特殊的树型结构，它的特点是每个节点最多只有2棵子树（即二叉树中不存在度大于2的节点），并且二叉树的子树有左右之分，其次序不能任意颠倒。
- 满二叉树：一棵二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层上，那么这棵树就称为满二叉树。
- 完全二叉树：对一棵有n个节点的二叉树按层序编号，所有的节点的编号从1-n。如果这棵树所有节点和同样深度的满二叉树的编号为从1-n的节点位置相同，则这棵二叉树为完全二叉树。换句话说，就是在满二叉树的基础上，在最后一层的叶子结点上，从右往左依次删除若干个节点，剩下的就是一棵完全二叉树。
二叉树的存储
二叉树的存储方式主要有两种：顺序存储和链式存储。
顺序存储：顺序结构存储就是使用数组来存储。在完全二叉树以及满二叉树的性质那里，我们了解到：如果从根节点出发，按照层序遍历的顺序，由1开始编号，那么父子女之间的编号是可以计算出来的。那么在存储完全二叉树的时候，就按照编号，依次放在数组对应下标的位置上，然后通过计算找到左右孩子和父亲：
结点下标为i：
如果父存在，父下标为i/2；
如果左孩子存在，左孩子下标为i × 2；
如果右孩子存在，右孩子下标为i × 2 + 1
顺序存储结构一般只用于完全二叉树或满二叉树。链式存储：链式存储类比链表的存储，都有静态实现和动态实现的方式。竞赛中给定的树结构一般都有编号，因此可以创建两个数组l[N]和r[N]，其中l[i]表示结点号为i的结点的左孩子编号，r[i]表示结点号为i的结点的右孩子编号。这样就可以把二叉树存储起来。
二叉树的遍历
二叉树的遍历方法主要有深度优先遍历和广度优先遍历。
深度优先遍历：不同于常规树的深度优先遍历，二叉树因其独特的性质可以划分成三种深度优先遍历：先序遍历，中序遍历，和后序遍历。其中，三种遍历方式的不同在于处理根节点的时机。对于一棵二叉树而言，整体可以划分成三部分：根节点+左子树+右子树：
先序遍历的顺序为：根+左+右；
中序遍历的顺序为：左+根+右；
后序遍历的顺序为：左+右+根
广度优先遍历：和常规的树的遍历方式一样，直接用队列帮助层序遍历即可。
二叉树算法题
通过洛谷平台的几道例题来具体说明二叉树的应用：
P1305 新二叉树：建树时可以直接用ASCII码值当做下标来使用。比如 'a' 直接映射成97，l[97]里面就存着 'a' 的左孩子，r[97]里面就存着 'a' 的右孩子，以此类推，建立二叉树。
B3642 二叉树的遍历：通过递归实现先序、中序和后序遍历。
P4913 【深基16.例3】二叉树深度：二叉树的高度=1+max(左子树的高度，右子树的高度)；因此，可以递归解决。
P1030 [NOIP 2001 普及组] 求先序排列：已知「中序」和「后序」的基础上，如何求「先序」。根据后序遍历可知，最后一个元素A就是当前这棵树的根；根据中序遍历可知，根节点A会把整个序列分成两部分，左边是左子树，右边是右子树；那么我们就可以在后序遍历的序列中，也找出对应的左右子树；接下来根据划分情况，继续处理相应的子树。
P1827 [USACO3.4] 美国血统 American Heritage：通过递归实现中序遍历。
P3884 [JLOI2009] 二叉树问题：如何求x，y之间的距离。先从x向上爬，同时标记路径中，所有点到x的距离；接下来从y向上爬，当第一次遇到标记点时，更新结果。