分别用递归和非递归方式实现二叉树先序、中序和后序遍历
使用java描述，读者需已经有数据结构知识
本文为代码添加了详细注释而不是抽线文字讲解
二叉树定义：
private class Node<T> {
public T value;
public Node<T> 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<Node<?>> 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<Node<?>> 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<Node<?>> 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;
}
}
}
网友评论