Tree

https://swexpertacademy.com/main/code/referenceCode/referenceCodeDetail.do?referenceId=TREE&category=undefined 

SW Expert Academy

1. 부모노드(int)와 자식노드 2개(int[2])의 구성을 가지는 클래스를 만들어줌.

2.  위의 클래스를 요소로 가지는 배열을 선언해줌.

3. 노드 추가

4. 루트노드 반환

5. 트리 출력

 

package DataStructure;

import java.util.Scanner;

class Tree{
	static final int MAX_CHILD_NUM = 2;
	//부모노드와 자식노드 2개의 기본 형태를 정의해주는 클래스
	class TreeNode{
		int parent;
		int[] child = new int[MAX_CHILD_NUM];
		//생성자
		public TreeNode(int parent) {
			this.parent = parent;
			for(int i = 0; i < MAX_CHILD_NUM; i++)
				//기본 값은 -1로 설정
				child[i] = -1;
		}
	}
	//((int)부모노드 + (int[2])자식노드 2개) 구성을 요소로 갖는 배열 선언
	TreeNode[] treenode;
	int nodeNum;
	//생성자
	public Tree(int nodeNum) {
		this.nodeNum = nodeNum;
		//입력수보다 하나 더 많게 배열 초기화 해줌
		treenode = new TreeNode[nodeNum + 1];
		for(int i = 0; i <= nodeNum; i++)
			//각 구성의 parent는 -1로 초기화 해줌
			treenode[i] = new TreeNode(-1);
	}
	//트리에 데이터 추가
	public void addChild(int parent, int child) {
		int found = -1;
		for(int i = 0; i < MAX_CHILD_NUM; i++) {
			//데이터가 저장돼있지 않으면
			if(treenode[parent].child[i] == -1) {
				//found에 데이터가 없는 index를 저장
				found = i;
				break;
			}
		}
		//두 자식노드 모두 데이터가 저장돼있으면 return
		if(found == -1)
			return;
		//해당 위치에 값을 저장해주고
		treenode[parent].child[found] = child;
		//child의 parent를 저장해준다. >> 이런 식으로 연결되게 함
		treenode[child].parent = parent;
	}
	//root 노드 찾기
	public int getRoot() {
		//처음부터 전체탐색
		for(int i = 1; i < nodeNum; i++) {
			//parent가 아무것도 가리키고 있지 않으면 == 초기화 상태 그대로면
			if(treenode[i].parent == -1)
				return i;
		}
		//모든 노드가 부모노드를 가지고 있으면
		return -1;
	}
	//노드 출력
	public void preOrder(int root) {
		System.out.printf("%d ", root);
		
		for(int i = 0; i < MAX_CHILD_NUM; i++) {
			int child = treenode[root].child[i];
			//값이 있는 경우에만 출력
			//재귀호출로 끝까지 출력해줌
			//출력되는 모양은 왼쪽부터 끝까지 출력 후, 끝에서부터 오른쪽 노드도 하나씩 출력해줌.
			if(child != -1)
				preOrder(child);
		}
	}
}

public class DS_Tree {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		for(int t = 1; t <= T; t++) {
			int node = sc.nextInt();
			int edge = sc.nextInt();
			
			//Tree 객체 생성
			Tree tree = new Tree(node);
			
			for(int i = 0; i < edge; i++) {
				int parent = sc.nextInt();
				int child = sc.nextInt();
				//값 저장
				tree.addChild(parent, child);
			}
			
			int root = tree.getRoot();
			System.out.printf("#%d ", t);
			//노드 출력
			tree.preOrder(root);
			System.out.println();
		}
		sc.close();
	}
}