二叉树前、中、后、层序遍历(递归和循环实现)
给定如下一棵二叉查找树(二叉排序树)
树结构:
public class Tree {
public int data;
//左孩子
public Tree lchild;
//右孩子
public Tree rchild;
}
下面的分别通过递归和循环两种方法实现二叉树的前序、中序、后序、层序遍历。
注意:前、中、后序遍历都是针对根结点而言。
(1)前序遍历
遍历顺序
1. 访问根节点;
2. 前序遍历左子树;
3. 前序遍历右子树。
特点:(根在前,从左往右,一棵树的根永远在左子树前面,左子树又永远在右子树前面 )
递归实现:
/**
* 前序遍历,递归实现
* @param root
* @return
*/
public void preorderTraversal(Tree root) {
if (root == null) {
return;
}
System.out.print(root.data + " ");
preorderTraversal(root.lchild);
preorderTraversal(root.rchild);
}
循环实现:
用栈来保存先前走过的路径,以便可以在访问完子树后,
可以利用栈中的信息,回退到当前节点的双亲节点,进行下一步操作。
public void preorderTraversalIteration(Tree root) {
Stack<Tree> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
System.out.print(root.data + " ");
stack.push(root);
root = root.lchild;
}
if (!stack.isEmpty()) {
root = stack.pop();
root = root.rchild;
}
}
}
图解说明:
输出结果:4 2 1 3 6 5 7
(2)中序遍历
遍历顺序
1. 中序遍历左子树;
2. 访问根节点;
3. 中序遍历右子树。
特点:(根在中,从左往右,一棵树的左子树永远在根前面,根永远在右子树前面)
递归实现:
/**
* 中序遍历,递归实现
* @param root
*/
public void inOrderTraversal(Tree root) {
if (root == null) {
return;
}
inOrderTraversal(root.lchild);
System.out.print(root.data + " ");
inOrderTraversal(root.rchild);
}
循环实现:
public void inOrderTraversalIteration(Tree root) {
Stack<Tree> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.lchild;
}
if (!stack.isEmpty()) {
root = stack.pop();
System.out.print(root.data + " ");
root = root.rchild;
}
}
}
图解说明:
输出结果:1 2 3 4 5 6 7
(3)后序遍历
遍历顺序
1. 后序遍历左子树;
2. 后续遍历右子树;
3. 访问根节点。
特点:(根在后,从左往右,一棵树的左子树永远在右子树前面,右子树永远在根前面)
递归实现:
/**
* 后序遍历,递归实现
* @param root
*/
public void postOrderTraversal(Tree root) {
if (root == null) {
return;
}
postOrderTraversal(root.lchild);
postOrderTraversal(root.rchild);
System.out.print(root.data + " ");
}
循环实现:
后序遍历的非递归算法是三种顺序中最复杂的,
原因在于:
后序遍历是先访问左、右子树,再访问根节点,而在非递归算法中,利用栈回退到时,并不知道是从左子树回退到根节点,还是从右子树回退到根节点,如果从左子树回退到根节点,此时就应该去访问右子树,而如果从右子树回退到根节点,此时就应该访问根节点。
所以相比前序和后序,必须得在压栈时添加信息,以便在退栈时可以知道是从左子树返回,还是从右子树返回进而决定下一步的操作。
public void postOrderTraversalIteration(Tree root) {
//用于表示是从左子树返回到父结点
int left = 1;
//用于表示是从右子树返回到父结点
int right = 2;
//用于存放树结点
Stack<Tree> treeStack = new Stack<>();
//用于存放是从左子结点还是右子结点返回父结点的标记
Stack<Integer> markStack = new Stack<>();
while (root != null || !treeStack.empty()) {
while (root != null) {
//将结点压栈并标记为左节点
treeStack.push(root);
markStack.push(left);
root = root.lchild;
}
while (!treeStack.empty() && markStack.peek() == right) {
//如果是从右子结点返回到父结点,直接输出
markStack.pop();
System.out.print(treeStack.pop().data + " ");
}
if (!treeStack.empty() && markStack.peek() == left) {
//如果是从左子结点返回到父结点,标记为右结点,并对右结点进行操作
markStack.pop();
markStack.push(right);
root = treeStack.peek().rchild;
}
}
}
图解说明:
输出结果:1 3 2 5 7 6 4
(4)层序遍历
遍历顺序
由根结点向下,从左到右一层一层的遍历;
递归实现:
public void sequenceTraversal(Tree root) {
if (root == null) {
return;
}
int deep = deep(root);
for (int i = 1; i <= deep; i++) {
seqTraversal(root, i);
}
}
private void seqTraversal(Tree root, int level) {
if (root == null || level < 1) {
return;
}
if (level == 1) {
System.out.print(root.data + " ");
return;
}
//左子树
seqTraversal(root.lchild, level - 1);
//右子数
seqTraversal(root.rchild, level - 1);
}
/**
* 计算树的深度
* @param root
* @return
*/
public int deep(Tree root) {
if (root == null) {
return 0;
}
int left = deep(root.lchild);
int right = deep(root.rchild);
return (left > right) ? (left + 1) : (right + 1);
}
循环实现:
通过队列辅助实现
- 1.对于不为空的结点,先把该结点加入到队列中
- 2.从队中拿出结点,如果该结点的左右结点不为空,就分别把左右结点加入到队列中
- 3.重复以上操作直到队列为空
/**
* 层序遍历,迭代实现
* @param root
*/
public void sequenceTraversalIteration(Tree root) {
if (root == null) {
return;
}
LinkedList<Tree> treeQueue = new LinkedList<>();
treeQueue.add(root);
Tree currentNode = null;
while (!treeQueue.isEmpty()) {
//移除并返问队列头部的元素
currentNode = treeQueue.poll();
System.out.print(currentNode.data + " ");
if (currentNode.lchild != null) {
treeQueue.add(currentNode.lchild);
}
if (currentNode.rchild != null) {
treeQueue.add(currentNode.rchild);
}
}
}
图解说明:
输出结果:4 2 6 1 3 5 7
总结
- 前序、中序、后序遍历都是基于==DFS(深度优先)==思想,所以在用循环实现的时候借助辅助空间栈来解决。
- 层序遍历基于==BFS(广度优先)==思想,所以在循环实现的时候借助队列来实现。
qq_39683071: 感谢,帮大忙,
汤姆的猫与狗: 没太理解,什么情况下聚合函数会返回NULL呢,结果集为空还是什么?原理是什么?
一只茶壶: 使用聚合函数对结果集进行聚合就会返回NULL
汤姆的猫与狗: 是因为没limit?
汤姆的猫与狗: 所以是为什么呢