Fork me on GitHub

二叉树的遍历总结

概述

这次首先总结二叉树的前序、中序、后序、层次遍历的递归与非递归实现。

下次总结二叉树的查找、求二叉树的深度、统计节点个数与节点比较的递归实现。

二叉树的结构定义为:

1
2
3
4
5
6
7
8
9
10
//Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int x) {
val = x;
}
}

前序遍历

前序遍历的递归实现,中序遍历、后序遍历的递归实现同理:

1
2
3
4
5
6
7
public void preOrder(TreeNode t) {
if (t != null){
System.out.println(t.val);
preOrder(t.left);
preOrder(t.right);
}
}

前序遍历的非递归实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void preOrder(TreeNode t) {
Stack<TreeNode> nodeStack = new Stack<>();//初始化栈
TreeNode root = t;//保存当前节点
//当前节点与栈不同时为空,则进行循环
while (root != null || !nodeStack.isEmpty()) {
//找到最左端节点
while (root != null) {
System.out.println(root.val);//输出当前节点
nodeStack.push(root);//当前节点入栈
root = root.left;//访问左子树
}
//左子树遍历后,出栈访问右子树
if (!nodeStack.isEmpty()) {
root = nodeStack.pop();
root = root.right;
}
}
}

中序遍历

中序遍历的递归实现,同理:

1
2
3
4
5
6
7
public void medOrder(TreeNode t) {
if (t != null){
preOrder(t.left);
System.out.println();
preOrder(t.right);
}
}

中序遍历的非递归实现,与前序遍历不同的就是在找最左端节点时不输出当前节点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void medOrder(TreeNode t) {
Stack<TreeNode> nodeStack = new Stack<>();//初始化栈
TreeNode root = t;//保存当前节点
//同样,当前节点与栈不同时为空,则循环
while (root != null || !nodeStack.isEmpty()) {
//寻找最左节点
while (root != null) {
nodeStack.push(root);//当前节点入栈
root = root.left;
}
if (!nodeStack.isEmpty()) {
root = nodeStack.pop();
System.out.println(root.val);//输出当前节点
root = root.right;//进入右子树
}
}
}

后序遍历

后序遍历的递归实现,同理:

1
2
3
4
5
6
7
public void postOrder(TreeNode t) {
if (t != null){
preOrder(t.left);
preOrder(t.right);
System.out.println();
}
}

后序遍历的非递归实现,需要注意的是得先访问父节点的两个子节点之后才能访问父节点,需要使用一个last节点来记录上一次访问的节点,判断是否是当前节点的右子节点,若是,则说明当前左右子树均已访问,则输出当前节点,否则访问其右子树:

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
public static void postOrder(TreeNode root) {
Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
TreeNode node = root;//记录当前节点
TreeNode lastVisit = root;//记录当前节点的右子树
while (node != null || !treeNodeStack.isEmpty()) {
//找到最左边的节点
while (node != null) {
treeNodeStack.push(node);
node = node.left;
}
//查看当前栈顶元素
node = treeNodeStack.peek();
//如果其右子树也为空,或者右子树已经访问
//则可以直接输出当前节点的值
if (node.right == null || node.right == lastVisit) {
System.out.print(node.val + " ");
treeNodeStack.pop();
lastVisit = node;
node = null;
} else {
//否则,继续遍历右子树
node = node.right;
}
}
}
BJTU-HXS wechat
海内存知己,天涯若比邻。