두 갈래 나무의 선순, 중순, 그리고 후속 역행은 비귀속의 형식을 채택한다

1. 순서대로 훑어보기: (자신이 창고를 만든다)

뿌리 노드를 눌러서 창고 꼭대기에서 꺼낸다

만약에 튀어나온 노드의 오른쪽 아이가 비어 있지 않으면 먼저 오른쪽 아이를 창고에 맡기고 왼쪽 아이가 비어 있지 않으면 왼쪽 아이를 창고에 넣는다

	// 
public static void preOrderUnRecur(Node head) {
		System.out.print("pre-order: ");
		if (head != null) {
			Stack<Node> stack = new Stack<Node>();
			stack.push(head);
			while (!stack.isEmpty()) {
				head = stack.pop();
				System.out.print(head.value + " ");
				if (head.right != null) {// 
					stack.push(head.right);
				}
				if (head.left != null) {
					stack.push(head.left);
				}
			}
		} 
		System.out.println();
	}

2. 중서 두루 훑어보다

현재 노드가 비어 있지 않으면 이 노드를 창고에 눌러서 노드를 왼쪽 아이로 이동합니다

현재 노드가 비어 있으면 창고 꼭대기의 원소를 튀겨내고 노드를 오른쪽 아이로 이동합니다

// 
	public static void inOrderUnRecur(Node head) {
		System.out.print("in-order: ");
		if (head != null) {// 
			Stack<Node> stack = new Stack<Node>();
			while (!stack.isEmpty() || head != null) {
				if (head != null) {
					stack.push(head);
					head = head.left;// if ， while  
				} else {
					head = stack.pop();
					System.out.print(head.value + " ");
					head = head.right;
				}
			}
		}
		System.out.println();
	}

3. 뒷차례 반복 (좌우 중)

방법 1: 두 개의 창고 사용

사상: 순서는 중좌우이고 중우좌좌(창고를 눌렀을 때 왼쪽 아이를 눌렀다가 오른쪽 아이를 눌렀다)로 바꿀 수 있다. 중우좌회전을 한 후에 인쇄하지 않고 창고에 순차적으로 저장한 다음에 창고에서 순서대로 튀어나올 수 있다. 결과는 좌중우이다

// -------- 1 （ ）
	public static void posOrderUnRecur1(Node head) {
		System.out.print("pos-order: ");
		if (head != null) {
			Stack<Node> s1 = new Stack<Node>();
			Stack<Node> s2 = new Stack<Node>();
			s1.push(head);
			while (!s1.isEmpty()) {
				head = s1.pop();
				s2.push(head);// ， ， 
				if (head.left != null) {// 
					s1.push(head.left);
				}
				if (head.right != null) {// 
					s1.push(head.right);
				}
			}
			while (!s2.isEmpty()) {// 2
				System.out.print(s2.pop().value + " ");
			}
		}
		System.out.println();
	}

방법 2: 창고 하나를 사용(파악하지 않아도 됨)

// -------- 2 （ ）
	public static void posOrderUnRecur2(Node h) {
		System.out.print("pos-order: ");
		if (h != null) {
			Stack<Node> stack = new Stack<Node>();
			stack.push(h);
			Node c = null;
			while (!stack.isEmpty()) {
				c = stack.peek();
				if (c.left != null && h != c.left && h != c.right) {
					stack.push(c.left);
				} else if (c.right != null && h != c.right) {
					stack.push(c.right);
				} else {
					System.out.print(stack.pop().value + " ");
					h = c;
				}
			}
		}
		System.out.println();
	}

4. 테스트 결과

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

		public Node(int data) {
			this.value = data;
		}
	}
-----------------------------------------
-----------------------------------------
// 
public static void preOrderRecur(Node head) {
		if (head == null) {
			return;
		}
		System.out.print(head.value + " ");
		preOrderRecur(head.left);
		preOrderRecur(head.right);
	}

	public static void inOrderRecur(Node head) {
		if (head == null) {
			return;
		}
		inOrderRecur(head.left);
		System.out.print(head.value + " ");
		inOrderRecur(head.right);
	}

	public static void posOrderRecur(Node head) {
		if (head == null) {
			return;
		}
		posOrderRecur(head.left);
		posOrderRecur(head.right);
		System.out.print(head.value + " ");
	}
	-------------------------------------------------
	
	public static void main(String[] args) {
		Node head = new Node(5);
		head.left = new Node(3);
		head.right = new Node(8);
		head.left.left = new Node(2);
		head.left.right = new Node(4);
		head.left.left.left = new Node(1);
		head.right.left = new Node(7);
		head.right.left.left = new Node(6);
		head.right.right = new Node(10);
		head.right.right.left = new Node(9);
		head.right.right.right = new Node(11);

		// recursive
		System.out.println("==============recursive==============");
		System.out.print("pre-order: ");
		preOrderRecur(head);
		System.out.println();
		System.out.print("in-order: ");
		inOrderRecur(head);
		System.out.println();
		System.out.print("pos-order: ");
		posOrderRecur(head);
		System.out.println();

		// unrecursive
		System.out.println("============unrecursive=============");
		preOrderUnRecur(head);
		inOrderUnRecur(head);
		posOrderUnRecur1(head);
		posOrderUnRecur2(head);

	}

출력 결과 비교

==============recursive==============
pre-order: 5 3 2 1 4 8 7 6 10 9 11 
in-order: 1 2 3 4 5 6 7 8 9 10 11 
pos-order: 1 2 4 3 6 7 9 11 10 8 5 
============unrecursive=============
pre-order: 5 3 2 1 4 8 7 6 10 9 11 
in-order: 1 2 3 4 5 6 7 8 9 10 11 
pos-order: 1 2 4 3 6 7 9 11 10 8 5 
pos-order: 1 2 4 3 6 7 9 11 10 8 5