J.A.R.V.I.S

life is not just live

树的几种遍历方式

主要记录一下对于二叉树,进行遍历的几种方式,包括:

  • 前序遍历
  • 中序遍历
  • 后序遍历
  • 深度优先遍历
  • 广度优先遍历

我们以下面的这个二叉树结构为例,分别描述一下这几种遍历的方式有什么不同,以及给出java实现的代码。

几种遍历的区别

我们知道,一个二叉树有根节点,左节点,左节点。

我们遍历的顺序肯定先是左节点,再右节点。前序、中序、后序的区别就是根节点的位置。

如果根节点在左节点前面,那么就是前序遍历。

如果根节点在两者之间,那么就是中序遍历。对于二叉搜索树而言,中序遍历得到的结果是从小到大的。

如果根节点在右节点后面,那么就是后序遍历了。

对于深度优先,我们对于一棵树,从根节点开始,一直访问左子节点,一直到为空,再向上依次返回访问右子节点。以上面的树结构为例,它访问的顺序为: A,B,D,H,I,E,C,F,J,G。

对于广度优先,我们把树分层,根节点为第一层,根节点的子节点为第二层,第二层的子节点为第三层,依次递推。遍历的时候就对每一层进行依次访问。上面的树结构的遍历结果为:A,B,C,D,E,F,G,H,I,J

代码实现

前序遍历

遍历打印

1
2
3
4
5
6
7
8
public void prologuePrint(TreeNode root) {
if (root == null) {
return;
}
prologuePrint(root.left);
System.out.print(root.val + " ");
prologuePrint(root.right);
}

遍历,将数据添加到集合中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List prologueList(TreeNode root) {
List result = new ArrayList();
prologueListHelp(root, result);
return result;
}

private void prologueListHelp(TreeNode node, List list) {
if (node == null) {
return;
}
prologueListHelp(node.left, list);
list.add(node.val);
prologueListHelp(node.right, list);
}

中序遍历

遍历打印

1
2
3
4
5
6
7
8
public void middlePrint(TreeNode root) {
if (root == null) {
return;
}
middlePrint(root.left);
System.out.print(root.val + "");
middlePrint(root.right);
}

遍历将数据添加到集合中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List middleList(TreeNode root) {
List result = new ArrayList();
middleListHelp(root, result);
return result;
}

private void middleListHelp(TreeNode node, List list) {
if (node == null) {
return;
}
middleListHelp(node.left, list);
list.add(node.val);
middleListHelp(node.right, list);
}

后序遍历

遍历打印

1
2
3
4
5
6
7
8
public void postPrint(TreeNode root) {
if (root == null) {
return;
}
postPrint(root.left);
System.out.print(root.val + " ");
postPrint(root.right);
}

遍历将数据添加到集合中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List postList(TreeNode root) {
List result = new ArrayList();
postListHelp(root, result);
return result;
}

private void postListHelp(TreeNode node, List list) {
if (node == null) {
return;
}
prologueListHelp(node.left, list);
list.add(node.val);
prologueListHelp(node.right, list);
}

深度优先遍历

用栈实现深度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void DFSPrint(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack();
stack.push(root);
while (!stack.empty()) {
TreeNode node = stack.pop();
System.out.print(node.val + " ");
//由于栈,先进后出,所以先放右节点
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}

广度优先遍历

用队列实现广度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void BFSPrint(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.val + " ");
//先进先出,先放左节点,再放右节点。遍历的时候就是每一层从左到右的顺序
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}