遍历是数据结构中的常见操作
把所有元素都访问一遍
线性数据结构的遍历比较简单
- 正序遍历
- 逆序遍历
根据结点访问顺序的不同，二叉树的常见遍历方式有4种
- 前序遍历（
Preorder Traversal） - 中序遍历（
Inorder Traversal） - 后序遍历（
Postorder Traversal） - 层序遍历（
Level Order Traversal）
前序遍历（Preorder Traversal）
访问顺序
根节点、前序遍历左子树、前序遍历右子树
7、4、2、1、3、5、9、8、11、10、12
/**
* 前序遍历
*/
public void preorderTraversal() {
preorderTraversal(root);
}
private void preorderTraversal(Node<E> node) {
if (node == null) return;
System.out.println(node.element);
preorderTraversal(node.left);
preorderTraversal(node.right);
}
中序遍历（Inorder Traversal）
访问顺序
-
中序遍历左子树、根节点、中序遍历右子树
1、2、3、4、5、7、8、9、10、11、12
- 中序遍历右子树、根节点、中序遍历左子树
12、11、10、9、8 、7、5、4、3、2、1
二叉搜索树的中序遍历结果是升序或者降序的
/**
* 中序遍历
*/
public void inorderTraversal() {
inorderTraversal(root);
}
private void inorderTraversal(Node<E> node) {
if (node == null) return;
inorderTraversal(node.left);
System.out.println(node.element);
inorderTraversal(node.right);
}
后序遍历（Postorder Traversal）
后序遍历左子树、后序遍历右子树、根节点
1、3、2、5、4、8、10、12、11、9、7
/**
* 后序遍历
*/
public void postorderTraversal() {
postorderTraversal(root);
}
private void postorderTraversal(Node<E> node) {
if (node == null) return;
postorderTraversal(node.left);
postorderTraversal(node.right);
System.out.println(node.element);
}
层序遍历（Level Order Traversal）
从上到下、从左到右依次访问每一个节点
7、4、9、2、5、8、11、1、3、10、12
实现思路：使用队列
- 将根节点入队
- 循环执行以下操作，直到队列为空
将队头节点A出队，进行访问
将A的左子节点入队
将A的右子节点入队
/**
* 层序遍历
*/
public void levelOrderTraversal(){
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);
}
}
}
遍历接口设计
/**
* 前序遍历
*/
public void preorderTraversal(Visitor<E> visitor) {
preorderTraversal(root,visitor);
}
private void preorderTraversal(Node<E> node,Visitor<E> visitor) {
if (node == null || visitor == null) return;
visitor.visit(node.element);
preorderTraversal(node.left,visitor);
preorderTraversal(node.right,visitor);
}
/**
* 中序遍历
*/
public void inorderTraversal(Visitor<E> visitor) {
inorderTraversal(root,visitor);
}
private void inorderTraversal(Node<E> node,Visitor<E> visitor) {
if (node == null || visitor == null) return;
inorderTraversal(node.left,visitor);
visitor.visit(node.element);
inorderTraversal(node.right,visitor);
}
/**
* 后序遍历
*/
public void postorderTraversal(Visitor<E> visitor) {
postorderTraversal(root,visitor);
}
private void postorderTraversal(Node<E> node,Visitor<E> visitor) {
if (node == null || visitor == null) return;
postorderTraversal(node.left,visitor);
postorderTraversal(node.right,visitor);
visitor.visit(node.element);
}
/**
* 层序遍历
*/
public void levelOrderTraversal(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();
visitor.visit(node.element);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
public static interface Visitor<E> {
void visit(E elemet);
}
利用上一章节二叉搜索树调用层序遍历
package njf;
import java.util.Comparator;
import njf.printer.BinaryTreeInfo;
import njf.printer.BinaryTrees;
import njf.BinarySearchTree.Visitor;
import njf.file.Files;
public class Main {
static void test1() {
Integer data[] = new Integer[] {
7, 4, 9, 2, 5, 8, 11, 3, 12, 1
};
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
for (int i = 0; i < data.length; i++) {
bst.add(data[i]);
}
BinaryTrees.println(bst);
bst.levelOrderTraversal(new Visitor<Integer>() {
@Override
public void visit(Integer elemet) {
System.out.print("_" + elemet + "_");
}
});
// bst.preorderTraversal(new Visitor<Integer>() {
// @Override
// public void visit(Integer elemet) {
// System.out.print("_" + elemet + "_");
//
// }
// });
}
public static void main(String[] args) {
test1();
}
}
打印结果如下：
┌───7_p(null)───┐
│ │
┌─4_p(7)─┐ ┌─9_p(7)─┐
│ │ │ │
┌─2_p(4)─┐ 5_p(4) 8_p(9) 11_p(9)─┐
│ │ │
1_p(2) 3_p(2) 12_p(11)
_7__4__9__2__5__8__11__1__3__12_
遍历接口增强
/**
* 前序遍历
*/
public void preorderTraversal(Visitor<E> visitor) {
if (visitor == null) return;
preorderTraversal(root,visitor);
}
private void preorderTraversal(Node<E> node,Visitor<E> visitor) {
if (node == null || visitor.stop) return;
visitor.stop = visitor.visit(node.element);
preorderTraversal(node.left,visitor);
preorderTraversal(node.right,visitor);
return;
}
/**
* 中序遍历
*/
public void inorderTraversal(Visitor<E> visitor) {
if (visitor == null) return;
inorderTraversal(root,visitor);
}
private void inorderTraversal(Node<E> node,Visitor<E> visitor) {
if (node == null || visitor.stop) return;
inorderTraversal(node.left,visitor);
if (visitor.stop) return;
visitor.stop = visitor.visit(node.element);
inorderTraversal(node.right,visitor);
}
/**
* 后序遍历
*/
public void postorderTraversal(Visitor<E> visitor) {
if (visitor == null) return;
postorderTraversal(root,visitor);
}
private void postorderTraversal(Node<E> node,Visitor<E> visitor) {
if (node == null || visitor.stop) return;
postorderTraversal(node.left,visitor);
postorderTraversal(node.right,visitor);
if (visitor.stop) return;
visitor.stop = visitor.visit(node.element);
}
/**
* 层序遍历
*/
public void levelOrderTraversal(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)) return;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
/**
* java抽象类
*/
public static abstract class Visitor<E> {
boolean stop;
/**
* @return 如果返回true，就代表停止遍历
*/
public abstract boolean visit(E elemet);
}
利用上一章节二叉搜索树调用层序遍历
package njf;
import java.util.Comparator;
import njf.printer.BinaryTreeInfo;
import njf.printer.BinaryTrees;
import njf.BinarySearchTree.Visitor;
import njf.file.Files;
public class Main {
static void test5() {
Integer data[] = new Integer[] {
7, 4, 9, 2, 1
};
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
for (int i = 0; i < data.length; i++) {
bst.add(data[i]);
}
BinaryTrees.println(bst);
bst.preorderTraversal(new Visitor<Integer>() {
public boolean visit(Integer element) {
System.out.print(element + " ");
return element == 2 ? true : false;
}
});
System.out.println();
bst.inorderTraversal(new Visitor<Integer>() {
public boolean visit(Integer element) {
System.out.print(element + " ");
return element == 4 ? true : false;
}
});
System.out.println();
bst.postorderTraversal(new Visitor<Integer>() {
public boolean visit(Integer element) {
System.out.print(element + " ");
return element == 4 ? true : false;
}
});
System.out.println();
bst.levelOrderTraversal(new Visitor<Integer>() {
public boolean visit(Integer element) {
System.out.print(element + " ");
return element == 9 ? true : false;
}
});
System.out.println();
}
public static void main(String[] args) {
test5();
}
}
打印结果如下：
┌─7_p(null)─┐
│ │
┌─4_p(7) 9_p(7)
│
┌─2_p(4)
│
1_p(2)
7 4 2
1 2 4
1 2 4
7 4 9
前序遍历 – 非递归
public void preorder(Visitor<E> visitor) {
if (visitor == null || root == null) return;
Node<E> node = root;
Stack<Node<E>> stack = new Stack<>();
while (true) {
if (node != null) {
if (visitor.visit(node.element)) return;
if (node.right != null) {
stack.push(node.right);
}
node = node.left;
}else if(stack.isEmpty()){
return;
}else {
node = stack.pop();
}
}
}
public void preorder(Visitor<E> visitor) {
if (visitor == null || root == null) return;
Stack<Node<E>> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node<E> node = stack.pop();
if (visitor.visit(node.element)) return;
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
中序遍历 – 非递归
public void inorder(Visitor<E> visitor) {
if (visitor == null || root == null) return;
Stack<Node<E>> stack = new Stack<>();
Node<E> node = root;
while (true) {
if (node != null) {
stack.push(node);
node = node.left;
}else if (stack.isEmpty()) {
return;
}else {
node = stack.pop();
if (visitor.visit(node.element)) return;
node = node.right;
}
}
}
后序遍历 – 非递归
public void postorder(Visitor<E> visitor) {
if (visitor == null || root == null) return;
// 记录上一次弹出访问的节点
Node<E> prev = null;
Stack<Node<E>> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node<E> top = stack.peek();
if (top.isLeaf()|| (prev != null && prev.parent == top)) {//没有子节点
prev = stack.pop();
if (visitor.visit(prev.element)) return;
}else {
if (top.right != null) {
stack.push(top.right);
}
if (top.left != null) {
stack.push(top.left);
}
}
}
}
练习：计算二叉树的高度
- 递归法
public int height() {
return height(root);
}
/**
* 计算二叉树的高度，利用递归
*/
private int height(Node<E> node) {
if (node == null) return 0;
return 1 + Math.max(height(node.left), height(node.right));
}
- 层序遍历
/**
* 计算二叉树的高度，利用层序遍历
*/
public int height() {
if (root == null) return 0;
// 树的高度
int height = 0;
// 存储着每一层的元素数量
int levelSize = 1;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
levelSize --;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
if (levelSize == 0) {// 意味着即将要访问下一层
levelSize = queue.size();
height ++;
}
}
return height;
}
练习: 判断一棵树是否为完全二叉树
◼ 如果树为空，返回 false
◼ 如果树不为空，开始层序遍历二叉树(用队列)
如果
node.left!=null，将 node.left 入队如果
node.left==null && node.right!=null，返回 false如果
node.right!=null，将 node.right 入队如果
node.right==null那么后面遍历的节点应该都为叶子节点，才是完全二叉树
否则返回
false
代码实现
public boolean isCompleteTree() {
if (root == null) return false;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
boolean isLeaf = false;
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
//如果出现叶子结点，但是后面结点又不是叶子结点，false
if (isLeaf && !(node.left == null && node.right == null)) return false;
if (node.left != null) {
queue.offer(node.left);
}else if(node.right != null) {// node.left == null && node.right != null
return false;
}
if(node.right != null) {
queue.offer(node.right);
}else {// node.right == null
isLeaf = true;
}
}
return true;
}
利用上一章节二叉搜索树验证是否为完全二叉树
package njf;
import java.util.Comparator;
import njf.printer.BinaryTreeInfo;
import njf.printer.BinaryTrees;
import njf.BinarySearchTree.Visitor;
import njf.file.Files;
public class Main {
static void test7() {
Integer data[] = new Integer[] {
7, 4, 10, 2, 5, 9, 11, 3, 1
};
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
for (int i = 0; i < data.length; i++) {
bst.add(data[i]);
}
BinaryTrees.println(bst);
System.out.println("是否为完全二叉树" + bst.isCompleteTree());
}
public static void main(String[] args) {
test7();
}
}
结果如下：
┌───7_p(null)────┐
│ │
┌─4_p(7)─┐ ┌─10_p(7)─┐
│ │ │ │
┌─2_p(4)─┐ 5_p(4) 9_p(10) 11_p(10)
│ │
1_p(2) 3_p(2)
是否为完全二叉树true
根据遍历结果重构二叉树
◼ 以下结果可以保证重构出唯一的一棵二叉树
- 前序遍历 + 中序遍历
例如：
前序遍历：4 2 1 3 6 5
中序遍历：1 2 3 4 5 6
- 后序遍历 + 中序遍历
◼ 前序遍历 + 后序遍历
✓ 如果它是一棵真二叉树（Proper Binary Tree），结果是唯一的
✓ 不然结果不唯一
前驱节点（predecessor）
◼ 前驱节点：中序遍历时的前一个节点
如果是二叉搜索树，前驱节点就是前一个比它小的节点
实现思路：
◼ 如果node.left != null
举例：6、13、8
predecessor = node.left.right.right.right...
终止条件：right 为 null
◼ 如果node.left == null && node.parent != null
举例：7、11、9、1
predecessor = node.parent.parent.parent...
终止条件：node 在 parent 的右子树中
◼ 如果node.left == null && node.parent == null
那就没有前驱节点
举例：没有左子树的根节点
代码实现:
/**
* 是否为前驱结点
*/
private Node<E> predecessor(Node<E> node) {
if (node == null) return node;
// 前驱节点在左子树当中（left.right.right.right....）
Node<E> p = node.left;
if (p != null) {
while (p.right != null) {
p = p.right;
}
return p;
}
// 从父结点、祖父节点中寻找前驱节点
while (node.parent != null && node.parent.left == node) {
node = node.parent;
}
// node.parent == null
// node == node.parent.right
return node.parent;
}
后继节点（successor）
后继节点：中序遍历时的后一个节点
如果是二叉搜索树，后继节点就是后一个比它大的节点
◼ 如果node.right != null
举例：1、8、4
successor = node.right.left.left.left...
终止条件：left 为 null
◼ 如果node.right == null && node.parent != null
举例：7、6、3、11
successor = node.parent.parent.parent...
终止条件：node 在 parent 的左子树中
◼ 如果node.right == null && node.parent == null
那就没有前驱节点
举例：没有右子树的根节点
/**
* 是否为后继结点
*/
private Node<E> successor(Node<E> node) {
if (node == null) return node;
// 后继节点在右子树当中（right.left.left.left....）
Node<E> p = node.right;
if (p != null) {
while (p.left != null) {
p = p.left;
}
return p;
}
// 从父结点、祖父节点中寻找前驱节点
while (node.parent != null && node.parent.right == node) {
node = node.parent;
}
// node.parent == null
// node == node.parent.left
return node.parent;
}
