树的三种遍历方式

树的三种遍历方式

以上是一个树结构,我们需要以三种不同的方式遍历它,先创建树的节点对象:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 树节点
*
* @author yu.zh [yuzh233@gmail.com]
* @date 2018/11/08
*/
public class TreeNode {
private String value;
private TreeNode leftNode;
private TreeNode rightNode;

public TreeNode(String value) {
this.value = value;
this.leftNode = null;
this.rightNode = null;
}

// getter and setter
}

再构建一棵树:

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
/**
* 创建一个树结构
*
* @author yu.zh [yuzh233@gmail.com]
* @date 2018/11/08
*/
public class TreeCreator {

private TreeCreator() {
}

public static TreeNode getInstance() {
return TreeCreatorFactory.root;
}

public static class TreeCreatorFactory {
private static TreeNode root;

static{
root = new TreeNode("A");
// 一级节点
root.setLeftNode(new TreeNode("B"));
root.setRightNode(new TreeNode("C"));
// 二级节点
root.getLeftNode().setLeftNode(new TreeNode("D"));
root.getLeftNode().setRightNode(new TreeNode("E"));
root.getRightNode().setRightNode(new TreeNode("F"));
// 三级节点
root.getLeftNode().getRightNode().setLeftNode(new TreeNode("G"));
}
}
}

前序遍历

前序遍历思想是先遍历父节点,再遍历左子节点,最后遍历右子节点。分析上面的树结构:

  • 先打印 A

  • A有左子节点和右子节点,先打印左子节点 B;(前序遍历先求父节点,不管B有没有子节点都会先遍历自己)

  • B有左子节点和右子节点,先打印左子节点 D

  • D没有子节点,看父节点B的右子节点,打印 E

  • 节点E有左子节点,打印 G

  • A的左子节点执行完毕,执行右子节点C,打印 C

  • C没有左子节点,有右子节点,打印 F

中序遍历

中序遍历思想是先遍历左子节点,再遍历父节点,最后遍历右子节点。分析上面的树结构:

  • A有左子节点B,B有子节点D,D没有子节点,打印 D (中序遍历先遍历左子节点再遍历父节点,所以需要往下递归直到没有子节点为止。)

  • D节点的父节点是B,打印 B

  • B的右子节点是E,E有子节点G,根据中序规则,先打印 G

  • 再打印 E

  • B的父节点是A,打印 A

  • A右节点是C,C没有左子节点,于是打印自己 C

  • C的右子节点是F,打印 F

后序遍历

中序遍历思想是先遍历左子节点,再遍历右子节点,最后遍历父节点。分析上面的树结构:

  • A有左子节点B,B有子节点D,D没有子节点,打印 D (后序遍历最后才遍历父节点,有子节点需要一直递归下去直到没有子节点。)

  • D有兄弟节点E,但是E也有子节点,先打印E的子节点 G

  • G打印完了,没有兄弟节点,打印父节点 E

  • D和E都执行完了,打印他们的父节点 B

  • B有兄弟节点C,C有子节点F,打印 F

  • C的子节点都打印完了,打印自己 C

  • A的B和C都打印完了,打印自己 A

后序遍历方式常用作简易的计算器处理,如我的算法笔记:

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×