【数据结构与算法】系列九 - 遍历二叉树

发表于 | 分类于 ， ， ，
| 字数统计 2.8k 字 | 阅读时长 13 分钟

前序/中序/后序/层序

一、二叉树的遍历

遍历是数据结构中的常见操作，就是把所有元素都访问一遍。

线性数据结构的遍历比较简单：正序遍历、逆序遍历。

根据节点访问顺序的不同，二叉树的常见遍历方式有4种：

  • 前序遍历（Preorder Traversal）
  • 中序遍历（Inorder Traversal）
  • 后序遍历（Postorder Traversal）
  • 层序遍历（Level Order Traversal）

1.1. 前序遍历

访问顺序：根节点 -> 前序遍历左子树 -> 前序遍历右子树。

如上图，前序遍历的结果就是：7、4、2、1、3、5、9、8、11、10、12。

1.1.1. 递归

1
2
3
4
5
6
7
8
9
10
11
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);
}

1.1.2. 栈

实现思路：

  1. 设置node = root
  2. 循环执行以下操作（如果node != null，对node进行访问）:
    • 将node.right入栈
    • 设置node = node.left
    • 如果node == null
      • 如果栈为空，结束遍历
      • 如果栈不为空，弹出栈顶元素并赋值给node，继续进入循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void preorderTraversalWithStack() {
  Stack<Node<E>> stack = new Stack<>();
  Node<E> node = root;
  while (node != null) {
    if (node.right != null) {
      stack.push(node.right);
    }
    System.out.println(node.element);
    node = node.left;
    if (node == null && !stack.isEmpty()) {
      node = stack.pop();
    }
  }
}

1.2. 中序遍历

访问顺序：中序遍历左子树 -> 根节点 -> 中序遍历右子树。

如上图，中序遍历的结果就是：1、2、3、4、5、7、8、9、10、11、12。

如果访问顺序是中序遍历右子树、根节点、中序遍历左子树呢？遍历结果：12、11、10、9、8 、7、5、4、3、2、1。

二叉搜索树的中序遍历结果是升序或者降序的。

1.2.1. 递归

1
2
3
4
5
6
7
8
9
10
11
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);
}

1.2.2. 栈

实现思路：

  1. 设置node = root
  2. 循环执行以下操作:
    • 如果node != null
      • 将node入栈
      • 设置node = node.left
    • 如果node == null
      • 如果栈为空，结束遍历
      • 如果栈不为空，弹出栈顶元素并赋值给node
    • 对node进行访问
    • 设置node = node.right
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void inorderTraversalWithStack() {
  Stack<Node<E>> stack = new Stack<>();
  Node<E> node = root;
  while (!stack.isEmpty() || node != null) {
    if (node != null) {
      stack.push(node);
      node = node.left;
    } else if (!stack.isEmpty()) {
      node = stack.pop();
      System.out.println(node.element);
      node = node.right;
    }
  }
}

1.3. 后序遍历

访问顺序：后序遍历左子树 -> 后序遍历右子树 -> 根节点。

如上图，后序遍历的结果就是：1、3、2、5、4、8、10、12、11、9、7。

1.3.1. 递归

1
2
3
4
5
6
7
8
9
10
11
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);
}

1.3.2. 栈

实现思路：

  1. 将root入栈
  2. 循环执行以下操作，直到栈为空
    • 如果栈顶节点是叶子节点 或者 上一次访问的节点是栈顶节点的子节点
      • 弹出栈顶节点，进行访问
    • 否则
      • 将栈顶节点的right、left按顺序入栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public void postorderTraversalWithStack() {
  Node<E> node = root;
  if (node == null) return;
  // 记录上一次访问的节点
  Node<E> lastVisited = null;
  Stack<Node<E>> stack = new Stack<>();
  while (node != null || !stack.isEmpty()) {
    while (node != null) {
        stack.push(node);
        node = node.left;
    }

    node = stack.pop();
    // 栈顶节点是叶子节点或者上一次访问的节点是栈顶节点的子节点
    if (node.right == null || node.right == lastVisited) {
        System.out.print(node.element);
        lastVisited = node;
        // 这里node没有改变指向，所以需要指向null，否则会死循环
        node = null;
    } else {
        // 既不是子节点且上一次访问的节点又不是栈顶节点的子节点话，代表是符节点，重新进栈
        stack.push(node);
        node = node.right;
    }
  }
}

1.4. 层序遍历

访问顺序：从上到下、从左到右依次访问每一个节点。

如上图，层序遍历的结果就是：7、4、9、2、5、8、11、1、3、10、12。

