# 数据结构--Morris遍历--二叉树的遍历

2018/05/03 22:55

Morris遍历

Morris遍历规则：

1.来到的当前结点即为cur，如果cur没有左孩子，则cur向右移动，即cur = cur.right

2.如果cur有左孩子，则找到cur左子树上最右的结点，记为mostRight

①如果mostRight的右指针指向null（第一次遍历到cur时），则将其指向当前结点cur，cur向左移动  cur = cur.left

②如果mostRight的右指针指向cur（第二次回到cur时），则让其指向null，cur向右移动  cur = cur.right

package binaryTree.traverse;

/**
* Created by Skye on 2018/5/3.
*
* 当前结点cur
* 1.如果cur没有左孩子，则cur = cur.right
* 2.如果cur有左孩子，则找到cur左孩子的最右结点mostRight
*   1）如果mostRight.right == null 则让mostRight.right = cur，cur = cur.left
*   2）如果mostRight.right == cur，则让mostRight.right = null，cur= cur.right
*/
public class MorrisTraversal {

public static void morris(Tree node){
if(node == null) return;
Tree cur = node;
while(cur != null){
Tree mostRight = cur.left;
if(mostRight != null){
while(mostRight.right != null && mostRight != cur){
mostRight = mostRight.right;
}
if(mostRight.right == null){
mostRight.right = cur;
cur = cur.left;
continue;
}else{
mostRight.right = null;
}
}
cur = cur.right;
}
}

public static void morrisIn(Tree node){
if(node == null) return;
Tree cur = node;
while(cur != null){
Tree mostRight = cur.left;
if(mostRight != null){
while(mostRight.right != null && mostRight.right != cur){
mostRight = mostRight.right;
}
if(mostRight.right == null){
mostRight.right = cur;
cur = cur.left;
continue;
}else{
mostRight.right = null;
}
}
System.out.print(cur.val + " ");
cur = cur.right;
}
}

public static void morrisPre(Tree tree){
if(tree == null) return;
Tree cur = tree;
while(cur != null){
Tree mostRight = cur.left;
if(mostRight != null){
while(mostRight.right != null && mostRight.right != cur){
mostRight = mostRight.right;
}
if(mostRight.right == null){
mostRight.right = cur;
System.out.print(cur.val + " ");
cur = cur.left;
continue;
}else{
mostRight.right = null;
}
} else{
System.out.print(cur.val + " ");
}

cur = cur.right;
}
}

public static void morrisPost(Tree node){
if(node == null) return;
Tree cur = node;
while(cur != null){
Tree mostRight = cur.left;
if(mostRight != null){
while(mostRight.right != null && mostRight.right != cur){
mostRight = mostRight.right;
}
if(mostRight.right == null){
mostRight.right = cur;
cur = cur.left;
continue;
}else{
mostRight.right = null;
printEdge(cur.left);
}
}
cur = cur.right;
}
printEdge(node);
}

public static void printEdge(Tree cur) {
if(cur == null) return;

int val = cur.val;
printEdge(cur.right);
System.out.print(val + " ");
}

}

1.采用链表逆向输出

public static void printEdge(Tree cur) {
if(cur == null) return;

int val = cur.val;
printEdge(cur.right);
System.out.print(val + " ");
}

2.先将链表反转，然后输出，最后在反转回来。

public static void printEdge1(Tree cur){
Tree tail = reverse(cur);
Tree node = tail;
while(node != null){
System.out.print(node.val + " ");
node = node.right;
}

reverse(tail);
}

public static Tree reverse(Tree node){
Tree pre = null;

while(node != null){
Tree next = node.right;
node.right = pre;
pre = node;
node = next;
}
return pre;
}

0
0 收藏

2021/12/29 17:19

1 评论
0 收藏
0