노드 순회(전위 순회, 중위 순회, 후위 순회)

코드

import java.util.ArrayList;
import java.util.List;

class Node {
	int data;
	Node lt, rt;

	public Node(int val) {
		data = val;
		lt = rt = null;
	}
}

public class Main {
	Node root;

	List<Integer> list1 = new ArrayList<Integer>();
	List<Integer> list2 = new ArrayList<Integer>();
	List<Integer> list3 = new ArrayList<Integer>();

	public void DFS(Node root) {
		if (root == null)
			return;
		else {
			list1.add(root.data);// 전위 순회
			DFS(root.lt);
			list2.add(root.data);// 중위 순회
			DFS(root.rt);
			list3.add(root.data);// 후위 순회
		}
	}

	public static void main(String args[]) {
		Main tree = new Main();
		tree.root = new Node(1);
		tree.root.lt = new Node(2);
		tree.root.rt = new Node(3);
		tree.root.lt.lt = new Node(4);
		tree.root.lt.rt = new Node(5);
		tree.root.rt.lt = new Node(6);
		tree.root.rt.rt = new Node(7);
		tree.DFS(tree.root);

		System.out.println(tree.list1);
		System.out.println(tree.list2);
		System.out.println(tree.list3);
	}
}

---

결과

[1, 2, 4, 5, 3, 6, 7]
[4, 2, 5, 1, 6, 3, 7]
[4, 5, 2, 6, 7, 3, 1]

---

무조건 위 순서로 순회하게 된다. 

여기서 핵심은 순회 시 어떤 시점에 로직을 넣느냐에 따라 전위-중위-후위 순회가 결정된다.

 

특히 후위순회는 더욱 중요한 것이 특성상 좌항을 모두 순회하고, 우항을 모두 순회하고 마지막으로 가운데 값으로 돌아온다.  이런 특성을 이용해 머지정렬 같은 것을 구현한다.