[Data Structure] Java 이진트리(Binary Tree) 구현

• 이 글은 "온라인 자바 스터디 내용"을 정리한 글입니다.

이진트리(Binary Tree)란?

• 트리란 노드와 간선으로 이루어져 반복적으로 정의되는 자료구조입니다.

• 이진 트리는 트리의 종류 중 하나로 모든 노드가 두 개의 서브트리를 가지고 있는 트리입니다.

• 이진 트리의 서브 트리는 공백이 될 수도 있고 하나의 서브트리만 가지거나 두 개 모두 가질 수도 있습니다.

이진트리 구현

노드 클래스

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

    public Node(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}

먼저 이진트리를 구현하기 전에 이진트리에 필요한 노드를 클래스로 표현해야 합니다. 이 때 노드 내에 담을 데이터와 왼쪽 서브트리, 오른쪽 서브트리를 가리킬 포인터를 가져야 합니다.

이진트리 클래스

• void push(Node node) : 노드를 트리에 추가하는 함수
• int pop(Node node) : 노드를 트리에서 제거하는 함수
• boolean contain(Node node) : 노드가 트리에 있는지 확인하는 함수
• Node removeLastNode(Node node) : 트리에서 마지막 노드를 제거하는 함수
• boolean isSame(Node a, Node b) : 두 개의 노드가 같은 노드인지 확인하는 함수

	import java.util.LinkedList;
	import java.util.Queue;
	public class BinaryTree {
	Node head;
	int size;
	public BinaryTree() {
	head = null;
	size = 0;
	}
	public void push(Node nd) {
	if (size == 0) {
	Node node = nd;
	head = node;
	}
	else {
	Node node = head;
	Queue<Node> q = new LinkedList<Node>();
	q.add(node);
	while (!q.isEmpty()) {
	Node temp = q.poll();
	if (temp.left == null) {
	temp.left = nd;
	break;
	}
	else {
	q.add(temp.left);
	}
	if (temp.right == null) {
	temp.right = nd;
	break;
	}
	else {
	q.add(temp.right);
	}
	}
	}
	size++;
	}
	public int pop(Node node) {
	if (contain(node)) {
	Node lastNode = removeLastNode();
	if(head != null){
	if(isSame(head,node)){
	head.value = lastNode.value;
	}
	else{
	Queue<Node> q = new LinkedList<Node>();
	q.add(head);
	while(!q.isEmpty()){
	Node temp = q.poll();
	if(temp.left != null){
	if(isSame(temp.left,node)){
	temp.left.value = lastNode.value;
	break;
	}else{
	q.add(temp.left);
	}
	}
	if(temp.right != null){
	if(isSame(temp.right,node)){
	temp.right.value = lastNode.value;
	break;
	}
	}
	}
	}
	}
	size--;
	return 1;
	}
	return 0;
	}
	public boolean contain(Node node) {
	boolean check = false;
	if (size != 0) {
	Queue<Node> q = new LinkedList<Node>();
	q.add(head);
	while (!q.isEmpty()) {
	Node temp = q.poll();
	if (isSame(temp,node)) {
	check = true;
	break;
	}
	if (temp.left != null) {
	q.add(temp.left);
	}
	if (temp.right != null) {
	q.add(temp.right);
	}
	}
	}
	return check;
	}
	private Node removeLastNode() {
	Node last = head;
	if(size == 1){
	head = null;
	}
	else {
	Queue<Node> q = new LinkedList<Node>();
	q.add(last);
	while (!q.isEmpty()) {
	Node temp = q.poll();
	last = temp;
	if (temp.left != null) {
	q.add(temp.left);
	}
	if (temp.right != null) {
	q.add(temp.right);
	}
	}
	q.add(head);
	while(!q.isEmpty()){
	Node temp = q.poll();
	if(temp.left != null){
	if(isSame(temp.left,last)){
	temp.left = null;
	break;
	}else{
	q.add(temp.left);
	}
	}
	if(temp.right != null){
	if(isSame(temp.right,last)){
	temp.right = null;
	break;
	}else{
	q.add(temp.right);
	}
	}
	}
	}
	return last;
	}
	private boolean isSame(Node a, Node b) {
	if (a.value == b.value && a.left == b.left && a.right == b.right) {
	return true;
	}
	return false;
	}
	public void printBFS(Node node) {
	Queue<Node> queue = new LinkedList<Node>();
	queue.add(node);
	while (!queue.isEmpty()) {
	Node temp = queue.poll();
	System.out.println(temp.value);
	if (temp.left != null) {
	queue.add(temp.left);
	}
	if (temp.right != null) {
	queue.add(temp.right);
	}
	}
	}
	public void printDFS(Node node) {
	if(node.left == null && node.right == null){
	System.out.println(node.value);
	}else{
	if(node.left != null){
	printDFS(node.left);
	}
	System.out.println(node.value);
	if(node.right != null){
	printDFS(node.right);
	}
	}
	}
	}

view raw Binary Tree.java hosted with ❤ by GitHub

BFS (Breadth-First Search)란?

• BFS는 그래프 전체를 탐색하는 알고리즘 중 하나로 루트 노드에서부터 시작하여 가까운 노드부터 먼저 탐색하는 방법입니다.
• 루트노드부터 가까운 정점을 방문하고 멀리 떨어져 있는 노드는 상대적으로 나중에 방문함으로써 노드를 넓게 탐색합니다.
• BFS 알고리즘 구현 시 큐(Queue) 를 이용하여 구현합니다.

    public void printBFS(Node node) {

        Queue<Node> queue = new LinkedList<Node>();
        queue.add(node);

        while (!queue.isEmpty()) {
            Node temp = queue.poll();
            System.out.println(temp.value);

            if (temp.left != null) {
                queue.add(temp.left);
            }

            if (temp.right != null) {
                queue.add(temp.right);
            }
        }
    }

DFS(Depth-First Search)란?

• DFS도 마찬가지로 그래프 전체를 탐색하는 알고리즘으로 루트노드에서 하나의 노드를 방문하게 되면 다음 인접한 노드로 가기 전에 방문한 노드를 끝까지 탐색하는 방법입니다.
• 하나의 노드를 끝까지 방문하기 때문에 노드를 깊게 탐색한다고 볼 수 있습니다.
• DFS 알고리즘 구현 시 재귀함수 또는 스택을 이용하여 구현합니다.

    public void printDFS(Node node) {

        if(node.left == null && node.right == null){
            System.out.println(node.value);
        }else{
            if(node.left != null){
                printDFS(node.left);
            }
            System.out.println(node.value);
            if(node.right != null){
                printDFS(node.right);
            }
        }
    }

결과

public class Main {
    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();

        Node node = new Node(3);
        Node node1 = new Node(5);
        Node node2 = new Node(7);
        Node node3 = new Node(4);
        Node node4 = new Node(2);

        bt.push(node);
        bt.push(node1);
        bt.push(node2);
        bt.push(node3);
        bt.push(node4);

        System.out.println("BFS로 탐색합니다");
        bt.printBFS(node);

        System.out.println("\nDFS로 탐색합니다");
        bt.printDFS(node);
    }
}