6.2 二叉树遍历
三大遍历概念
在实际的编程中,二叉树是一种非常常见的数据结构。常见的二叉树有AVL树、红黑树和哈夫曼树。其中AVL树和红黑树是排序二叉树。排序二叉树的特征就是对于每个节点,左子节点比自己小,右子节点比自己大。对于一般的树,有用栈实现的深度优先遍历和用FIFO队列实现的广度优先遍历。但是因为二叉树一般用作排序树,所以有了从“顺序”的维度进行遍历的三种方法:前序遍历、中序遍历和后序遍历,其中中序遍历是二叉树独有的。
以下是一个排序二叉树的例子。
先看看前序遍历,前序遍历Preorder Traversal,与深度优先搜索DFS效果一致,这里就不多说了。
中序遍历Inorder Traversal对排序二叉树特别重要,为什么呢?中序遍历是先访问左子树,再访问自己,再访问右子树。其效果呢,恰好形成了从小到大的遍历。请看下图:
所以中序遍历的意义在于排序。但是后序遍历Postorder Traversal,后序遍历是先访问左子节点,再访问右子节点,最后访问自己。这么做最大的用途是用来做删除操作,删除肯定是最后处理自己的。
递归实现方法
递归实现的代码比较容易,以下是三种遍历的递归实现
/**
* middle order search
*
* @param visitor
*/
public void preOrder(Predicate<Node<T>> visitor) {
final Deque<BinaryNode<T>> nodes = new ArrayDeque<>();
if (!visitor.test(this)) {
return;
}
if (this.getLeft() != null) {
getLeft().preOrder(visitor);
}
if (this.getRight() != null) {
getRight().preOrder(visitor);
}
}
/**
* middle order search
*
* @param visitor
*/
public void inOrder(Predicate<Node<T>> visitor) {
final Deque<BinaryNode<T>> nodes = new ArrayDeque<>();
if (this.getLeft() != null) {
getLeft().inOrder(visitor);
}
if (!visitor.test(this)) {
return;
}
if (this.getRight() != null) {
getRight().inOrder(visitor);
}
}
/**
* middle order search
*
* @param visitor
*/
public void postOrder(Predicate<Node<T>> visitor) {
final Deque<BinaryNode<T>> nodes = new ArrayDeque<>();
if (this.getLeft() != null) {
getLeft().postOrder(visitor);
}
if (this.getRight() != null) {
getRight().postOrder(visitor);
}
if (!visitor.test(this)) {
return;
}
}
非递归实现方法
对于二叉树的前序遍历,直接使用栈进行DFS就行了。可以参考本专栏前一篇文章,这里不再赘述。但是中序遍历和后序遍历如何不通过递归实现呢?
中序遍历也是用栈,不过是方法不一样。初始化栈时,先把整个左子树放入栈中。然后出栈的时候,把右节点的整个左子树放进去。代码稍微复杂了一点,如下:
/**
* middle order search
*
* @param visitor
*/
public void inOrderWithStack(Predicate<Node<T>> visitor) {
final Deque<BinaryNode<T>> stack = new ArrayDeque<>();
BinaryNode<T> left = (BinaryNode<T>) getRoot();
while (left != null) {
stack.push(left);
left = left.left;
}
while (!stack.isEmpty()) {
BinaryNode<T> node = stack.pop();
if (!visitor.test(node)) {
break;
}
if (node.right != null) {
BinaryNode<T> l = node.right;
while (l != null) {
stack.push(l);
l = l.left;
}
}
}
}
后序遍历,因为是用来删除的,根结点最后访问,对于这种最后访问的场景,我们自然想到了栈。所以我们自然想到的是使用双栈算法,第一个栈用于DFS,然后将遍历出来的元素压入第二个栈。再从第二个栈访问。代码我是复用了DFS的代码,如下:
/**
* middle order search
*
* @param visitor
*/
public void postOrderTwoStacks(Predicate<Node<T>> visitor) {
Deque<Node<T>> stack = new LinkedList<>();
dfs(x->{
stack.push(x);
return true;
}, false);
while (!stack.isEmpty()){
Node<T> node = stack.poll();
if (!visitor.test(node)) {
break;
}
}
}
相关文章
- 由中序序列和后序序列确定一棵二叉树
- 中序遍历和前序遍历确定一棵二叉树(笔算)
- Java实现 LeetCode 617 合并二叉树(遍历树)
- Java实现 LeetCode 606 根据二叉树创建字符串(遍历树)
- Java实现 LeetCode 331 验证二叉树的前序序列化
- Java实现 LeetCode 107 二叉树的层次遍历 II(二)
- LeetCode(105):从前序与中序遍历序列构造二叉树
- 222. 完全二叉树的节点个数
- 94. 二叉树的中序遍历
- Leetcode.1372 二叉树中的最长交错路径
- python 二叉树类及其四种遍历方法
- 二叉树 排序二叉树-可以通过中序遍历得到排序的数据 二叉排序树时间复杂度O(logn),
- 【数据结构笔记12】数据结构之线索二叉树介绍及其线索化(构造线索二叉树、寻找前驱、后继结点)
- 二叉树学习笔记-概述
- 【华为机试真题 Python实现】完全二叉树非叶子部分后序遍历
- 145. 二叉树的后序遍历
- 1339. 分裂二叉树的最大乘积-深度优先遍历
- 二叉树中序非递归遍历与递归遍历
- Geeks 一般二叉树的LCA
- LintCode 二叉树的层次遍历
- wiki 3143 二叉树的前序、中序及后序遍历
- 二叉树各种遍历序列之间的转换总结[转载]
- 【LeetCode】124.二叉树中的最大路径和