[java] 스택을 이용한 이진 트리 구현하기

05 Dec 2023

java

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조입니다. 이진 트리를 구현하는 방법 중 하나는 스택을 이용하는 것입니다. 스택은 LIFO(Last-In, First-Out)의 구조로 데이터를 저장하고, 이를 이용하여 이진 트리를 구현할 수 있습니다.

스택 클래스 구현하기

스택을 구현하기 위해 먼저 스택 클래스를 만들어야 합니다. Java에서는 Stack 클래스를 기본으로 제공하고 있지만, 우리는 직접 스택을 구현해보겠습니다.

public class Stack<T> {
    private LinkedList<T> stack;
    
    public Stack() {
        stack = new LinkedList<>();
    }
    
    public boolean isEmpty() {
        return stack.isEmpty();
    }
    
    public int size() {
        return stack.size();
    }
    
    public void push(T item) {
        stack.addLast(item);
    }
    
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return stack.removeLast();
    }
    
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return stack.getLast();
    }
}

위의 코드는 제네릭을 이용하여 스택을 구현한 예시입니다. LinkedList를 사용하여 내부 데이터를 관리하고, push(), pop(), peek() 등의 메서드를 제공합니다.

이진 트리 클래스 구현하기

이제 스택 클래스를 활용하여 이진 트리를 구현해보겠습니다.

public class BinaryTree<T> {
    private Node<T> root;
    
    private static class Node<T> {
        T data;
        Node<T> left;
        Node<T> right;
        
        Node(T data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }
    
    public void insert(T data) {
        if (root == null) {
            root = new Node<>(data);
            return;
        }
        
        Stack<Node<T>> nodeStack = new Stack<>();
        nodeStack.push(root);
        
        while (!nodeStack.isEmpty()) {
            Node<T> currentNode = nodeStack.pop();
            if (currentNode.left == null) {
                currentNode.left = new Node<>(data);
                break;
            } else if (currentNode.right == null) {
                currentNode.right = new Node<>(data);
                break;
            } else {
                nodeStack.push(currentNode.left);
                nodeStack.push(currentNode.right);
            }
        }
    }
}

위의 코드에서는 insert() 메서드를 통해 이진 트리에 데이터를 삽입할 수 있습니다. 스택을 통해 노드를 순회하면서 비어있는 자식 노드를 찾으면 데이터를 삽입합니다.

사용 예시

아래는 이진 트리를 사용하는 예시 코드입니다.

public class Main {
    public static void main(String[] args) {
        BinaryTree<Integer> tree = new BinaryTree<>();
        
        tree.insert(1);
        tree.insert(2);
        tree.insert(3);
        tree.insert(4);
    }
}

위의 예시 코드에서는 이진 트리에 1, 2, 3, 4를 삽입하고 있습니다.

결론

위에서는 스택을 이용하여 이진 트리를 구현하는 방법에 대해 알아보았습니다. 스택을 활용하면 이진 트리를 간편하게 구현할 수 있으며, 다양한 이진 트리 기능을 추가할 수도 있습니다.