1、二叉树的遍历
遍历是数据结构中常见的操作，主要是将所有元素都访问一遍。对于线性结构来说，遍历分为两种：正序遍历和逆序遍历。而对于树形结构来说，根据节点访问顺序不同，二叉树的遍历分为如下4种：
- 1、前序遍历（Preorder Traversal）
- 2、中序遍历(Inorder Traversal)
- 3、后序遍历(Postorder Traversal)
- 4、层序遍历(Levelorder Traversal)
注意：这4种遍历方式是二叉树的遍历方式，并不只是针对于二叉搜索树。
2、前序遍历(Preorder Traversal)
前序遍历节点的访问顺序：先访问根节点，前序遍历左子树、前序遍历右子树
前序遍历顺序.png
上图中遍历的节点的顺序如下：
先根节点"7"
然后 前序遍历左子树部分（"4"、"2"、"1"、"3"、"5"）
然后 前序遍历右子树部分（"9"、"8"、"11"、"10"、"12"）
2.1、使用递归方式实现前序遍历
public void preorder() {
preorder(root);
}
// 前序遍历---递归方式
private void preorder(Node<E> node) {
if (node == null)
return;
//这里只是将节点的元素打印出来，也可以通过接口回调的方式将其提供给执行者去处理遍历的节点
System.out.println(node.element);
preorder(node.left);
preorder(node.right);
}
2.2、使用迭代方式实现前序遍历
利用栈来实现：
- 1、将root入栈
- 2、循环执行以下操作，直到栈为空：
- 1、弹出栈顶节点top，进行访问。
- 2、将top.right入栈。
- 3、将top.left入栈。
image.png
代码实现如下：
// 前序遍历---迭代方式：使用栈来实现
/**
* 1、将root入栈 2、弹出栈顶元素 3、将栈顶元素的右子节点入栈 4、将栈顶元素的左子节点入栈 5、栈为空则结束遍历
*/
private void preorder2() {
if (root == null)
return;
Stack<Node<E>> stack = new Stack<>();
Node<E> node = root;
stack.add(node);
while (!stack.isEmpty()) {
node = stack.pop();
System.out.println(node.element);
if (node.right != null)
stack.add(node.right);
if (node.left != null)
stack.add(node.left);
}
}
3、中序遍历（Inorder Traversal）
-
节点的访问顺序: 先中序遍历左子树、根节点、中序遍历右子树。
遍历顺序如下图：
image.png
上图中遍历节点的顺序如下：
中序遍历左子树：（"1"、"2"、"3"、"4"、"5"）
根节点："7"
中序遍历右子树：（"8"、"9"、"10"、"11"、"12"）
- 如果访问的顺序：先中序遍历右子树、根节点、再中序遍历左子树，节点的访问顺序如下：
中序遍历右子树：（"12"、"11"、"10"、"9"、"8"）
根节点："7"
中序遍历左子树：（"5"、"4"、"3"、"2"、"1"）
由上可见：对于二叉搜索树来说：中序遍历的结果是升序或降序的。
3.1、使用递归方式实现中序遍历
// 中序遍历--递归方式实现
private void inorder(Node<E> node) {
if (node == null)
return;
inorder(node.left);
System.out.println(node.element);
inorder(node.right);
}
3.2、使用迭代方式实现中序遍历
利用栈来实现：
- 1、设置node=root。
- 2、循环执行如下操作：
- 1、如果node!=null
- a、将node入栈。
- b、设置node=node.left。 - 2、如果node==null
- a、如果栈为空则结束循环。
- b、如果栈不为空则出栈栈顶元素并赋值给node。
- c、对node进行访问。
- d、设置node=node.right。
image.png
- 1、如果node!=null
具体代码如下：
/**
* 中序遍历--使用迭代方式实现--使用栈来实现
* 1、设置node=root
* 2、进行如下循环操作：
* 1、如果node！=null
* a、将node入栈
* b、设置node=node.left
* 2、如果node==null
* a、如果栈为空则结束循环
* b、将栈顶元素出栈，并赋值给node
* c、对node进行访问
* d、设置node=node.right
*/
private void inorder2() {
if (root == null)
return;
Stack<Node<E>> stack = new Stack<>();
//设置node=root
Node<E> node = root;
while (true) {
/**
* 如果node不为空，将node加入到栈中
* 设置node=node.left
*/
if (node != null) {
stack.add(node);
node = node.left;
} else {
/**
* 如果node==null
* 此时如果栈为空，则退出循环
* 将栈顶元素出栈，并赋值给node
* 访问node
* 设置node=node.right
*/
if (stack.isEmpty())
break;
node = stack.pop();
System.out.println(node.element);
node = node.right;
}
}
}
4、后序遍历（Postorder Traversal）
访问顺序：先后序遍历左子树、再后序遍历右子树、根节点
遍历如下图：
image.png
节点输出顺序：
后序遍历左子树：（"1"、"3"、"2"、"5"、"4"）
后序遍历右子树：（"8"、"10"、"12"、"11"、"9"）
根节点："7"
4.1、递归方式实现后序遍历
// 递归方式实现后序遍历
private void postorder(Node<E> node) {
if (node == null)
return;
postorder(node.left);
postorder(node.right);
System.out.println(node.element);
}
5、层序遍历（Levelorder Traversal）
访问顺序：从上至下，从左到右，依次访问每一个节点
image.png
节点的访问顺序：
"7"、"4"、"9"、"2"、"5"、"8"、"11"、"1"、"3"、"10"、"12"
实现思路：由于是先进先出的，可以使用队列来实现。
- 1、将root入队
- 2、下面循环执行如下操作，直至队列为空：
- 1、将队头元素A出队，并访问队头。
- 2、将A的left入队
- 3、将A的right入队
实现代码如下：
// 层序遍历
public void levelorder() {
if (root == null)
return;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
System.out.println(node.element);
if (node.left != null)
queue.offer(node.left);
if (node.right != null)
queue.offer(node.right);
}
}
6、增强遍历接口
- 1、上面4种遍历方式，我们只是将遍历的元素打印出来，如果我们允许外部操作遍历的元素，就需要使用接口回调的方式来实现。下面以前序遍历为例：
public void preorder(Visitor<E> visitor) {
if (visitor == null)
return;
preorder(root, visitor);
// preorder2();
}
// 前序遍历---递归方式
private void preorder(Node<E> node, Visitor<E> visitor) {
if (node == null)
return;
visitor.visit(node.element);
preorder(node.left, visitor);
preorder(node.right, visitor);
}
public static interface Visitor<E> {
void visit(E e);
}
调用如下：
bst.preorder(new Visitor<Person>() {
@Override
public void visit(Person e) {
System.out.println(e);
}
});
- 2、上面4种遍历会将所有元素都进行遍历，如果我们想只对其中几个元素进行操作呢？该怎么处理？
比如在每次遍历到元素的值等于4时就不再向下遍历。我们第一想法肯定创建一个成员变量记录一下，那么4种遍历方式就需要创建4个成员变量来记录。其实不用这么麻烦，还记得在调用遍历方法时，传入了一个接口
Visitor，如果将这个接口改成抽象类，并在这个抽象类中增加一个成员变量来记录。
public static abstract class Visitor<E> {
public boolean stop;
public abstract boolean visit(E e);
}
public void preorder(Visitor<E> visitor) {
if (visitor == null)
return;
preorder(root, visitor);
}
// 前序遍历---递归方式
private void preorder(Node<E> node, Visitor<E> visitor) {
if (node == null || visitor.stop)
return;
visitor.stop = visitor.visit(node.element);
preorder(node.left, visitor);
preorder(node.right, visitor);
}
public void inorder(Visitor<E> visitor) {
if (visitor == null)
return;
inorder(root, visitor);
}
// 中序遍历--递归方式实现
private void inorder(Node<E> node, Visitor<E> visitor) {
if (node == null || visitor.stop)
return;
inorder(node.left, visitor);
// 在遍历左子树时visitor.stop可能已经为true，所以需要在此处加上判断
if (visitor.stop)
return;
visitor.stop = visitor.visit(node.element);
inorder(node.right, visitor);
}
// 后序遍历
public void postorder(Visitor<E> visitor) {
if (visitor == null)
return;
postorder(root, visitor);
}
// 递归方式实现后序遍历
private void postorder(Node<E> node, Visitor<E> visitor) {
if (node == null || visitor.stop)
return;
postorder(node.left, visitor);
postorder(node.right, visitor);
if (visitor.stop)
return;
visitor.stop = visitor.visit(node.element);
}
// 层序遍历
public void levelorder(Visitor<E> visitor) {
if (root == null || visitor == null)
return;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
if (visitor.visit(node.element))
break;
if (node.left != null)
queue.offer(node.left);
if (node.right != null)
queue.offer(node.right);
}
}
7、遍历的应用
- 前序遍历：树状结构的展示（注意左右子树的顺序）。
-
中序遍历：
二叉搜索树的中序遍历按升序或降序处理节点。 - 后序遍历：适用于一些先子后父的操作。
- 层序遍历：计算二叉树的高度和判断一棵树是否是完全二叉树。
7.1、利用前序遍历打印树状二叉树
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
toString(sb, root, "");
return sb.toString();
}
// 使用前序遍历方式打印二叉树
private void toString(StringBuilder sb, Node<E> node, String prefix) {
if (node == null)
return;
sb.append(prefix).append("【").append(node.element).append("】").append("\n");
toString(sb,node.left,prefix+"〖L〗");
toString(sb,node.right,prefix+"〖R〗");
}
打印结果如下
【4】
〖L〗【2】
〖L〗〖L〗【1】
〖L〗〖R〗【3】
〖R〗【6】
〖R〗〖L〗【5】
〖R〗〖R〗【7】
由于是前序遍历，所以【4】肯定是根节点，紧接着打印的【2】肯定是左子树的根节点，和其平级的【6】肯定是右子树的根节点。所以其树状结构如下：
┌───4_p_null──┐
│ │
┌─2_p_4─┐ ┌─6_p_4─┐
│ │ │ │
1_p_2 3_p_2 5_p_6 7_p_6
7.2、翻转二叉树
226. 翻转二叉树
翻转一棵二叉树。
示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
翻转二叉树是将每一个节点的左右子节点进行翻转，由于是每一个节点，所以需要进行遍历。由于我们是对每一个节点左右子节点进行翻转，每次要做的事情相同，我们可以使用递归来实现。
使用递归主要明确一下三点：
- 1、整个递归的终止条件是什么？
遍历完所有节点
- 2、一级递归需要做什么？
需要做的就是将当前节点的左右子节点进行交换。
- 3、应该返回给上一次的返回值是什么?
由于要返回的是二叉树翻转完成后的根节点，而翻转并不会改变跟节点，所以可直接返回root即可。
下面使用四种遍历方式来实现：
public class _226_翻转二叉树 {
// 使用前序遍历
public TreeNode invertTree1(TreeNode root) {
if (root == null)
return null;
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree1(root.left);
invertTree1(root.right);
return root;
}
// 使用中序遍历
public TreeNode invertTree2(TreeNode root) {
if (root == null)
return null;
invertTree2(root.left);
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree2(root.left);
return root;
}
// 后序遍历
public TreeNode invertTree3(TreeNode root) {
if (root == null)
return null;
invertTree3(root.left);
invertTree3(root.right);
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
return root;
}
// 层序遍历
public TreeNode invertTree4(TreeNode root) {
if (root == null)
return null;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
TreeNode tmp = node.left;
node.left = node.right;
node.right = tmp;
if (node.left != null)
queue.offer(node.left);
if (node.right != null)
queue.offer(node.right);
}
return root;
}
}
7.3、计算二叉树的高度
7.3.1、递归方式
- 1、终止条件
当遍历完所有节点，递归就终止了，因此当node为null时，就终止
- 2、找返回值
我们希望向上一级递归返回什么？由于是计算node节点的高度，node节点的高度等于其左子节点的高度和右子节点的高度中最大值加1。
- 3、本级递归需要做什么
需要计算该节点的左子节点和右子节点的高度，然后取最大值，再加上1就是该节点的高度。
具体实现如下：
private int height2(Node<E> node) {
if (node == null)
return 0;
return 1 + Math.max(height2(node.left), height2(node.right));
}
7.3.2、迭代方式
使用层序遍历方式遍历二叉树，一层一层进行遍历，遍历了多少层，就说明二叉树的高度是多少。问题就在于：如何知道何时遍历完了一层呢？
看下图
image.png
层序遍历使用队列实现的，在遍历完一层后（这一层元素全部出队），队列的size就是下一层元素的数量，具体实现如下：
private int height;// 树的高度
private int levelCount = 1;// 第一层的元素数量
// 计算二叉树的高度 使用层序遍历的方式
private int height(Node<E> node) {
if (node == null)
return 0;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(node);
while (!queue.isEmpty()) {
Node<E> newNode = queue.poll();
levelCount--;
if (newNode.left != null)
queue.offer(newNode.left);
if (newNode.right != null)
queue.offer(newNode.right);
if (levelCount == 0) {
levelCount = queue.size();
height++;
}
}
return height;
}
上面两个方法中传入的都是Node对象，在外部调用时，并不知道那个节点，这就需要实现一个通过元素来查找节点的方法。
//通过元素查找节点
public Node<E> node(E element) {
if (root == null)
return null;
Node<E> node = root;
int cmp = 0;
while (node != null) {
cmp = compare(element, node.element);
if (cmp == 0)
return node;
if (cmp > 0)
node = node.right;
else
node = node.left;
}
return null;
}
注意：该方法仅适用于二叉搜索树。
7.4、判断一棵树是否是完全二叉树
完全二叉树的特点：
- 1、完全二叉树是从左至右、从上至下进行编号和相同高度的满二叉树编号一致。
- 2、完全二叉树的叶子节点只能出现在最后两层，最后一层的叶子节点靠左对齐。
-
3、度为1的节点要么有0个，要么有1个。
image.png
那么该如何判断是一个完全二叉树呢？根据其特点可知，我们通过层序遍历的方式进行遍历。
- 1、如果树为空，则返回false。
- 2、如果树不为空，则使用层序遍历的方式进行遍历。
- 1、如果node.left!=null，将其入队
- 2、如果node.left==null&&node.right!=null，则返回false
- 3、如果node.right!=null，将其入队
- 4、如果node.right==null（node为叶子节点或度为1的节点，完全二叉树度为1的节点为0或1个）
- a、那么后面遍历的节点都是叶子节点，才是完全二叉树
- b、否则返回false - 3、遍历结束，返回true。
具体实现如下：
public boolean isCompleteTree() {
if (root == null)
return false;
boolean leaf = false;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
if (leaf && !node.isLeaf())
return false;
// 如果node.left!=null就入队
if (node.left != null)
queue.offer(node.left);
else { //
if (node.right != null)
return false;
// 和下面叶子节点判断重复，可去掉
// else if (node.right == null)
// leaf = true;
}
if (node.right != null)
queue.offer(node.right);
else {
// if(node.left!=null) {
// leaf = true;
// }else if(node.left==null) { //重复
// leaf = true;
// }
//如果遍历到的节点
// 上面判断重复,简化为
leaf = true;
}
}
return true;
}
调用方法测试
BinarySearchTree<Integer> bst =new BinarySearchTree<Integer>();
int[] array= {8,4,12,3,7,9,15,2,6};
for (int i : array) {
bst.add(i);
}
BinaryTrees.println(bst);
System.out.println(bst.isCompleteTree());
打印结果如下
┌───8_p_null───┐
│ │
┌─4_p_8─┐ ┌─12_p_8─┐
│ │ │ │
┌─3_p_4 ┌─7_p_4 9_p_12 15_p_12
│ │
2_p_3 6_p_7
false
如果我们想测试某个样子的树，就按照层序遍历的顺序将其加入树中即可。
8、重构二叉树
- 1、根据前序遍历结果+中序遍历结果、后序遍历结果+中序遍历结果可以确保构建出唯一的二叉树。
- 2、根据前序遍历结果+后序遍历结果不能确保构建出一个完整的二叉树，如果二叉树是真二叉树，那么可以构建出唯一的二叉树，否则不能。
8.1、根据前序遍历结果+中序遍历结果
我们以一个例子做一下这个过程，假设：
- 前序遍历的顺序是: CABGHEDF
- 中序遍历的顺序是: GBHACDEF
- 1、根据前序遍历结果可知根节点为：
C，然后根据中序遍历结果，可知左子树为：GBHA；右子树为：DEF。
C
/ \
GBHA DEF
- 2、取出左子树，左子树的前序遍历结果为：
ABGH，可知根节点为A；中序遍历为：GBHA，可知只有左子树：GBH
C
/ \
A DEF
/
GBH
- 3、使用同样的方法，左子树的前序为：
BGH，根节点为：B，左子树的中序为：GBH，G和H为根节点B的左右子节点。
C
/ \
A DEF
/
B
/ \
G H
- 4、回到右子树，右子树的前序遍历为：
EDF，根节点为E，右子树的中序遍历为：DEF，D和F为根节点E的左右子节点。
C
/ \
A E
/ / \
B D F
/ \
G H
其实就是在不断的找根节点，然后根据根节点，将树不断的分成左右子树。然后对于左子树和右子树再不断的找根节点，将树再次分成左右子树。下面使用递归来实现一下：
public class CreateTree {
// 已知前序加中序 输出后序
// 前序遍历的顺序是: CABGHEDF
// 中序遍历的顺序是: GBHACDEF
public static Node preAndMid(String preStr, String midStr) {
if (preStr == null || preStr.length() == 0 || midStr == null || midStr.length() == 0)
return null;
// 获取根节点
char rootElement = preStr.charAt(0);
Node root = new Node(String.valueOf(rootElement), null, null);
if (midStr.length() == 1)
return root;
// 获取根节点的值在中序遍历结果中的位置
int index = midStr.indexOf(rootElement);
String leftChildStr = midStr.substring(0, index);
if (leftChildStr.isEmpty()) { // 表示没有左子树
root.left = null;
} else {
root.left = preAndMid(preStr.substring(1, index + 1), leftChildStr);
}
String rightChildStr = midStr.substring(index + 1);
if (rightChildStr.isEmpty()) { // 表示没有右子树
root.right = null;
} else {
root.right = preAndMid(preStr.substring(index + 1), rightChildStr);
}
return root;
}
public static void postOrder(Node node) {
if (node == null)
return;
postOrder(node.left);
postOrder(node.right);
System.out.println(node.element);
}
private static class Node {
Node left;
Node right;
String element;
public Node(String element, Node left, Node right) {
this.left = left;
this.right = right;
this.element = element;
}
}
public static void main(String[] args) {
Node rootNode = preAndMid("CABGHEDF", "GBHACDEF");
postOrder(rootNode);
}
}
8.2、根据后序遍历结果+中序遍历结果
例如：
- 后续遍历结果为：GHBADFEC
- 中序遍历结果为：GBHACDEF
- 1、根据后续遍历可知，根节点为:
C，则可根据中序将其分为左子树：GBHA；右子树：DEF。
C
/ \
GHBA DEF
- 2、取出左子树，左子树的后序遍历结果为：
GHBA，可知根节点为A；中序遍历为：GBHA，可知只有左子树：GBH
C
/ \
A DEF
/
GBH
- 3、使用同样的方法，左子树的后序遍历结果为：
GHB，可知根节点为B，中序遍历为：GBH，可知G和H为B的左右子节点
C
/ \
A DEF
/
B
/ \
G H
- 4、回到右子树，右子树的后续遍历为
DFE，根节点为E，中序遍历为：DEF，D和F为根节点E的左右子节点
C
/ \
A E
/ / \
B D F
/ \
G H
依然是根据后续遍历的结果，找根节点，然后根据根节点将中序遍历结果，不断分成左右子树。
具体实现如下：
// 已知后序加中序 输出前序
// 后序遍历的顺序是: GHBADFEC
// 中序遍历的顺序是: GBHACDEF
public static Node postAndMid(String postStr, String midStr) {
if (postStr == null || postStr.length() == 0 || midStr == null || midStr.length() == 0)
return null;
// 获取根节点
char rootElement = postStr.charAt(postStr.length()-1);
Node root = new Node(String.valueOf(rootElement), null, null);
if (midStr.length() == 1)
return root;
// 获取根节点的值在中序遍历结果中的位置
int index = midStr.indexOf(rootElement);
String leftChildStr = midStr.substring(0, index);
if (leftChildStr.isEmpty()) { // 表示没有左子树
root.left = null;
} else {
root.left = postAndMid(postStr.substring(0, index), leftChildStr);
}
String rightChildStr = midStr.substring(index + 1);
if (rightChildStr.isEmpty()) { // 表示没有右子树
root.right = null;
} else {
root.right = postAndMid(postStr.substring(index ,postStr.length()-1), rightChildStr);
}
return root;
}
9、前驱结点和后继节点
9.1、前驱结点
前驱结点：中序遍历的前一个节点。如果是二叉搜索树，那么前驱结点就是前一个比它小的节点。
虽然前驱结点是针对所有二叉树，但是为了更好的理解，下面以二叉搜索树来举例，话不多说先上图：
image.png
中序遍历顺序为：先中序遍历左子树、然后根节点、最后中序遍历右子树，所以可知：
- 1、node.left!=null时，前驱结点==node.left.right.right....，终止条件为right==null。
- 2、node.left=null&&node.parent!=null时，前驱结点=node.parent.parent....，终止条件为node在parent的右子树中。
- 3、node.left==null&&node.parent==null时，没有前驱结点。
具体代码实现如下：
// 获取指定节点的前驱结点
private Node<E> precursor(Node<E> node) {
if (node == null)
return node;
Node<E> leftNode = node.left;
// node.left.right.right....
if (leftNode != null) {
while (leftNode.right != null) {
leftNode = leftNode.right;
}
return leftNode;
}
// node.parent.parent....
while (node.parent != null && node == node.parent.left) {
node = node.parent;
}
//走到这里条件 node.parent===null || node == node.parent.right
//这两种情况下都会返回node.parent
return node.parent;
}
9.2、后继节点
后继节点：中序遍历时的后一个节点。如果是二叉搜索树，那么后继节点就是后一个比它大的节点。
- 1、node.right!=null时，后继节点=node.right.left.left.....，终止条件为left==null。
- 2、node.right==null&&node.parent!=null时，后继节点=node.parent.parent.....，终止条件为node在parent的左子树中。
- 3、node.right==null&&node.parent==null时，没有后继节点。
具体的实现如下：
// 后继节点
private Node<E> successor(Node<E> node) {
if (node == null)
return null;
Node<E> rightNode = node.right;
// node.right.left.left....
if (rightNode != null) {
while (rightNode.left != null) {
rightNode = rightNode.left;
}
return rightNode;
}
// node.parent.parent...
while (node.parent != null && node != node.parent.left) {
node = node.parent;
}
return node.parent;
}
