기초 - Tree

트리 사용 문제

트리는 Node라는 클래스로 구성하면 쉽다.

• value = Node번호
• x = x좌표에 따라 오른쪽 / 왼쪽이 결정된다.
• y = 제일 높은게 Root

public static class Node{
	int value;
	int x;
	int y;
	
	Node left;
	Node right;
	
	public Node(int value, int x, int y) {
		this.value = value;
		this.x = x;
		this.y = y;
	}
}

1. y좌표 제일 큰 Node가 Root이다.

Arrays.sort(nodeArr, (a1, b1) -> b1.y - a1.y);

2. 정렬 후 [0]번째가 Root Node일 것이고, 그 이후 차례대로 insert를 수행해준다.

public static Node findRoot(Node[] nodeinfo) {
	Node root = nodeinfo[0];
	for(int i = 1; i < nodeinfo.length; i++) {
		insert(root, nodeinfo[i]);
	}
	return root;
}

3. insert는 재귀적으로 수행해준다. x좌표에 따라 right, left가 정해진다.

public static void insert(Node root, Node other) {
	if(other.x < root.x) {
		if(root.left == null) {
			root.left = other;
		} else {
			insert(root.left, other);
		}
	} else {
		if(root.right == null) {
			root.right = other;
		} else {
			insert(root.right, other);
		}
	}
}

4. 전 중 후위순회이며 전위순회는 루트 -> 오른쪽 -> 왼쪽이다.

public static void preOrder(Node root, ArrayList<Integer> list) {
	if(root == null) return;
	list.add(root.value);
	preOrder(root.left, list);
	preOrder(root.right, list);
}