遍历二叉树:常规算法与Morris算法实现前序、中序、后序遍历
目录
看到一个要求时间复杂度O(N),空间复杂度为O(1)遍历二叉树的算法题目,感觉有点意思。
1 普通二叉树遍历方法
之前在课本上学到的遍历二叉树方法,主要有前序、中序、后序以及层序,无论具体实现使用递归或者非递归的方法,都无法做到额外空间复杂度为o(1)。递归写法实质上使用了函数栈,非递归的写法更不用说,空间复杂度都与树的高度有关o(h),h为树的高度。为了对比后面提到的Morris算法,这里先提供一下常见算法实现代码(Java),不做详细说明。
- 树节点定义
package tree;
public class Node {
public int value;
public Node left;
public Node right;
public Node(int val){
this.value = val;
}
}
这里将各个成员变量都设置为public,直接对外暴露,主要是省去一些set get方法,重点在算法实现上,不要太介意~。
- 前序递归实现
public void preOrderRecur(Node head){
if(head == null){
return;
}
System.out.println(head.value + " ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
- 前序非递归实现
public void preOrderUnRecur(Node head){
if(head != null ){
Stack<Node> stack = new Stack<Node>();
stack.add(head);
while (!stack.isEmpty()){
head = stack.pop();
System.out.println(head.value + " ");
if(head.right != null){
stack.push(head.right);
}
if(head.left != null){
stack.push(head.left);
}
}
}
}
- 中序递归实现
public void inOrderRecur(Node head){
if(head == null){
return;
}
inOrderRecur(head.left);
System.out.println(head.value + " ");
inOrderRecur(head.right);
}
- 中序非递归实现
public void inOrderUnRecur(Node head){
if(head != null){
Stack<Node> stack = new Stack<Node>();
while (!stack.isEmpty() || head != null){
if(head != null){
stack.push(head);
head = head.left;
}else {
head = stack.pop();
System.out.println(head.value + " ");
head = head.right;
}
}
}
}
- 后序递归实现
public void posOrderRecur(Node head){
if(head == null){
return;
}
posOrderRecur(head.left);
posOrderRecur(head.right);
System.out.println(head.value + " ");
}
- 后序非递归实现
public void posOrderUnRecur(Node head){
if(head != null){
Stack<Node> stack = new Stack<Node>();
stack.push(head);
Node c = null;
while (!stack.isEmpty()){
c = stack.peek();
if(c.left != null && head != c.left && head != c.right){
stack.push(c.left);
}else if(c.right != null && head != c.right){
stack.push(c.right);
}else {
System.out.println(stack.pop().value + " ");
head = c;
}
}
}
}
2 Morris算法介绍及实现
由于在遍历的时候,我们需要记住某种遍历次序的的后驱或者前驱结点,常见的递归和非递归都是采用栈的方式完成这个过程,有没有内部空间来记录这些后驱或者前驱结点呢?有,那就是叶结点的左,右孩子结点,因为叶结点的两个孩子结点都是空指针,如果利用好这些空间,我们就可以在O(1)
的空间完成遍历。
利用叶结点的左、右孩子指向遍历的前驱或者后驱结点,这些指针叫做线索,对应的二叉树叫做线索二叉树。
Morris遍历是使用线索二叉树进行中序遍历的一种实现,其可以在O(n)
的时间,O(1)
的空间完成遍历, 对其稍加修改可以推广到先序、后序遍历,其遍历过程包含三个部分:
- 创建指向中序后驱结点的线索;
- 遍历输出结点;
- 删除线索,恢复树的结构;
2.1 Morris 中序遍历
Morris 中序遍历过程如下:
-
当前结点的左孩子是否为空,若是则输出当前结点,更当前结点为当前结点的右孩子;否则进入2;
-
在当前结点的左子树中寻找中序遍历下的前驱结点(左子树中最右结点)
a. 若前驱结点的右孩子为空,则将前驱结点的右孩子指向当前结点,当前结点更新为当前结点的左孩子;进入3;
b. 若前驱结点的右孩子为当前结点(不为空),将前驱结点的右孩子置NULL,输出当前结点,当前结点更新为当前结点的右孩子,进入3;
-
若当前结点不为空,进入1;否则程序结束;
核心代码:
public static void inOrder(Node root) {
Node cur = root, pre = null;
for (; cur != null;) {
if (cur.left != null) {
pre = cur.left;
// find predecessor
while (pre.right != null && pre.right != cur)
pre = pre.right;
if (pre.right == null) {// create thread
pre.right = cur;
cur = cur.left;
} else {
print(cur);
pre.right = null;
cur = cur.right;
}
} else {
print(cur);
cur = cur.right;
}
}
}
下图为每一步迭代的结果(从左至右,从上到下),cur
代表当前节点,深色节点表示该节点已输出。
2.2 Morris 前序遍历
对于前序遍历,只需要在中序遍历的基础上稍加修改便可以完成。
Morris 前序遍历的流程如下:
-
当前结点的左孩子是否为空,若是则输出当前结点,并更新当前结点为当前结点的右孩子;否则进入2;
-
在当前结点的左子树中寻找中序遍历下的前驱结点(左子树中最右结点)
a. 若前驱结点的右孩子为空,则将前驱结点的右孩子指向当前结点,输出当前结点(在这里输出,和中序遍历不同的地方),当前结点更新为当前结点的左孩子;进入3;
b. 若前驱结点的右孩子为当前结点(不为空),将前驱结点的右孩子置NULL,当前结点更新为当前结点的右孩子,进入3;
-
若当前结点不为空,进入1;否则程序结束;
public static void preOrder(Node root) {
Node cur = root, pre = null;
for (;cur != null;) {
if (cur.left != null) {
pre = cur.left;
// find predecessor
while (pre.right != null && pre.right != cur)
pre = pre.right;
if (pre.right == null) {// create thread
print(cur);// print node here
pre.right = cur;
cur = cur.left;
} else {
pre.right = null;//delete thread
cur = cur.right;
}
} else {
print(cur);
cur = cur.right;
}
}
}
下图为每一步迭代的结果(从左至右,从上到下),cur
代表当前节点,深色节点表示该节点已输出。
2.3 Morris 后序遍历
后序遍历的流程如下:
-
新建一个
Dummy
结点,该结点的左孩子指向树根root
,将Dummy
作为当前结点; -
当前结点的左孩子是否为空,更新当前结点为当前结点的右孩子;否则进入2;
-
在当前结点的左子树中寻找中序遍历下的前驱结点(左子树中最右结点):
a. 若前驱结点的右孩子为空,则将前驱结点的右孩子指向当前结点,当前结点更新为当前结点的左孩子,进入3;
b. 若前驱结点的右孩子为当前结点(不为空),反转当前结点到前驱结点之间的路径,输出该路径所有结点;反转当前结点到前驱结点之间的路径,恢复原状。将前驱结点的右孩子置NULL,当前结点更新为当前结点的右孩子,进入3;
-
若当前结点不为空,进入1;否则程序结束;
public static void postOrder(Node root) {
// TODO Auto-generated method stub
Node dummy = new Node (-1);
dummy.left = root;
Node cur = dummy, pre = null;
for (;cur != null;) {
if (cur.left != null) {
pre = cur.left;
// find predecessor
while (pre.right != null && pre.right != cur)
pre = pre.right;
if (pre.right == null) {// create thread
pre.right = cur;
cur = cur.left;
} else {//print here
reverse(cur.left, pre);
print(pre, cur.left);
reverse(pre, cur.left);
pre.right = null;
cur = cur.right;
}
} else {
cur = cur.right;
}
}
}
private static void print(TreeNode from, TreeNode to) {
// TODO Auto-generated method stub
for (;;from = from.right) {
print(from);
if (from == to) break;
}
}
private static void reverse(Node from, Node to) {
// TODO Auto-generated method stub
if (from == to) return;
Node x = from, y = from.right, z= null;
x.right = null;
for (;;) {
z = y.right;
y.right = x;
x = y;
if (y == to) break;
y = z;
}
}
下图为每一步迭代的结果(从左至右,从上到下),cur
代表当前节点,深色节点表示该节点已输出。