面试题(5)-面试中常考的树(2)_什么是二叉树和二叉树的遍历
1.什么是二叉树
二叉树需要满足两个条件:
本质上为有序树；
每个结点的度(结点拥有子树的个数称为该结点的度)不能超过2，即结点的度仅能为0，1，2。
二叉树的性质
二叉树第i层的结点数最多为2^(i-1) (i>=1)。
深度为k的二叉树最多有2^k - 1个结点。
在任意一颗二叉树中，若终端结点（叶子结点）的个数为n0，度为2的结点树为n2，则n0=n2+1。
证明：设二叉树中度为1的结点数为n1，结点总数为n，则n = n0 + n1 +n2。同时，度为2的子结点共有2 * n2个，度为1的子结点共有n1个，总结点数=子结点数+根结点 故n = n2 * 2 + n1 +1。两等式联立得出n0 = n2 +1。
二叉树的分类：
1.满二叉树：
若二叉树中除了叶子结点，每一个节点的度都为2，则称此二叉树为满二叉树。
满二叉树具有以下性质：
满二叉树的第i层结点数为2^(i-1)；
深度为k的满二叉树有2^k - 1个结点，叶子结点有2^(k-1)个；
具有n个结点的满二叉树的深度为log2(n+1)；
满二叉树中不存在度为1的结点，叶子结点仅存在在最底层。
2.完全二叉树
若二叉树除了最后一层结点满足满二叉树的定义，且最后一层节点满足从左到右分布的次序，则该二叉树被称为完全二叉树。
完全二叉树除了满足普通二叉树的性质外，还满足以下性质：
n个结点的完全二叉树的深度为[log2n]+1;
将完全二叉树按照层次从左到右编号，
（1）当i > 1时，序号为i的结点的父结点为结点[i / 2]；
（2）若2i > n, 则序号为i的结点无左子女结点，否则该节点的左子女结点序号为2i；
（3）若2i+1>n，则序号为i的结点无右子女结点，否则该结点的右子女结点的序号为2i+1。
二叉树的存储方式
二叉树的存储方式有两种，顺序存储和链式存储。
1.顺序存储
顺序存储只适用于完全二叉树，若想存储普通二叉树，需要先将其转化为完全二叉树。满二叉树也是一种特殊的完全二叉树。普通二叉树转化成完全二叉树的方法如下
对于完全二叉树的存储，仅需对其从根节点开始仅需编号，使用数组存储编号即可。取出式依据完全二叉树由左到右分布的性质恢复即可。
2.链式存储
顺序存储会造成一定程度上的空间浪费，链式存储可以很好地解决这个问题。链式存储中每个结点包含三部分：左孩子结点、数据域和右孩子结点。
链式存储的JAVA实现为：
2.二叉树的遍历
二叉树的遍历指从根结点出发，按照某种次序依次访问二叉树中所有的结点，每个结点被访问的次数有且仅有一次。
1.前序遍历：
前序遍历的思想是：（根左右）
先访问根结点；
访问当前结点的左子树；
访问当前结点的右子树。
遍历顺序为：A -> B -> D -> E -> C -> F -> G
2.中序遍历：
中序遍历的思路是：（左根右）
遇到一个节点，先缓存，看其是否有左子节点，若有，则输出左节点，再输出原节点，最后输出右节点。
中序遍历顺序为：D -> B -> E ->A -> F -> C -> G
3.后序遍历：
后续遍历的思路是：（左右根）
遇到一个节点，先缓存，看它是否存在左子节点，有则输出，接着看其是否有右子结点，最后输出原节点。
后序遍历顺序为：D -> E -> B -> F -> G -> C ->A
4.广度优先搜索(BFS)：
又称宽度优先搜索,层次遍历,广度优先搜索思路是：
先访问上一层，在访问下一层，从左至右进行遍历, 一层一层的往下访问
广度优先搜索为：A -> B -> C -> D -> E -> F ->G
5.深度优先搜索(DFS)：
深度优先搜索思路是：
他的访问顺序是：先访根节点，然后左结点，一直往下，直到最左结点没有子节点的时候然后往上退一步到父节点，然后父节点的右子节点在重复上面步骤……
深度优先搜索为：A -> B -> D -> E -> C -> F -> G
