二叉树的三种遍历方式

概述

二叉树(Binary tree)是树形结构的一个重要类型。

许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。

二叉树特点是每个节点最多只能有两棵子树,且有左右之分。

二叉树是n个有限元素的集合,该集合或者为空、或者由一个称为根(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
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
package com.leetcode.editor.tree;

import com.leetcode.utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
* 二叉树的前序遍历
*
* @author loquy
* @date 2021 /12/10 16:32
*/
public class BinaryTreePreorderTraversal {

/**
* The entry point of application.
*
* @param args the input arguments
*/
public static void main(String[] args) {
TreeNode left2 = new TreeNode(4);
TreeNode right2 = new TreeNode(5);
TreeNode left = new TreeNode(2, left2, right2);
TreeNode right3 = new TreeNode(6);
TreeNode right = new TreeNode(3, null, right3);
TreeNode treeNode = new TreeNode(1, left, right);
List<Integer> integers = preorderTraversal(treeNode);
for (Integer integer : integers) {
System.out.println(integer);
}
TreeNode.show(treeNode);
}

/**
* Preorder traversal list.
*
* @param root the root
* @return the list
*/
public static List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
preorder(root, res);
return res;
}

/**
* Preorder.
*
* @param root the root
* @param res the res
*/
public static void preorder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
// 前序遍历,根->左->右的顺序
// 把当前节点的值添加到集合
res.add(root.val);
// 递归遍历左子树,直到没有左子树
preorder(root.left, res);
// 递归遍历右子树,直到没有右子树
preorder(root.right, res);
}
}

输出

1
2
3
4
5
6
7
8
9
10
11
1
2
4
5
3
6
1
/ \
2 3
/ \ \
4 5 6

中序遍历

思路

遍历顺序:左子树 -> 根结点 -> 右子树

代码示例

用递归的方式实现遍历。

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
package com.leetcode.editor.tree;

import com.leetcode.utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
* 二叉树的中序遍历
*
* @author loquy
* @date 2021 /12/06 10:25
*/
public class BinaryTreeInorderTraversal {

/**
* The entry point of application.
*
* @param args the input arguments
*/
public static void main(String[] args) {
TreeNode left2 = new TreeNode(4);
TreeNode right2 = new TreeNode(5);
TreeNode left = new TreeNode(2, left2, right2);
TreeNode right3 = new TreeNode(6);
TreeNode right = new TreeNode(3, null, right3);
TreeNode treeNode = new TreeNode(1, left, right);
List<Integer> integers = inorderTraversal(treeNode);
for (Integer integer : integers) {
System.out.println(integer);
}
TreeNode.show(treeNode);
}

/**
* Inorder traversal list.
*
* @param root the root
* @return the list
*/
public static List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
inorder(root, res);
return res;
}

/**
* Inorder.
*
* @param root the root
* @param res the res
*/
public static void inorder(TreeNode root, List<Integer> res) {
if (root == null) {
// 递归结束条件,空则返回
return;
}
// 中序遍历,左->根->右的顺序
// 递归遍历左子树,直到没有左子树
inorder(root.left, res);
// 把当前节点的值添加到集合
res.add(root.val);
// 递归遍历右子树,直到没有右子树
inorder(root.right, res);
}
}

输出

1
2
3
4
5
6
7
8
9
10
11
4
2
5
1
3
6
1
/ \
2 3
/ \ \
4 5 6

后序遍历

思路

遍历顺序:左子树 -> 右子树 -> 根结点

代码示例

用递归的方式实现遍历。

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
package com.leetcode.editor.tree;

import com.leetcode.utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
* 二叉树的后序遍历
* @author loquy
* @date 2021/12/10 16:40
*/
public class BinaryTreePostorderTraversal {

/**
* The entry point of application.
*
* @param args the input arguments
*/
public static void main(String[] args) {
TreeNode left2 = new TreeNode(4);
TreeNode right2 = new TreeNode(5);
TreeNode left = new TreeNode(2, left2, right2);
TreeNode right3 = new TreeNode(6);
TreeNode right = new TreeNode(3, null, right3);
TreeNode treeNode = new TreeNode(1, left, right);
List<Integer> integers = postorderTraversal(treeNode);
for (Integer integer : integers) {
System.out.println(integer);
}
TreeNode.show(treeNode);
}

/**
* postorder traversal list.
*
* @param root the root
* @return the list
*/
public static List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
postorder(root, res);
return res;
}

/**
* postorder.
*
* @param root the root
* @param res the res
*/
public static void postorder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
// 后序遍历,左->右->根的顺序
// 递归遍历左子树,直到没有左子树
postorder(root.left, res);
// 递归遍历右子树,直到没有右子树
postorder(root.right, res);
// 把当前节点的值添加到集合
res.add(root.val);
}
}

输出

1
2
3
4
5
6
7
8
9
10
11
4
5
2
6
3
1
1
/ \
2 3
/ \ \
4 5 6

源码

查看此仓库


二叉树的三种遍历方式
http://www.loquy.cn/3718dbb0.html
作者
loquy
发布于
2022年6月22日
许可协议