二叉树的遍历
文章目录
遍历二叉树一共有四种方式:前序遍历,中序遍历,后序遍历,层序遍历(广度优先)
准备
先定义一个结点类(后续代码需要使用)
public class Node<V> {
public V value;
public Node<V> left;
public Node<V> right;
public Node(V value) {
this.value = value;
}
}
前序遍历
操作步骤如下:
- 访问根结点
- 递归遍历左子树
- 递归遍历右子树
假设一个二叉树的结构如下图所示:
则遍历结果为:1 2 4 5 3 6
实现方式:
- 递归方式
public class PreOrderRecursivelyVisitor {
public <V> void visit(Node<V> root) {
if (root == null) {
return;
}
System.out.println(node.value + " ");
visit(root.left, output);
visit(root.right, output);
}
}
- 非递归方式
借助栈(先进后出)来实现
代码如下:
public class PreOrderVisitor {
public <V> void visit(Node<V> root) {
if (root == null) {
return;
}
Stack<Node<V>> help = new Stack<>();
// 1. 根结点入栈
help.push(root);
while (!help.isEmpty()) {
// 2. 栈顶结点出栈
Node<V> node = help.pop();
// 3. 访问出栈结点
System.out.println(node.value + " ");
// 4. 依次将该结点的右,左孩子入栈
if (node.right != null) {
help.push(node.right);
}
if (node.left != null) {
help.push(node.left);
}
}
}
}
中序遍历
操作步骤如下:
- 递归遍历左子树
- 访问根结点
- 递归遍历右子树
假设一个二叉树的结构如下图所示:
则遍历结果为:4 2 5 1 3 6
实现方式:
- 递归方式
public class InOrderRecursivelyVisitor {
public <V> void visit(Node<V> root) {
if (root == null) {
return;
}
visit(root.left, output);
System.out.println(node.value + " ");
visit(root.right, output);
}
}
- 非递归方式
public class InOrderVisitor {
public <V> void visit(Node<V> root) {
if (root == null) {
return;
}
Stack<Node<V>> help = new Stack<>();
// 定义一个当前结点遍历并指向根结点
Node<V> current = root;
while (current != null || !help.isEmpty()) {
if (current != null) {
// 若当前结点不为空,则入栈
help.push(current);
// 将当前结点指向该结点的左孩子
current = current.left;
} else {
// 若当前结点为空(即当前已经没有可访问的左子树了),则出栈
current = help.pop();
// 访问出栈结点
System.out.println(current.value + " ");
// 将当前结点指向出栈结点的右孩子
current = current.right;
// (若该结点存在,则重复执行上面的if分支将该结点的左子树依次入栈)
}
}
}
}
后序遍历
操作步骤如下:
- 递归遍历左子树
- 递归遍历右子树
- 访问根结点
假设一个二叉树的结构如下图所示:
则遍历结果为:4 5 2 6 3 1
实现方式:
- 递归方式
public class PostOrderRecursivelyVisitor {
public <V> void visit(Node<V> root) {
if (root == null) {
return;
}
visit(root.left, output);
visit(root.right, output);
System.out.println(node.value + " ");
}
}
- 非递归方式
这种方式稍微复杂一点,因为要先遍历完左右子树,再访问根结点,所以需要知道左右子树的访问状态。
public class PostOrderVisitor {
public <V> void visit(Node<V> root) {
if (root == null) {
return;
}
Stack<Node<V>> help = new Stack<>();
// 根结点入栈
help.push(root);
// top指向栈顶元素
Node<V> top = null;
// visited表示刚刚访问过的结点(初始指向根结点)
Node<V> visited = root;
while (!help.isEmpty()) {
// 获取栈顶元素,但是不进行出栈操作
top = help.peek();
if (top.left != null && top.left != visited && top.right != visited) {
// 若栈顶元素的左孩子结点存在,且左右孩子都未被访问过,则左孩子入栈
help.push(top.left);
} else if (top.right != null && top.right != visited) {
// 若栈顶元素的右孩子结点存在,且右孩子未被访问过,则右孩子入栈
help.push(top.right);
} else {
// 栈顶元素出栈,并访问该结点
System.out.println(help.pop().value + " ");
// 记录已访问过的结点
visited = top;
}
}
}
}
层序遍历
也可称为广度优先遍历
操作步骤如下:
从上往下,从左至右依次访问每层的结点
假设一个二叉树的结构如下图所示:
则遍历结果为:1 2 3 4 5 6
实现方式:
借助队列(先进先出)来实现
代码如下:
public class LevelOrderVisitor {
public <V> void visit(Node<V> root) {
if (root == null) {
return;
}
Queue<Node<V>> queue = new LinkedList<>();
// 根结点进入队尾
queue.offer(root);
while (!queue.isEmpty()) {
// 出队列
Node<V> node = queue.poll();
// 访问该结点
System.out.println(node.value + " ");
// 依次将该结点的左右孩子入队列
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
}
以上就是遍历二叉树的几种方式,完整代码可查看二叉树的遍历。如有错误,请指正,谢谢。
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论