作者：孙玉昌，昵称【一一哥】，另外【壹壹哥】也是我哦
千锋教育高级教研员、CSDN博客专家、万粉博主、阿里云专家博主、掘金优质作者
前言
在上一篇文章中，壹哥带大家一起学习认识了树型数据结构的定义和特点，并特别介绍了二叉树的遍历操作，分别有：前序遍历、中序遍历、后序遍历。前中后的核心区别是根据根节点在遍历过程中的位置决定的，即：根节点在最前面的称之为中序遍历，根节点在中间的称之为中序遍历，根节点在最后的称之为后序遍历。需要大家掌握根据树形结构写出对应的遍历序列结果的能力。
------------------------------前戏已做完，精彩即开始----------------------------
全文大约【3700】 字，不说废话，只讲可以让你学到技术、明白原理的纯干货！本文带有丰富的案例及配图视频，让你更好地理解和运用文中的技术概念，并可以给你带来具有足够启迪的思考......
配套开源项目资料
Github： github.com/SunLtd/Lear…
Gitee： 一一哥/从零开始学Java
一. 二叉树的编码实现
接下来壹哥就带大家，通过代码来进行二叉树的编码实现。
1. 定义二叉树的结点
对于树型数据结构中的结点，最多可以包含三部分：结点数据、左孩子子树、右孩子子树。我们使用Java对结点结构可以进行如下定义：
public class Node {
//结点中存储的数据
Object data;
//结点的左子树
Node left;
//结点的右子树
Node right;
//结点的高度
int height;
//构造方法
Node(Object data){
this.data = data;
}
Node(Object data,Node left,Node right){
this.data = data;
this.left = left;
this.right = right;
this.height = 0;
}
}
2. 二叉树的遍历实现
如上图所示，二叉树的根节点为A，向下第二层为B结点、C结点，依次类推。根据上图，我们很容易知道，若我们要对二叉树进行遍历，只需要从A结点出发，按照对应的前、中、后等不同的逻辑顺序进行遍历即可。因此，我们需要明确：在遍历二叉树时，只需要知道二叉树根节点即可。
2.1 前序遍历
public void prevOrderTraversal(Node root){
//若根节点为null，直接返回
if(root == null){
return;
}
//先序遍历，表示先访问根节点，故先输出传入的结点中的数据
System.out.printf("%s",root.data);
//遍历当前结点的左孩子结点
prevOrderTraversal(root.left);
//遍历当前结点的右孩子结点
prevOrderTraversal(root.right);
}
根据上述代码，若要执行前序遍历，只需要调用prevOrderTraversal时将A结点作为参数传入，即可得到打印的二叉树的前序遍历的结果：A B D C E G F H J。
2.2 中序遍历
public void inOrderTraversal(Node root){
if(root == null){
return;
}
//1、首先遍历当前root结点的左子树
inOrderTraversal(root.left);
//2、遍历当前结点root中的数据，并进行输出
System.out.printf("%s ",root.data);
//3、遍历当前结点root的右子树
inOrderTraversal(root.right);
}
中序遍历的代码编程如上，先遍历当前结点root的左子树，接着将当前结点root中元素输出，最后遍历当前结点root的右子树。调用上述inOrderTraversal函数，将A结点作为参数传入。可以得到中序二叉树中序遍历的结果为：B D A G E C H F I。
2.3 后序遍历
public void postOrderTraversal(Node root){
if(root == null){
return;
}
//1、先遍历当前结点的左子树
postOrderTraversal(root.left);
//2、先遍历当前结点的右子树
postOrderTraversal(root.right);
//3、最后当前结点的数据data
System.out.printf("%s ",root.data);
}
如上所示的后序遍历操作，在调用postOrderTraversal函数时，将树的根结点A作为参数传入。可以得到后序遍历的序列为：D B G E H I F C A。
2.4 层序遍历(广度遍历)
前面三种遍历方式前序、中序、后序均属于深度遍历，前文我们曾经提到，层序遍历又称广度遍历。主要是按层对树进行结点的遍历。在编程实现上，层序遍历与深度遍历的操作稍有不同，具体实现如下：
public void levelOrderTraversal(Node root){
if(root == null){
return;
}
Queue queue = new LinkedList();
//首先访问第1层的根节点
queue.add(root);
while(!queue.isEmpty()){
//从队列中取出一个结点，并输出该结点，意味着已经访问过该结点
Node node = queue.poll();
System.out.printf("%s ", node.data);
//判断并将该结点的左子树存入到队列中
if(node.left != null){
queue.add(node.left);
}
//判断并将该结点的右子树存入到队列中
if(node.right != null){
queue.add(node.right);
}
}
}
如上述代码所示，在进行层序遍历(广度遍历)时，我们借用了前面已经学习过的数据结构队列Queue，将每次访问的结点输出后，同时将结点的左右子树存入到队列中。因为我们知道队列的特点是，元素输入的顺序与输出的顺序会保持一致，因此在每次取数据时，总是先取出之前存入的数据；同时，又会把下一层数据(左右子树)存入队列中。最终，上述代码对树的层序遍历结果是：A B C D E F G H I。
二. 二叉查找树
1. 二叉查找树概念
二叉查找树，全称为Binary Search Tree，简称BST。从名字中我们容易理解，二叉查找树是在二叉树的基础上，同时具备了某些特性的一种特殊的二叉树型结构。二叉查找树相较于二叉树，额外满足以下几个条件：
(1). 若左子树不为空，则左子树上的所有结点的值均小于根结点位置上的值；
(2). 若右子树不为空，则右子树上的所有结点的值均大于根结点位置上的值；
(3). 左、右子树也都是二叉查找树。
总结上述几个条件的，我们可以用一居话概括二叉查找树的特点，左子树的数值小于根结点点数值，根结点数值小于右子树结点数值，整个二叉树结点的数值从左至右是有序的。
基于以上所总结的二叉查找树的特点，有的资料和教材也把查找树称之为二叉搜索树，以及二叉排序树(Binary Sort Tree，简称BST)。因此，大家要记住以下结论特征：左子树结点数值 < 根结点数值 < 右子树结点数值。
如上图所示，就是一棵二叉查找树：在此二叉查找树中，任意的子树都满足左子树结点数值 < 父结点数值 < 右子树结点数值的规律。
2. 二叉查找树的操作
二叉查找树最简单的操作是结点查找，其次，因为整个二叉查找树都满足从左至右是有序的，因此如果二叉查找树的结点数量发生变化，就会引起二叉查找树需要重新调整的操作，所以，我们此处还会讨论二叉查找树新增结点和删除结点的操作，最后二叉查找树与普通二叉树一样，都可以进行最基本的遍历操作。
接下来，我们依次讨论：结点查找、新增结点、删除结点、遍历二叉查找树。
2.1 结点查找
我们通过示例进行说明结点查找的逻辑，如下所示：
上图中是一个二叉查找树，现在我们希望查找数值5所在的结点。其具体的步骤如下：
①. 访问根节点，根结点数值位7；
②. 要查找的数值5 < 7，因此访问结点7的左子树结点，并获得左子树结点数值4；
③. 要查找的数值5 > 4，因此访问结点4的右子树结点，并获得右子树结点数值6；
④. 要查找的数值5 < 6，因此访问结点6的左子树结点，并获得左子树结点数值5；
⑤. 要查找的数值5 == 5，因此表示找到了目标数值5所在的结点。
时间复杂度分析：假设一课二叉查找树结点的个数为n，我们会发现在进行查找时，总是会先判断要查找的数值和当前结点的数值的大小，然后根据判断结果，选择其中一侧进行继续查找；而不符合条件的另外一侧子树，可以直接放弃，因为我们知道二叉查找树从左至右总是有序的。这种从左至右有序的二叉查找树，在进行查找时，可以极大的节省时间。实际上，使用二叉查找树查找某个结点，所需要的时间复杂度为O(log 2 n) ，该时间复杂度与树的深度O(log2n)是一样的。
2.2 新增结点
依然以上述二叉查找树为例，现在要插入数值为3的结点，示意图如下：
如上图，插入数值为3的结点的步骤如下：
①. 访问根结点，获得根结点数值7；
②. 要插入结点的数值3 < 7，因此访问根结点的左子树，并获得左子树结点的数值4；
③. 要插入结点的数值3 < 4，因此访问根结点的左子树，并获得左子树结点的数值2；
④. 要插入结点的数值3 > 2，因此访问根结点的右子树，但右子树为空；
⑤. 右子树为空，即意味着找到了要插入的位置，即将新增的数值位3的结点作为结点2的右子树。
时间复杂度分析：根据插入的步骤，我们可以非常容易的理解插入结点的操作时间复杂度也为O(log2n)，与查找结点时间复杂度相同。
2.3 删除结点
删除结点的操作与前面的查找和增加操作不太一样，删除操作需要分不同的情况进行讨论，原因是删除操作会使二叉查找树的结点减少，删除后需要让剩余的结点继续满足二叉查找树的规则和特点，就可能需要做出调整。
具体的，我们可以将删除结点操作分为三种情况：删除叶子结点、删除结点有1个子树、删除结点有2个子树。下面，我们详细进行讨论：
2.3.1 删除叶子结点
删除叶子结点是最简单的操作，因为叶子结点是最底层的结点，因此不需要任何的调整，直接删除即可。删除叶子结点不会对二叉查找树的性质产生影响。
2.3.2 删除结点有1个子树
当要删除的结点有1个子树时（可能是左子树，也可能是右子树）。我们需要将删除结点的子树结点，替换到删除结点的位置。比如，以下图为例：
如上图所示，我们希望删除数值位6的结点。由于结点6有一棵数值位5的左子树。因此，在将结点6删除后，将子结点5放在原来结点6的位置上，如上右图所示。
通过上述案例操作我们可以总结：当删除结点有1个子树结点时，直接将子结点放在删除结点的位置。
2.3.3 删除结点有2个子树
当删除结点有2个子树时，可以借助二叉树的中序遍历结果进行操作。具体步骤为：
(1). 找出二叉查找树的中序遍历序列；
(2). 找到要删除结点数值的前驱结点数值；
(3). 使用前驱结点数值替换删除的结点。
以下图为例：要删除二叉查找树的数值9所在的结点
如上图所示，删除步骤如下：
①. 根据图示的二叉查找树，得到中序遍历结果：1 2 4 5 6 7 8 9 10 12；
②. 确定要删除数值9的结点；
③. 在中序遍历结果序列中找到9的前驱8；
④. 使用数值8结点替换结点9，替换后入上右图所示。
2.4 遍历二叉查找树
我们已经知道二叉查找树是具有特殊性质的二叉树，因此二叉查找树的遍历与二叉树的遍历规则完全一致，此处我们就不再赘述。
------------------------------正片已结束，来根事后烟----------------------------
四. 结语
通过本篇内容，壹哥就带大家一起学习了二叉树的Java编程实现，其实，前序遍历、中序遍历、后序遍历的编程实现原理都是相同的，只是遍历的顺序不同而已。同时，在进行编程实现时，我们发现，无论前序、中序还是后序遍历，都出现了在函数内部继续调用函数本身的现象，在计算机编程中，我们把程序调用自己本身的折中操作称之为递归。各位感兴趣的读者，可以自己查阅资料，了解递归的相关概念和特点。
另外如果你独自学习觉得有很多困难，可以加入壹哥的学习互助群，大家一起交流学习。