实现思路：使用队列。

  1. 将根节点入队；
  2. 循环执行以下操作，直到队列为空：
    • 将队头节点A出队，进行访问
    • 将A的左子节点入队
    • 将A的右子节点入队
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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);
    }
  }
}

1.5. 增强遍历（设计接口）

如果允许外界遍历二叉树的元素？应该如何设计接口？

  • 让使用者可以自定义操作访问的元素
  • 指定节点终止遍历

如果是Java，可以增加一个接口（interface）或抽象类（abstract）；如果是iOS，可以使用闭包或者代理。

以Java为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
// 定义抽象类（在Java中interface不能定义变量，abstract才可以定义变量）
public static abstract class Visitor<E> {
  boolean stop;
  /**
   * @return 如果返回true，就代表停止遍历
   */
  public abstract boolean visit(E element);
}

// 前序遍历（递归）
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);
  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)) return;
    
    if (node.left != null) {
      queue.offer(node.left);
    }
    
    if (node.right != null) {
      queue.offer(node.right);
    }
  }
}

// 使用
static void test9() {
  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.preorder(new Visitor<Integer>() {
    public boolean visit(Integer element) {
      System.out.print(element + " ");
      return element == 2 ? true : false;
    }
  });
  System.out.println();
  
  bst.inorder(new Visitor<Integer>() {
    public boolean visit(Integer element) {
      System.out.print(element + " ");
      return element == 4 ? true : false;
    }
  });
  System.out.println();
  
  bst.postorder(new Visitor<Integer>() {
    public boolean visit(Integer element) {
      System.out.print(element + " ");
      return element == 4 ? true : false;
    }
  });
  System.out.println();
  
  bst.levelOrder(new Visitor<Integer>() {
    public boolean visit(Integer element) {
      System.out.print(element + " ");
      return element == 9 ? true : false;
    }
  });
  System.out.println();
}

二、遍历的应用

前序遍历：树状结构展示（注意左右子树的顺序）。

中序遍历：二叉搜索树的中序遍历按升序或者降序处理节点。

后序遍历：适用于一些先子后父的操作。

层序遍历：计算二叉树的高度；判断一棵树是否为完全二叉树。

2.1. 计算二叉树高度

2.1.1. 递归

1
2
3
4
5
6
7
8
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));
}

2.1.2. 迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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;
}

2.2. 判断一棵树是否为完全二叉树

实现思路：

  • 如果树为空，返回false
  • 如果树不为空，开始层序遍历二叉树（用队列）
    • 如果node.left!=null，将node.left入队
    • 如果node.left==null && node.right!=null，返回false（完全二叉树度为1的节点必须左对齐）
    • 如果node.right!=null，将node.right入队
    • 如果node.right==null
      • 那么后面遍历的节点应该都为叶子节点，才是完全二叉树，返回true
      • 否则返回false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 判断是否为完全二叉树
public boolean isComplete() {
  if (root == null) return false;
  
  Queue<Node<E>> queue = new LinkedList<>();
  queue.offer(root);

  boolean leaf = false;
  while (!queue.isEmpty()) {
    Node<E> node = queue.poll();
    if (leaf && !node.isLeaf()) 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
      leaf = true;
    }
  }
  
  return true;
}

// 判断是否为叶子节点
public boolean isLeaf() {
  return left == null && right == null;
}

2.3. 翻转二叉树

递归（使用前/后/中序遍历方式都可以）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public TreeNode invertTree(TreeNode root) {
  //递归函数的终止条件，节点为空时返回
  if(root==null) {
    return null;
  }
  //下面三句是将当前节点的左右子树交换
  TreeNode tmp = root.right;
  root.right = root.left;
  root.left = tmp;
  //递归交换当前节点的 左子树
  invertTree(root.left);
  //递归交换当前节点的 右子树
  invertTree(root.right);
  //函数返回时就表示当前这个节点，以及它的左右子树
  //都已经交换完了
  return root;
}

迭代（使用层序遍历）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public TreeNode invertTree(TreeNode root) {
  if(root==null) {
    return null;
  }
  //将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
  LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
  queue.add(root);
  while(!queue.isEmpty()) {
    //每次都从队列中拿一个节点，并交换这个节点的左右子树
    TreeNode tmp = queue.poll();
    TreeNode left = tmp.left;
    tmp.left = tmp.right;
    tmp.right = left;
    //如果当前节点的左子树不为空，则放入队列等待后续处理
    if(tmp.left!=null) {
      queue.add(tmp.left);
    }
    //如果当前节点的右子树不为空，则放入队列等待后续处理
    if(tmp.right!=null) {
      queue.add(tmp.right);
    }
    
  }
  //返回处理完的根节点
  return root;
}

三、LeetCode