分别用递归和非递归方式实现二叉树先序、中序和后序遍历
分别用递归和非递归方式实现二叉树先序、中序和后序遍历
使用java描述,读者需已经有数据结构知识二叉树定义:
本文为代码添加了详细注释而不是抽线文字讲解
private class Node {
public T value;
public Node left, right;
}
先序遍历 遍历的顺序为“根-左-右”。
递归算法为:
public void preOrderRecurA(Node> root) {
// 递归算法退出条件:当前节点为空
if (root == null) {
return;
}
// “根-左-右”
System.out.println(root.value + " ");
preOrderRecurA(root.left);
preOrderRecurA(root.right);
}
利用栈保存递归算法中间的结果。
public void preOrderRecurB(Node> root) {
// 开始条件为非空
if (root == null) {
return;
}
// 栈 stack 用来保存中间节点
Stack> stack = new Stack<>();
// 算法以根结点开始
stack.push(root);
// 结束条件为栈空
while (!stack.isEmpty()) {
// 由“根-左-右”得知,先访问当前节点,
root = stack.pop();
System.out.println(root.value);
// 由于栈是先进后出,所以右孩子先入队,左孩子后入队
// 这样才能实现“根-左-右”
if (root.right != null) {
stack.push(root.right);
}
if (root.left != null) {
stack.push(root.left);
}
}
}
中序遍历 遍历的顺序为“左-根-右”。
递归算法为:
public void inOrderRecurA(Node> root) {
// 递归算法退出条件:当前节点为空
if (root == null) {
return;
}
// “左-根-右”
inOrderRecurA(root.left);
System.out.println(root.value + " ");
inOrderRecurA(root.right);
}
非递归算法为
public void inOrderRecurB(Node> root) {
// 算法运行条件:树非空
if (root == null) {
return;
}
// 栈 stack 用来保存中间节点
Stack> stack = new Stack<>();
// 中序遍历过程中也可能栈空,退出条件需加一条
// 例如 1
// x 2
// x 为空节点,手动模拟算法便会发现遍历过程中出现了栈空
while (!stack.isEmpty() || root != null) {
// 由“左-根-右”,先暂存当前元素访问左孩子
if (root != null) {
stack.push(root);
root = root.left;
}
// “左”为空,访问“根”
else {
root = stack.pop();
System.out.println(root.value + " ");
root = root.right;
}
}
}
后续遍历 遍历的顺序为“左-右-根”。
【分别用递归和非递归方式实现二叉树先序、中序和后序遍历】递归算法为:
public void postOrderRecurA(Node> root) {
// 递归算法退出条件:当前节点为空
if (root == null) {
return;
}
// “左-右-根”
postOrderRecurA(root.left);
postOrderRecurA(root.right);
System.out.println(root.value + " ");
}
非递归算法:
方法一:逆序法(两个栈)
逆后序遍历序列(后序遍历序列的逆序)只不过是把先序遍历序列过程中左右子树的顺序交换所得的结果。(自行手写某树的遍历序列就会明白)
因此只要修改一下前序遍历的算法,先保存逆后序遍历序列,再逆序输出就行了,此方法空间复杂度、时间复杂度都比较大,故不提供代码,只提供思路
方法二:难度高,手动多模拟几次
public void postOrderRecurB(Node> root) {
// 此算法需反复手动模拟便可理解
// 算法运行条件:树非空
if (root == null) {
return;
}
// 栈 stack 用来保存中间节点
Stack> stack = new Stack<>();
// root 也用来表示最近一次出栈的节点
stack.push(root);
// 一个临时变量,栈顶节点
Node> c = null;
while (!stack.isEmpty()) {
c = stack.peek();
// 分三种情况
// 1.若root等于c的左孩子或右孩子,则说明c的孩子都已经打印完毕(“左-右-根”),
// 否则则说明左孩子尚未遍历
if (c.left != null && root != c.left && root != c.right) {
stack.push(c.left);
}
// 2.当条件1不成立时且root不为c的右孩子时(右孩子存在),则说明“左”已经遍历,该访问“右”
else if (c.right != null && root != c.right) {
stack.push(c.right);
// 3.“左-右”都遍历完毕,访问根节点
} else {
System.out.println(stack.pop().value + " ");
// 注意:记录这次出栈的节点
root = c;
}
}
}
推荐阅读
- 一个人的旅行,三亚
- EffectiveObjective-C2.0|EffectiveObjective-C2.0 笔记 - 第二部分
- 第326天
- 赠己诗
- 考研英语阅读终极解决方案——阅读理解如何巧拿高分
- 如何寻找情感问答App的分析切入点
- D13|D13 张贇 Banner分析
- 托福听力高分备考方案
- 自媒体形势分析
- 姚老师互动问答会|姚老师互动问答会 # 问题001(如何更有智慧的和身边人分享金刚智慧())