morris 두루 다니다

일반적으로 두 갈래 트리를 실현하는 전차순(preorder), 중차순(inorder), 후차순(postorder)은 두 가지 자주 사용하는 방법이 있다. 하나는 귀속(recursive)이고, 다른 하나는 창고를 사용하여 실현하는 교체 버전(stack+iterative)이다.이 두 가지 방법은 모두 O(n)의 공간 복잡도 (귀속 자체가 stack 공간을 차지하거나 사용자가 정의한 stack) 이다.
본고는 공간 O(1)의 역행 방법을 소개한다.
지난번에 말한 바와 같이 우리의 고전은 사실 세 번의 현재 노드를 방문할 기회가 있다. 네가 다시 언제 조작을 하느냐에 따라 세 가지로 나뉜다.
https://blog.csdn.net/hebtu666/article/details/82853988
morris는 노드를 두 번 방문할 기회가 있습니다.
그것이 공간을 절약하는 원리는 대량의 잎 노드의 쓸모없는 공간을 이용하여 이전의 노드를 기록하고 이전의 노드로 돌아가는 일을 하는 것이다.
우리는 선순에서 후순을 말하지 않고 모리스가 두루 훑어보는 원칙을 말한다.
1. 왼쪽 아이가 없으면 오른쪽 나무를 계속 훑어본다
2. 왼쪽 아이가 있으면 왼쪽 나무의 가장 오른쪽 노드를 찾아라.
1) 맨 오른쪽 노드의 오른쪽 포인터가 비어 있으면 (처음 만났다는 뜻) 현재 노드를 가리키고 현재 노드는 왼쪽으로 계속 처리합니다.
2) 맨 오른쪽 노드의 오른쪽 포인터가 비어 있지 않으면 (이전 결점을 가리키는 것을 의미함) 오른쪽 포인터를 비어 있고 현재 노드는 오른쪽으로 계속 처리됩니다.
 
이것이 바로 모리스가 두루 돌아다니는 것이다.
최소한 3의 트리를 수동으로 시뮬레이션하여 프로세스를 익히십시오.
 
코드 보기:
결점을 정의하려면 다음과 같이 하십시오.

	public static class Node {
		public int value;
		Node left;
		Node right;

		public Node(int data) {
			this.value = data;
		}
	}

순서:
(완전히 규칙에 따라 쓰면 된다.)

// （ ）： ， 。
	public static void morrisPre(Node head) {
		if (head == null) {
			return;
		}
		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;
				}
				if (cur2.right == null) {
					cur2.right = cur1;
					System.out.print(cur1.value + " ");
					cur1 = cur1.left;
					continue;
				} else {
					cur2.right = null;
				}
			} else {
				System.out.print(cur1.value + " ");
			}
			cur1 = cur1.right;
		}
		System.out.println();
	}

morris는 글을 발표할 때 중서만 썼다.선순환은 인쇄 시기가 다를 뿐이기 때문에 후세 사람들은 선순환을 개선했다.뒷순서는 모든 오른쪽 경계를 인쇄함으로써 이루어진다. 모든 경계에 대해 역순으로 인쇄하고 다시 역순으로 돌아간다.제자리에서 역순해야 한다. 그렇지 않으면 우리morris가 두루 훑어보는 의미도 없어진다.
전체 코드:

public class MorrisTraversal {

	
	
	public static void process(Node head) {
		if(head == null) {
			return;
		}
		
		// 1
		//System.out.println(head.value);
		
		
		process(head.left);
		
		// 2
		//System.out.println(head.value);
		
		
		process(head.right);
		
		// 3
		//System.out.println(head.value);
	}
	
	
	public static class Node {
		public int value;
		Node left;
		Node right;

		public Node(int data) {
			this.value = data;
		}
	}
// ： 
	public static void morrisIn(Node head) {
		if (head == null) {
			return;
		}
		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 {
					cur2.right = null;
				}// ， 
			}
			System.out.print(cur1.value + " ");
			cur1 = cur1.right;
		}
		System.out.println();
	}
// （ ）： ， 。
	public static void morrisPre(Node head) {
		if (head == null) {
			return;
		}
		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;
				}
				if (cur2.right == null) {
					cur2.right = cur1;
					System.out.print(cur1.value + " ");
					cur1 = cur1.left;
					continue;
				} else {
					cur2.right = null;
				}
			} else {
				System.out.print(cur1.value + " ");
			}
			cur1 = cur1.right;
		}
		System.out.println();
	}
// 
	public static void morrisPos(Node head) {
		if (head == null) {
			return;
		}
		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;
				}
				if (cur2.right == null) {
					cur2.right = cur1;
					cur1 = cur1.left;
					continue;
				} else {
					cur2.right = null;
					printEdge(cur1.left);
				}
			}
			cur1 = cur1.right;
		}
		printEdge(head);
		System.out.println();
	}
// 
	public static void printEdge(Node head) {
		Node tail = reverseEdge(head);
		Node cur = tail;
		while (cur != null) {
			System.out.print(cur.value + " ");
			cur = cur.right;
		}
		reverseEdge(tail);
	}
// （ ）
	public static Node reverseEdge(Node from) {
		Node pre = null;
		Node next = null;
		while (from != null) {
			next = from.right;
			from.right = pre;
			pre = from;
			from = next;
		}
		return pre;
	}
	public static void main(String[] args) {
		Node head = new Node(4);
		head.left = new Node(2);
		head.right = new Node(6);
		head.left.left = new Node(1);
		head.left.right = new Node(3);
		head.right.left = new Node(5);
		head.right.right = new Node(7);

		morrisIn(head);
		morrisPre(head);
		morrisPos(head);
	}

}