摘要
二叉树的遍历可以用递归的方式简单实现,但是递归也有其局限性,所以非递归实现是否可行?下面的文章就会告诉答案。递归的局限性是什么?文章中也会给出作者的理解。
二叉树的遍历有 4 种方式,分别是前序遍历、中序遍历、后序遍历和层序遍历,它们的区别如下表:
遍历方法 | 访问顺序 |
---|---|
前序遍历(Preorder Traversal) | 根节点、左子树、右子树 |
中序遍历(Inorder Traversal) | 左子树、根节点、右子树 |
后序遍历(Postorder Traversal) | 左子树、右子树、根节点 |
层序遍历(Level Order Traversal) | 从上到下、从左到右依次访问每一个节点 |
在《数据结构与算法-基础(八)遍历二叉树》中使用递归的方式实现这些遍历(递归方法可以看第八期文章),遍历二叉树使用递归方式实现,在代码上会更加简单明了,同时也不能忽视它的缺点(递归的普遍缺点):
1、 递归是本质是调用自身,那么在时间和空间上需要更多的消耗;
2、 递归思想核心就是把一个问题拆分为多个小问题,多个小问题重叠的部分,就是增加重复计算消耗;
3、 递归实际上是将函数不断地压入栈,那么就会存在栈溢出的情况(递归层级多的情况下);
那么是否有其他的遍历实现方案?本文就是介绍遍历二叉树的另外一个方案,统称为非递归遍历,了解这个方案的好处有:
1、 多增加一个实现方案,在应用场景中实现时,可以多一个选择;
2、 一个方案本质是解决某方面的思考和逻辑,通过这个方案了解和学习它的思维和逻辑,方面在解决问题时多一个思路;
准备
在实现遍历之前,先要确定二叉树的类结构,类中有 root
来作为根节点,size
记录二叉树中的节点(或元素)数量:
public class BinaryTree<E> implements BinaryTreeInfo {
protected int size;
protected Node<E> root;
}
Node
类中有记录父节点、左子节点、右子节点和存放元素变量这 4 个基本属性:
protected static class Node<E> {
Node<E> parent;
Node<E> left;
Node<E> right;
E element;
}
前序遍历
前序遍历的顺序是根节点、左子树、右子树。这里用堆栈(stack)的数据结构来实现,大致的逻辑是:
1、 将root赋值给node,然后循环;
2、 当node不是null时,打印node,然后将右子节点压入stack,左子节点赋值给node,进行下一个循环;
3、 当stack是null时,退出循环完成遍历;
4、 当stack不为null,node是null时,就从stack中推出一个node;
代码逻辑中需要注意这几点:
1、 root是null时,不可以遍历;
2、 在循环之前,创建stack;
3、 当右子节点不是null时,才能压入stack;
public void preorderTanversal() {
if (root == null) return;
Node<E> node = root;
Stack<Node<E>> stack = new Stack<>();
while (true) {
if (node != null) {
// 访问 node 节点
print(node.element)
// 将右子节点入栈
if (node.right != null) {
stack.push(node.right);
}
// 向左走
node = node.left;
} else if (stack.isEmpty()) {
return;
} else {
// node 为 null,stack 不为空
node = stack.pop();
}
}
}
中序遍历
中序遍历访问的顺序是左子树、根节点、右子树。中序遍历的逻辑是:
1、 从根节点开始,一直向左遍历,将遍历到的节点一次压入stack中;
2、 从stack中推出node,访问node的元素,然后将右子节点赋值给node;
3、 当stack为null时,完成循环;
写代码时需要特别注意的细节,当 node 为 null 时,不能执行压入 stack 操作,中序遍历相对于前序遍历需要多过几遍代码,帮助更好的理解。
public void inorderTraversal() {
if (root == null) return;
Node<E> node = root;
Stack<Node<E>> stack = new Stack<>();
while (true) {
if (node != null) {
stack.push(node);
node = node.left;
} else if (stack.isEmpty()) {
return;
} else {
// node 为 null, stack 不为 null
// 访问 node 节点
node = stack.pop();
print(node.element)
// 让右节点进行中序遍历
node = node.right;
}
}
}
后序遍历
后序遍历的访问顺序是左子树、右子树、根节点。大致的代码逻辑是:
1、 定义变量prev记录上次被stack推出的node,将root压入stack,然后开始循环;
2、 查看stack顶部的node,当node不是叶子节点,prev的父节点不是stack的顶部节点时,就分别将node的左右非空子节点压入stack;
3、 如果2中的条件不满足,那么就推出stack的node赋值给prev,并访问node;
4、 结束循环的条件是stack为null;
这里用变量 prev 目的就是保证压入 stack 中的节点能保证左子节点、右子节点、节点的顺序:
public void postorderTraversal() {
if (root == null) return;
// 记录上一次弹出的节点
Node<E> prev = null;
Stack<Node<E>> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node<E> top = stack.peek();
if (top.isLeaf() ||(prev != null && prev.parent == top)) {
prev = stack.pop();
// 访问节点
print(prev.element)
} else {
if (top.right != null) {
stack.push(top.right);
}
if (top.left != null) {
stack.push(top.left);
}
}
}
层序遍历
层序遍历的访问顺序是从根节点开始,从上到下,从左到右依次访问节点,这里用队列的数据结构来处理:
1、 将根节点入队到队列中,以队列不为null为循环条件开始遍历;
2、 队列出队node,访问node,并将node的左右非空子节点入队;
public void leverOrderTraversal() {
if (root == null) return;
Queue<Node<E>> queue = new LinkedList<>();
// 第一节点入队
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
// 访问节点
print(node.element)
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
用队列实现层序遍历的方式是一个非常奇特的点,这样的实现方式值得多看几遍。
总结
- 二叉树的遍历方式都可以用非递归的方式实现;
- 使用栈或者队列的方式,核心目的就是保证它的访问顺序,代码中要特别注意循环的条件;
- 中序遍历和后序遍历是比较难理解,需要多看几遍,层序遍历是非常奇特点切入点,值得多看几遍。
版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: