题目
遍历二叉树的神级方法 morris
java代码
package com.lizhouwei.chapter3;
/**
* @Description:遍历二叉树的神级方法 morris
* @Author: lizhouwei
* @CreateDate: 2018/4/14 17:15
* @Modify by:
* @ModifyDate:
*/
public class Chapter3_5 {
//morris中序
public void morrisInOrder(Node head) {
Node cur1 = head;
Node cur2 = null;//左子节点
while (cur1 != null) {
cur2 = cur1.left;//当前节点的左子节点
if (cur2 != null) {
//循环遍历到左子节点的最右子节点
while (cur2.right != null && cur2.right != cur1) {
cur2 = cur2.right;
}
//如过最右节点未指向cur1，则使之指向cur1,并略过后续代码;
if (cur2.right == null) {
cur2.right = cur1;
cur1 = cur1.left;
continue;
} else {
//如过最右节点已指向cur1，恢复，则使之指向null,
cur2.right = null;
}
}
//如果cur1.left 为null,则说明没有左子树,则开始打印父节点;
System.out.print(cur1.value + " ");
cur1 = cur1.right;
}
System.out.println();
}
//morris前序
public void morrisPreOrder(Node head) {
Node cur1 = head;
Node cur2 = null;//左子节点
while (cur1 != null) {
cur2 = cur1.left;//当前节点的左子节点
if (cur2 != null) {
//循环遍历到左子节点的最右子节点
while (cur2.right != null && cur2.right != cur1) {
cur2 = cur2.right;
}
//如过最右节点未指向cur1，则使之指向cur1,并略过后续代码;
if (cur2.right == null) {
cur2.right = cur1;
System.out.print(cur1.value + " ");//遇见父节点，先打印父节点
cur1 = cur1.left;
continue;
} else {
//如过最右节点已指向cur1，恢复，则使之指向null,
cur2.right = null;
}
} else {
//如果cur1.left 为null,说明没有左子节点,在切换到右子树之前先打印父节点
System.out.print(cur1.value + " ");
}
cur1 = cur1.right;
}
System.out.println();
}
//morris后序
public void morrisPostOrder(Node head) {
Node cur1 = head;
Node cur2 = null;//左子节点
while (cur1 != null) {
cur2 = cur1.left;//当前节点的左子节点
if (cur2 != null) {
//循环遍历到左子节点的最右子节点
while (cur2.right != null && cur2.right != cur1) {
cur2 = cur2.right;
}
//如过最右节点未指向cur1，则使之指向cur1,并略过后续代码;
if (cur2.right == null) {
cur2.right = cur1;
cur1 = cur1.left;
continue;
} else {
//如过最右节点已指向cur1，恢复，则使之指向null,
cur2.right = null;
printEdge(cur1.left);
}
}
cur1 = cur1.right;
}
printEdge(head);
System.out.println();
}
//打印节点
public void printEdge(Node head) {
Node tail = reverse(head);
Node cur = tail;
while (cur != null) {
System.out.print(cur.value + " ");
cur = cur.right;
}
//恢复链表
reverse(tail);
}
//反转节点的右子节点链
public Node reverse(Node head) {
Node pre = null;
Node next = null;
while (head != null) {
next = head.right;
head.right = pre;
pre = head;
head = next;
}
return pre;
}
//测试
public static void main(String[] args) {
Chapter3_5 chapter = new Chapter3_5();
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
Node head = NodeUtil.generTree(arr, 0, arr.length - 1);
System.out.print("morris中序遍历：");
chapter.morrisInOrder(head);
System.out.print("非递归中序遍历：");
NodeUtil.inOrder(head);
System.out.println();
System.out.print("morris前序遍历：");
chapter.morrisPreOrder(head);
System.out.print("非递归前序遍历：");
NodeUtil.preOrder(head);
System.out.print("morris后序遍历：");
chapter.morrisPostOrder(head);
System.out.print("非递归后序遍历：");
NodeUtil.postOrder(head);
}
}
《程序员代码面试指南》第三章 二叉树问题 遍历二叉树的神级方法 morris的相关教程结束。
