자바로 트리 만들기

자바에서 간단한 트리를 만들어보았다.

 

클래스 Node

필드: 이름, 부모, 자식들

public int name;

public Node parent;

public ArrayList<Node> childs;

 

메소드: 생성자

public Node (int name){

    this.name = name;

    childs = new ArrayList<Node>();

}

 

 

트리는 Node 객체들의 배열이다.

직관적으로 사용하기 위하여 1번 노드는 tree[1], 2번 노드는 tree[2]인 것으로 한다.

즉 5개의 노드를 가진 트리는 길이가 6인 Node 배열로 구현한다.

 

parent가 null이면 그 노드는 root이다.

childs가 비어있다면 그 노드는 leaf이다.

 

코드

다음은 입력받은 노드의 바로 아랫단계의 자식들을 모두 출력하는 코드이다. 

//트리 만들기 연습
import java.util.ArrayList;
import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		Node[] tree = new Node[6];
		for(int i = 1; i<6; i++) {
			tree[i] = new Node(i);
		}
		
		tree[1].childs.add(tree[2]);
		tree[2].parent = tree[1];
		
		tree[1].childs.add(tree[3]);
		tree[3].parent = tree[1];
		
		tree[2].childs.add(tree[4]);
		tree[4].parent = tree[2];
		
		tree[2].childs.add(tree[5]);
		tree[5].parent = tree[2];
		
		while(true) {
			System.out.println("x 를 입력하면 종료됩니다");
			System.out.print("입력>>");
			//입력값 받기
			String input = br.readLine();
			//x가 입력되면 종료
			if (input.equals("x")) System.exit(0);
			//입력받은 노드의 자식을 출력
			int num = Integer.parseInt(input);
			for(Node n : tree[num].childs) {
				System.out.println(n.name);
			}
		}
		
	}

}

//노드 클래스
class Node{
	public int name;	//노드 이름(번호)
	public Node parent;	//부모
	public ArrayList<Node> childs;	//자식들
	
	//생성자
	public Node(int name) {
		this.name = name;
		childs = new ArrayList<Node>();
	}
}

 

다음은 입력받은 노드의 서브트리에 속하는 모든 노드들을 출력하는 코드이다. 재귀 방식의 깊이우선탐색을 사용하였다.

//서브트리 모두 방문 연습
import java.util.ArrayList;
import java.io.*;

public class Main {
	
	static Node[] tree;
	
	//자신과 서브트리의 모든 노드들을 출력하는 함수
	static void printSubs (Node n) {
		System.out.println(n.name);
		
		for(Node m: n.childs) {
			printSubs(m);
		}
		
	}

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		tree = new Node[6];
		for(int i = 1; i<6; i++) {
			tree[i] = new Node(i);
		}
				
		tree[1].childs.add(tree[2]);
		tree[2].parent = tree[1];
		
		tree[1].childs.add(tree[3]);
		tree[3].parent = tree[1];
		
		tree[2].childs.add(tree[4]);
		tree[4].parent = tree[2];
		
		tree[2].childs.add(tree[5]);
		tree[5].parent = tree[2];
		
		while(true) {
			System.out.println("x 를 입력하면 종료됩니다");
			System.out.print("입력>>");
			//입력값 받기
			String input = br.readLine();
			//x가 입력되면 종료
			if (input.equals("x")) System.exit(0);
			//입력받은 노드의 서브트리에 속하는 모든 노드들을 출력
			int num = Integer.parseInt(input);
			printSubs(tree[num]);
		}
		
	}

}

//노드 클래스
class Node{
	public int name;	//노드 이름(번호)
	public Node parent;	//부모
	public ArrayList<Node> childs;	//자식들
	
	//생성자
	public Node(int name) {
		this.name = name;
		childs = new ArrayList<Node>();
	}
}