二叉树认识与四种遍历方式递归和迭代实现

1. 树

我们都知道,树是一种一对多的数据结构,它是由n个有限节点组成的一个具有层次关系的集合,它有如下的特点:

  • 根节点是唯一的(老大当然是一个~);
  • 每个节点都有零个或者必须多个子节点(丁克、独生子、双胞胎、三胞胎…);
  • 每一个非根节点有且只有一个父节点(只有一个老爹,没有老王)

如下图,A即是根节点:

510px-Treedatastructure.png

2. 二叉树

从名字和图中可以看出,二叉树应该是一种特殊形式的树:

576px-Binary_tree.svg.png

没错!它和树相比,有一下的自己的特点:

  • 每个节点最多有两颗树(可以丁克,可以独生子,可以双胞胎,但是不允许三胞胎、四胞胎…);

  • 左子树和右子树是有顺序的,次序不能任意颠倒(老大老二分明);

  • 即使树中的某节点只有一棵子树,也要区别它是左子树还是右子树(独生子也要称老大!);

2.1 特殊二叉树

另外,二叉树还有特殊的形式:

满二叉树:所有分支节点都存在左子树和右子树,并且所有的叶子都在同一层上。

full-tree.png

完全二叉树:在一棵二叉树中,除最后一层外,若其余层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点。

complete-tree.png

2.2 遍历方式

先序遍历

TIM截图20181112191209.png

先序遍历的流程是:首先访问根节点,然后遍历左子树,最后遍历右子树。遍历的顺序是:A-B-D-G-H-C-E-I-F

中序遍历

middle.png

中序遍历的流程是:从根节点开始,首先遍历左子树(将会一直寻找结点的左子树,直到为空),然后访问根节点,最后遍历右子树;遍历的顺序为:G-D-H-B-A-E-I-C-F

后序遍历

post.png

后序遍历的流程是:首先遍历左子树,然后遍历右子树,最后访问根节点。遍历的顺序为:G-H-D-B-I-E-F-C-A

层序遍历

TIM截图20190203103355.png

层序遍历比较简单:按照从左到右的顺序,逐层遍历各个节点。遍历的顺序为:A-B-C-D-E-F-G

3. 编程实现

首先我们来定义二叉树结点类TreeNode的数据结构:

1
2
3
4
5
6
7
8
9
10
public class TreeNode {

public int data; // 数据域,存放当前节点的值
public TreeNode left; // 左子树的引用
public TreeNode right; // 左子树的引用

public TreeNode(int data) {
this.data = data;
}
}

接着我们使用代码的方式来实现二叉树的四种遍历方式,在每个遍历方式中我们都会同时采用递归和迭代的方式来实现。

3.1 先序遍历

递归实现

递归实现先序遍历非常简单,通过递归调用来实现遍历左右子树即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
return traversal(root, res);
}

public List<Integer> traversal(TreeNode node, List<Integer> res) {
if (node == null) return res;

res.add(node.val); // 访问当前结点的值
traversal(node.left, res); // 递归调用,遍历左子树
traversal(node.right, res); // 递归调用,遍历右子树
return res;
}

迭代实现

迭代方式通过来实现,每次访问完根结点之后,都将该结点的左右结点推入栈中。

需要注意的是,每次在将子结点推入栈中时,首先要进行判空,其次因为栈先进后出的特性:要先将右结点推入栈中,因为先序遍历先访问左子结点的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) return res;

stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
res.add(node.val);

if (node.right == null) stack.push(node.right);
if (node.left == null) stack.push(node.left);
}
return res;
}

先序遍历的这种方式称之为深度优先遍历BFS):即从根节点出发,沿着左子树方向进行纵向遍历,直到找到叶子节点为止(深度!深度!即先找到最深的左子树)。然后回溯到前一个节点,进行右子树节点的遍历,直到遍历完所有可达节点为止。

3.2 中序遍历

递归实现

递归实现中序遍历代码和前序遍历的类似,区别在于首先通过递归遍历左子树,直到左子树为空则访问该结点,然后再递归遍历右子树:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
return traversal(root, res);
}

public List<Integer> traversal(TreeNode root, List<Integer> res) {
if (root == null) return res;

traversal(node.left, res); // 递归调用,遍历左子树
res.add(node.val); // 访问当前结点的值
traversal(node.right, res); // 递归调用,遍历右子树
return res;
}

迭代实现

迭代方式中序遍历同样通过来实现,每次出栈一个结点都一直遍历其左子树并入栈,直到左子树空。然后访问栈顶结点并出栈。接着继续遍历右子树:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();

TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
/* 遍历cur的左子结点,并将这些结点都压入栈中 */
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
// 出栈,访问这些子结点的右结点值
cur = stack.pop();
res.add(cur.val);
cur = cur.right;
}
return res;
}

3.3 后序遍历

递归实现

同样,递归方法实现的后序遍历和其他遍历也非常类似,序列在于后序遍历会递归调用访问左子树和右子树,然后再访问该结点:

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
return traversal(root, res);
}

private List<Integer> traversal(TreeNode root, List<Integer> res) {
if (root == null) return res;
traversal(root.left, res);
traversal(root.right, res);
res.add(root.val);
return res;
}

迭代实现

迭代方式后续遍历需要通过双栈来实现,在每次出栈一个结点之后,都将该结点添加到ansStack中,然后继续将该结点的左右子树入栈。最后得到的ansStack正好和后续遍历的顺序相反:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>(); // 临时栈,用于遍历
Stack<TreeNode> ansStack = new Stack<>(); // 存放答案结点

if (root == null) return res;
stack.push(root);
while (!stack.isEmpty()) {
root = stack.pop();
ansStack.push(root);
if (root.left != null) stack.push(root.left);
if (root.right != null) stack.push(root.right);
}
/* 将栈中结点出栈,并访问结点数据添加到列表中 */
while (!ansStack.isEmpty()) {
res.add(ansStack.pop().val);
}
return res;
}

3.4 层序遍历

通过队列很容易可以实现层序遍历,每次迭代都将队列中的结点出队,并将它们的子结点都入队,这样就能始终保持队列中的结点都是某一层的所有结点了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new ArrayDeque<>();
if (root == null) return res;

queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> list = new ArrayList<>();
while (size-- > 0) { // 遍历每层的结点
TreeNode node = queue.remove();
list.add(node.val);

if (node.left != null) queue.offer(node.left); // 将左子树入队
if (node.right != null)queue.offer(node.right); // 将右子树入队
}
res.add(list);
}
return res;
}

这种遍历方式被称作广度优先搜索BFS),它是从根节点出发,在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。维基百科上有一张动图能很好地展示出广度优先遍历的过程:

白色代表尚未加入队列且未遍历,灰色代表加入队列等待遍历,黑色则代表已经被遍历。

Pushy wechat
欢迎订阅我的微信公众号