树的遍历

Tree Traversal

2022-05-21 约 1833 字预计阅读 4 分钟

在计算机科学里，树的遍历（也称为树的搜索）是图的遍历的一种，指的是按照某种规则，不重复地访问某种树的所有节点的过程。具体的访问操作可能是检查节点的值、更新节点的值等。不同的遍历方式，其访问节点的顺序是不一样的。以下虽然描述的是二叉树的遍历算法，但它们也适用于其他树形结构。

遍历的种类

与那些基本上都有标准遍历方式（通常是按线性顺序）的线性数据结构（如链表、一维数组）所不同的是，树结构有多种不同的遍历方式。从二叉树的根节点出发，节点的遍历分为三个主要步骤：对当前节点进行操作（称为“访问”节点）、遍历左边子节点、遍历右边子节点。这三个步骤的先后顺序也是不同遍历方式的根本区别。

由于从给定的某个节点出发，有多个可以前往的下一个节点（树不是线性数据结构），所以在顺序计算（即非并行计算）的情况下，只能推迟对某些节点的访问——即以某种方式保存起来以便稍后再访问。常见的做法是采用栈（LIFO）或队列（FIFO）。由于树本身是一种自我引用（即递归定义）的数据结构，因此很自然也可以用递归方式，或者更准确地说，用corecursion，来实现延迟节点的保存。这时（采用递归的情况）这些节点被保存在call stack中。

遍历方式的命名，源于其访问节点的顺序。最简单的划分：

是深度优先（先访问子节点，再访问父节点，最后是第二个子节点）？
还是广度优先（先访问第一个子节点，再访问第二个子节点，最后访问父节点）？

深度优先可进一步按照根节点相对于左右子节点的访问先后来划分。

如果把左节点和右节点的位置固定不动，那么根节点放在左节点的左边，称为前序（pre-order）
根节点放在左节点和右节点的中间，称为中序（in-order）
根节点放在右节点的右边，称为后序（post-order）。

对广度优先而言，遍历没有前序中序后序之分：给定一组已排序的子节点，其“广度优先”的遍历只有一种唯一的结果。

深度优先遍历 DFS

深度优先搜索算法产生目标图相应拓扑排序表。

深度优先搜索使用栈实现，整个过程可以想象成一个倒立的树形。

前序遍历(Pre-Order Traversal)

中左右 - 指先访问根，然后访问子树的遍历方式

深度优先遍历 - 前序遍历： F, B, A, D, C, E, G, I, H.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


@Data
public class TreeNode {
  private int val;
  /** 左子树 */
  private TreeNode left;
  /** 右子树 */
  private TreeNode right;

  public TreeNode(int x) {
    val = x;
  }
}

List<TreeNode> nodeList = new ArrayList<>();
public List<TreeNode> preOrderTraversal(TreeNode root) {
    if (root == null) {
      return null;
    }
    nodeList.add(root);
    preOrderTraversal(root.left);
    preOrderTraversal(root.right);
}

非递归

 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


//对比代码， 前序遍历，唯一区别就是， 一个一直向左， 一个一直向右
public List<Integer> preorderTraversal(TreeNode root) {
  List<Integer> res = new ArrayList<>();
  Deque<TreeNode> stack = new ArrayDeque<>();

  while(root != null || !stack.isEmpty()){
    //go left down to the ground
    while(root != null){
      res.add(root.val);
      stack.push(root);
      root = root.left;
    }

    //if we reach to the leaf, go back to the parent right, and repeat the go left down.
    TreeNode cur = stack.pop();
    root = cur.right;
  }

  return res;
}

public List<TreeNode> dfs(TreeNode root) {
    List<TreeNode> nodeList = new ArrayList<>();
    if (root == null) {
      return null;
    }

    Deque<TreeNode> stack = new ArrayDeque();
    stack.add(root);

    while (!stack.isEmpty()) {
      TreeNode node = stack.pop();
      nodeList.add(node);
      // 堆栈保存，注意是先右后左
      if (node.getRight() != null) {
        stack.push(node.getRight());
      }
      if (node.getLeft() != null) {
        stack.push(node.getLeft());
      }
    }
    return nodeList;
  }

中序遍历(In-Order Traversal)

左中右 - 指先访问左（右）子树，然后访问根，最后访问右（左）子树的遍历方式

深度优先遍历 - 中序遍历： A, B, C, D, E, F, G, H, I.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


List<TreeNode> nodeList = new ArrayList<>();
public List<TreeNode> inOrder(TreeNode root) {
    if (root == null) {
      return null;
    }
    
    inOrder(root.left);
    nodeList.add(root);
    inOrder(root.right);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15



public List < Integer > inorderTraversal(TreeNode root) {
    List < Integer > res = new ArrayList < > ();
    Stack < TreeNode > stack = new Stack < > ();
    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        res.add(root.val);
        root = root.right;
    }
    return res;
}

后序遍历(Post-Order Traversal)

左右中 - 指先访问子树，然后访问根的遍历方式

深度优先搜索 - 后序遍历： A, C, E, D, B, H, I, G, F.

递归法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


List<TreeNode> nodeList = new ArrayList<>();
public List<TreeNode> postOrder(TreeNode root) {
    if (root == null) {
      return null;
    }
    
    postOrder(root.left);
    postOrder(root.right);
    nodeList.add(root);
}

迭代法

先序遍历代码不同的地方在左右选取不同，而且后续遍历最后需要反转。左右根 -> 根右左

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();

        while(root != null || !stack.isEmpty()){
            while(root != null){
                res.add(root.val);
                stack.push(root);
                root = root.right;
            }

            TreeNode cur = stack.pop();
            root = cur.left;
        }
        
        Collections.reverse(res);
        return res;
    }

广度优先遍历 BFS

和深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点。二叉树的广度优先遍历又称按层次遍历。算法借助队列实现。

广度优先遍历 - 层次遍历： F, B, G, A, D, I, C, E, H.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


public List<TreeNode> bfs(TreeNode root) {
    List<TreeNode> nodeList = new ArrayList<>();
    if (root == null) {
      return nodeList;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
      TreeNode node = queue.poll();
      nodeList.add(node);

      if (node.getLeft() != null) {
        queue.add(node.getLeft());
      }

      if (node.getRight() != null) {
        queue.add(node.getRight());
      }
    }

    return nodeList;
  }

从前序与中序遍历序列构造二叉树

 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


public TreeNode buildTree(String[] preorder, String[] inorder) {
    if (preorder == null || preorder.length == 0) {
      return null;
    }
    TreeNode root = new TreeNode(preorder[0]);
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    int inorderIndex = 0;
    for (int i = 1; i < preorder.length; i++) {
      String preorderVal = preorder[i];
      TreeNode node = stack.peek();
      if (!Objects.equals(node.getVal(), inorder[inorderIndex])) {
        node.setLeft(new TreeNode(preorderVal));
        stack.push(node.getLeft());
      } else {
        while (!stack.isEmpty() && Objects.equals(stack.peek().getVal(), inorder[inorderIndex])) {
          node = stack.pop();
          inorderIndex++;
        }
        node.setRight(new TreeNode(preorderVal));
        stack.push(node.getRight());
      }
    }
    return root;
  }

目录