算法-二叉树

算法-二叉树

1. 二叉树的遍历

说明:假设给定二叉树的树形结构以及对应节点的数据结构如下:

二叉树的遍历

1
2
3
4
5
6
7
8
class Node {
int val;
Node left;
Node right;
Node(int val) {
this.val = val;
}
}

1.1 前序遍历

前序遍历(父 - 左 - 右)指:对每一个节点,都优先遍历父节点;然后是左子节点;最后是右子节点。对应图例的二叉树,则遍历顺序为:

  • 从根结点 A 出发,遍历 A
  • A 具有左子节点 B,遍历 B
  • B 具有左子节点 D,遍历 D
  • D 不具有左子节点,但具有右子节点 H,遍历 H
  • H 不具有左子节点,但具有右子节点 K,遍历 K
  • K 不具有左子节点,也不具有右子节点,返回 H
  • H 遍历完毕,返回 D
  • D 遍历完毕,返回 B
  • B 具有右子节点 E,遍历 E
  • E 不具有左子节点,也不具有右子节点,返回 B
  • B 遍历完毕,返回 A
  • A 具有右子节点 C,遍历 C
  • ......
1
A -> B -> D -> H -> K -> E -> C -> F -> I -> L -> G -> J
1
2
3
4
5
6
7
8
9
10
11
12
13
class BinaryTreeErgodic {
public void preOrder(Node parent) {
if (parent == null) {
return;
}
// 优先遍历父节点,用 println 表示遍历到。
System.out.println("Val: " + parent.val);
// 然后遍历左子节点。
preOrder(parent.left);
// 最后遍历右子节点。
preOrder(parent.right);
}
}

1.2 中序遍历

中序遍历(左 - 父 - 右)指:对每一个节点,都优先深度遍历左子节点,直到某个节点没有左子节点;然后遍历父节点;最后遍历右子节点。对应图例的二叉树,则遍历顺序为:

  • 从根结点 A 出发,A 具有左子节点 B
  • B 具有左子节点 D
  • D 不具有左子节点,遍历 D 自己
  • D 具有右子节点 H
  • H 不具有左子节点,遍历 H 自己
  • H 具有右子节点 K
  • K 不具有左子节点,遍历 K 自己
  • K 不具有右子节点,遍历完毕返回 H
  • H 遍历完毕,返回 D
  • D 遍历完毕,返回 B
  • B 左子节点遍历完毕,遍历 B 自己
  • B 具有右子节点 E
  • E 不具有左子节点,遍历 E 自己
  • E 不具有右子节点,遍历完毕返回 B
  • B 遍历完毕,返回 A
  • A 左子节点遍历完毕,遍历 A 自己
  • A 具有右子节点 C
  • ......
1
D -> H -> K -> B -> E -> A -> F -> L -> I -> C -> G -> J
1
2
3
4
5
6
7
8
9
10
11
12
13
class BinaryTreeErgodic {
public void midOrder(node parent) {
if (parent == null) {
return;
}
// 优先深度遍历左子节点。
preOrder(parent.left);
// 直到左子节点遍历完毕,则遍历自己,用 println 表示遍历到。
System.out.println("Val: " + parent.val);
// 最后遍历右子节点。
preOrder(parent.right);
}
}

1.3 后序遍历

后序遍历(左 - 右 - 父)指:对每一个节点,都优先深度遍历左子节点,直到某个节点没有左子节点;然后深度遍历右子节点;最后遍历父节点。对应图例的二叉树,则遍历顺序为:

  • 从根结点 A 出发,A 具有左子节点 B
  • B 具有左子节点 D
  • D 不具有左子节点,但具有右子节点 H
  • H 不具有左子节点,但具有右子节点 K
  • K 不具有左子节点,也不具有右子节点,遍历 K 自己
  • K 遍历完毕,返回 H
  • H 左子节点遍历完毕,右子节点遍历完毕,遍历 H 自己
  • H 遍历完毕,返回 D
  • D 左子节点遍历完毕,右子节点遍历完毕,遍历 D 自己
  • D 遍历完毕,返回 B
  • B 左子节点遍历完毕,具有右子节点 E
  • E 不具有左子节点,也不具有右子节点,遍历 E 自己
  • E 遍历完毕,返回 B
  • B 左子节点遍历完毕,右子节点遍历完毕,遍历 B 自己
  • B 遍历完毕,返回 A
  • A 左子节点遍历完毕,具有右子节点 C
  • C 具有左子节点 F
  • F 不具有左子节点,但具有右子节点 I
  • I 具有左子节点 L
  • L 不具有左子节点,也不具有右子节点,遍历 L 自己
  • ......
1
K -> H -> D -> E -> B -> L -> I -> F -> J -> G -> C -> A
1
2
3
4
5
6
7
8
9
10
11
12
13
class BinaryTreeErgodic {
public void midOrder(node parent) {
if (parent == null) {
return;
}
// 优先深度遍历左子节点。
preOrder(parent.left);
// 然后遍历右子节点。
preOrder(parent.right);
// 直到左右子节点都遍历完毕,最后遍历自己,用 println 表示遍历到。
System.out.println("Val: " + parent.val);
}
}