2021 年 Java 工作或更难找，华为 Java 面试社招

### 二叉树 #### 定义 **二叉树**是`n(n>=0)`个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。 #### 图解  #### 二叉树特点 由二叉树定义以及图示分析得出二叉树有以下特点： 1. 每个结点最多有两颗子树，所以二叉树中不存在度大于 2 的结点。 2. 左子树和右子树是有顺序的，次序不能任意颠倒。 3. 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。 #### 二叉树性质 由二叉树定义以及图示分析得出二叉树有以下性质： 1.  2.  3.  4.  5. 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点有如下特性： > * 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点; > * 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点； > * 若 2i+1>n，则该结点无右孩子结点， 否则，编号为 2i+1 的结点为其右孩子结点。 ### 斜树 #### 定义 **斜树**：所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。  ### 满二叉树 #### 图解  #### 定义 **满二叉树**：在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。 #### 满二叉树的特点 满二叉树的特点有： 1. 叶子只能出现在最下一层。出现在其它层就不可能达成平衡。 2. 非叶子结点的度一定是 2。 3. 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。 ### 完全二叉树 #### 图解  #### 定义 **完全二叉树**：对一颗具有 n 个结点的二叉树按层编号，如果编号为 i(1<=i<=n)的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。 #### 完全二叉树特点 **特点**： 1. 叶子结点只能出现在最下层和次下层。 2. 最下层的叶子结点集中在树的左部。 3. 倒数第二层若存在叶子结点，一定在右部连续位置。 4. 如果结点度为 1，则该结点只有左孩子，即没有右子树。 5. 同样结点数目的二叉树，完全二叉树深度最小。 6. **注**：满二叉树一定是完全二叉树，但反过来不一定成立。 ### 二叉树的存储结构 #### 定义 二叉树的顺序存储结构就是使用一维数组存储二叉树中的结点，并且结点的存储位置，就是数组的下标索引。 #### 图解  如图一棵完全二叉树按照顺序存储： ### 二叉树遍历 #### 定义 **二叉树的遍历**是指从二叉树的根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。 #### 访问次序 二叉树的访问次序可以分为四种： 1. 前序遍历 根结点 > 左子树 > 右子树 2. 中序遍历 左子树> 根结点 > 右子树 3. 后序遍历 左子树 > 右子树 > 根结点 4. 层序遍历 仅仅需按层次遍历就可以 #### 图解  #### 前序遍历 ##### 定义 **前序遍历**通俗的说就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。 ##### 遍历流程 ``` 1、从根结点出发，则第一次到达结点 A，故输出 A; 2、继续向左访问，第一次访问结点 B，故输出 B； 3、按照同样规则，输出 D，输出 H； 4、当到达叶子结点 H，返回到 D，此时已经是第二次到达 D，故不在输出 D，进而向 D 右子树访问，D 右子树不为空，则访问至 I，第一次到达 I，则输出 I； 5、I 为叶子结点，则返回到 D，D 左右子树已经访问完毕，则返回到 B，进而到 B 右子树，第一次到达 E，故输出 E； 6、向 E 左子树，故输出 J； 7、按照同样的访问规则，继续输出 C、F、G； ``` ##### 遍历结果 > 前序遍历输出为：**ABDHIEJCFG** #### 中序遍历 ##### 定义 **中序遍历**就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。 ##### 遍历流程 ``` 1、从根结点出发，则第一次到达结点 A，不输出 A，继续向左访问，第一次访问结点 B，不输出 B；继续到达 D，H； 2、到达 H，H 左子树为空，则返回到 H，此时第二次访问 H，故输出 H； 3、H 右子树为空，则返回至 D，此时第二次到达 D，故输出 D； 4、由 D 返回至 B，第二次到达 B，故输出 B； 5、按照同样规则继续访问，输出 J、E、A、F、C、G； ``` ##### 遍历结果 > 中序遍历输出为：**HDIBJEAFCG** # 最后 每年转战互联网行业的人很多，说白了也是冲着高薪去的，不管你是即将步入这个行业还是想转行，学习是必不可少的。作为一个 Java 开发，学习成了日常生活的一部分，不学习你就会被这个行业淘汰，这也是这个行业残酷的现实。 如果你对 Java 感兴趣，想要转行改变自己，那就要趁着机遇行动起来。或许，这份**限量版的 Java 零基础宝典**能够对你有所帮助。 **[开源分享：【一线大厂 Java 面试题解析+核心总结学习笔记+最新讲解视频+实战项目源码】](https://ali1024.coding.net/public/P7/Java/git)**