Java实现前序遍历输出二叉树

Java实现前序遍历输出二叉树的方法如下:

首先, 定义二叉树的结点类型:

class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7

然后, 可以使用递归的方式来遍历二叉树:

void preorderTraversal(TreeNode root) {
  if (root == null) {
    return;
  }
  System.out.println(root.val);  // 访问当前结点
  preorderTraversal(root.left);  // 遍历左子树
  preorderTraversal(root.right); // 遍历右子树
}
1
2
3
4
5
6
7
8
9

或者使用非递归的方式, 可以使用栈来存储遍历的结点:

void preorderTraversal(TreeNode root) {
  if (root == null) {
    return;
  }
  Stack<TreeNode> stack = new Stack<>();
  TreeNode p = root;
  while (p != null || !stack.isEmpty()) {
    while (p != null) {
      System.out.println(p.val);  // 访问当前结点
      stack.push(p);
      p = p.left;
    }
    if (!stack.isEmpty()) {
      p = stack.pop();
      p = p.right;
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这两种方法都可以用来实现前序遍历二叉树, 其中第二种方法不使用递归, 可以避免递归带来的调用开销, 在处理大型二叉树时更加高效。