[자료구조] 트리(Tree) - 이진트리, 트리순회, 구현(Java)

트리

트리는 노드와 에지로 연결된 그래프의 특수한 형태로 다음과 같은 특징을 갖는다. 

• 순환 구조(Cycle)를 지니고 있지 않고, 1개의 루트 노드가 존재한다.
• 루트노드를 제외한 나머지 노드는 단 1개의 부모노드를 가진다.
• 트리의 서브 트리 역시 트리의 모든 특징을 따른다.
• 비선형 자료구조로 계층적 관계를 표현한다. Ex) 디렉터리 구조, 조직도
• 노드가 N개인 트리는 항상 N-1개의 간선(edge)을 가진다.
  즉, 간선은 항상 (정점의 개수 - 1) 만큼을 가진다.

 

트리의 구성요소

기본적인 트리의 구성요소를 정리해 보자.

• 정점(Vertex): A, B, C와 같은 값으로 나타내며, 트리 구조에서 노드(node)로 표현된다.
• 간선(Edge): 정점 간에 연결된 선이다.
• 자식노드(Child), 부모 노드(Parent)
• 형제노드(Silbling): 같은 부모를 가진 노드를 말한다.
• 리프 노드(Leef): 더 이상 뻗어 날 수 없는 마지막 노르를 일컫는다.

 

• 차수(degree): 각 노드가 갖는 자식의 수, 모든 노드의 차수가 n개 이하인 트리를 n진 트리라고 한다. 

• 조상(ancestor): 어떤 노드에서 위쪽으로 뻗어나간 간선을 따라가면 만나는 모든 노드를 말한다.
• 자손(descendant): 어떤 노드에서 아래쪽으로 뻗어나간 모든 노드를 말한다.
• 루트 노드(Root): 트리의 시작 노드이다.
• 높이(height): 루트 노드에서 가장 멀리 있는 리프 노드까지의 거리이다.
• 레벨(level): 루트 노드에서 떨어진 거리이다.

 

이진트리

위에 용어 설명에서 차수에 따라 트리의 명칭이 결정된다고 했는데 이진트리는 차수가 2개 이하인 트리를 말한다. 트리의 종류는 매우 다양하지만 코딩 테스트를 위한 학습에서는 `이진트리(binary tree)`만 제대로 알고 있으면 충분하다.

 

이진트리는 배열이나 포인터로 구현할 수 있으며, 배열을 이용한 구현 방법을 알아볼 것이다.

배열로 표현하기 

비선형 계층 구조인 트리를 배열로 표현하기 위해선 다음 3가지의 규칙이 필요하다.

• 루트 노드는 배열 인덱스 1번에 저장한다.
• 왼쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스의  `x 2`이다.
• 오른쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스의  `x 2 + 1`이다.

 

위 규칙에 따라 인덱스를 붙이면 다음과 같다. `1 -> 2 -> 4-> 8` 순으로 인덱스가 부모 x 2로 증가한다. 빨간색으로 표현된 인덱스를 따라가 보면 `1 -> 3 -> 7`순이로 부모 x 2 + 1로 증가한다.

 

실제 위 그림을 배열로 넣으면 다음과 같다. 

인덱스	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
값		1	4	8	3	5		7	2						6

만약 인덱스를 0부터 시작한다면 왼쪽노드는 부모 노드의 배열 인덱스 x 2 + 1이 되고, 오른쪽 노드는 부모 노드의 배열 인덱스 x 2 + 2가 된다. 입력값에 따라 루트 노드를 0 혹은 1로 정해야 되는 경우가 있어 알아두자.

 

트리를 배열로 표현한 걸 보면 빈 값이 많이 보인다. 노드들의 부모-자식 관계를 곱셈 연산하여 배열의 인덱스로 사용하기 때문에 실제 노드보다 많은 공간을 사용할 수밖에 없다. 즉, 배열 방식은 공간의 낭비(메모리)가 생기는 단점이 있다. 

 

그럼에도 배열 표현방식은 이진트리를 표기하기에 난이도가 많이 낮고, 메모리만 넉넉하다면 구현 시간을 단축하는 용도로 많이 사용된다. 코딩테스트에서도 대부분 배열 구현으로 해결할 수 있기 때문에 많이 사용된다. 

 

다음 표는 배열의 인덱스 간의 상관관계를 나타낸다. 중요한 개념이니 숙지하도록 하자.

이동 목표 노드	인덱스	연산 제약 조건 (N=노드 개수)
루트 노드	index = 1
부모 노드	index / 2	현재의 노드가 루트가 아님
왼쪽 자식 노드	index*2	index*2 < N
오른쪽 자식 노드	index*2+1	index*2+1 < N

 

실 구현 코드(Java)

아래 코드는 루트 노드가 인덱스 0이라고 가정하에 만들어졌으니, 위에 이진트리 조건에 따라 진행한 코드이다.

public class BinaryTreeArray {
    private int[] tree; // 트리를 저장할 배열
    private int capacity; // 트리의 최대 크기

    public BinaryTreeArray(int capacity) {
        this.tree = new int[capacity];
        this.capacity = capacity;

        // -1로 초기화하여 빈 노드를 나타냄
        for (int i = 0; i < capacity; i++) {
            tree[i] = -1;
        }
    }

    // 루트 노드 설정
    public void setRoot(int value) {
        tree[0] = value;
    }

    // 왼쪽 자식 설정
    public void setLeft(int parentIndex, int value) {
        int leftIndex = 2 * parentIndex + 1;
        if (leftIndex >= capacity) {
            System.out.println("왼쪽 자식을 설정할 공간이 없습니다.");
            return;
        }
        if (tree[parentIndex] == -1) {
            System.out.println("부모 노드가 존재하지 않습니다.");
            return;
        }
        tree[leftIndex] = value;
    }

    // 오른쪽 자식 설정
    public void setRight(int parentIndex, int value) {
        int rightIndex = 2 * parentIndex + 2;
        if (rightIndex >= capacity) {
            System.out.println("오른쪽 자식을 설정할 공간이 없습니다.");
            return;
        }
        if (tree[parentIndex] == -1) {
            System.out.println("부모 노드가 존재하지 않습니다.");
            return;
        }
        tree[rightIndex] = value;
    }

    // 트리 출력
    public void printTree() {
        for (int i = 0; i < capacity; i++) {
            if (tree[i] == -1) {
                System.out.print("null ");
            } else {
                System.out.print(tree[i] + " ");
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        BinaryTreeArray binaryTree = new BinaryTreeArray(10);

        // 루트 설정
        binaryTree.setRoot(1);

        // 자식 노드 설정
        binaryTree.setLeft(0, 2);   // 루트의 왼쪽 자식
        binaryTree.setRight(0, 3);  // 루트의 오른쪽 자식
        binaryTree.setLeft(1, 4);   // 왼쪽 자식(2)의 왼쪽 자식
        binaryTree.setRight(1, 5);  // 왼쪽 자식(2)의 오른쪽 자식

        // 트리 출력
        System.out.println("트리 출력:");
        binaryTree.printTree();
    }
}

결과값은 다음과 같이 나온다.

트리 출력:
1 2 3 4 5 null null null null null

 

트리 순회

선형 자료구조인 배열과 리스트의 경우, 순회하는 법이 인덱스 `0,1,2`부터 `n-1`까지로 방법이 하나로 정해져 있기 때문에, 순회하는 방법을 따로 배우지 않는다. 하지만 트리의 경우 비선형 자료구조이므로 순회하는 방법이 여러 가지가 존재한다.

• lever-order traversal(레벨순회)
• preorder treversal(전위순회), inorder traversal(중위순회), postorder traversal(후위순회)

 

레벨순회(level-order traversal)

위와 같은 트리가 있다고 가정한다면, 레벨 별 정점의 값을 다음과 같다.

level 0	A
level 1	B C D
level 2	E F G H I
level 3	J K L

레벨 순회는 말 그대로 level 별로 순회하는 것을 말한다.

( A ) --> ( B, C, D ) --> ( E, F, G, H, I ) --> ( J, K, L )

 

레벨 순회 구현

코드를 이용해 구현해 보자. 

public static void levelOrder(TreeNode root) {
    if (root == null) {
        System.out.println("트리가 비어 있습니다.");
        return;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        TreeNode currentNode = queue.poll();

        // 방문한 노드를 출력
        System.out.println("방문한 노드: " + currentNode.value);

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

BFS(너비 우선 탐색)는 트리의 각 레벨을 순차적으로 탐색한다. 이는 레벨 순회의 정의와 일치한다. BFS는 큐로 구현되고, 큐에 현재 노드의 자식을 순서대로 넣기만 하면 탐색 순서를 자연스럽게 보장이 된다. 

 

레벨 순회의 코드 법칙

1. 큐에 노드를 추가
   • 탐색할 노드를 큐에 추가한다.
   • 시작점은 항상 루트 노드이다.
2. 큐에서 노드 제거 및 방문 처리
   • 큐에서 노드를 꺼낸다. `poll()`
   • 해당 노드를 방문처리 한다. `System.out.println()`
3. 자식 노드를 큐에 추가
   • 현재 노드의 왼쪽 자식과 오른쪽 자식을 확인한다.
   • 자식이 존재하면 큐에 추가한다.
4. 큐가 비면 탐색 종료
   • 큐가 비어 있는 경우, 더 이상 탐색할 노드가 없으므로 탐색이 종료된다.

 

전위순회, 중위순회, 후위순회

 

1. 전위 순회

전위 순회는 현재 노드를 부모 노드로 생각했을 때 `부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드`순서로 방문한다.

 

다음 트리를 이용해 전위 순회를 진행해 보자.

 

01단계 

루트 노드에서 시작하며, 현재 노드를 부모노드라고 생각하면 방문 순서는 `1 -> 4 -> 8`이다. 그러니 노드 `을 방문한 다음 왼쪽 자식은 노드 4로 이동한다. 

 

02 단계

노드 4로 이동하였고, 방문 순서는 `4 -> 3 -> 5`이므로 자신을 방문하고 3으로 이동한다. 

 

03 단계

노드 3으로 이동하였고, 방문순서는 `3 -> 2 -> 오른쪽 자식 없음`이므로 자신을 방문하고 2로 이동한다.

 

04 단계

노드 2로 이동하였고, 2의 경우 자식노드가 없기 때문에 3으로 거슬러 올라갑니다. 3은 이미 왼쪽 자식을 방문하였고 오른쪽 자식이 없으니, 부모로 거슬러 올라갑니다. 

 

노드 4에서는 오른쪽 자식인 노드 5의 값이 있으니 5로 이동합니다.

 

05 단계

마찬가지로 노드 5를 출력하고 방문할 자식이 없으므로 1까지 거슬러 올라가 남은 오른쪽 자식인 노드 8로 이동한다. 

 

06 단계

이런 방식으로 출력한다면 아래와 같은 순서로 순회하게 된다.

1 -> 4 -> 3 -> 2 -> 5 -> 8 -> 7 -> 6 

 

2. 중위 순회

중위 순회는 현재 노드를 부모 노드라 가정했을 때 방문 우선순위가 `왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드`이다.

여기서 주의할 점이 중위 순회에는 거쳐가는 노드, 즉, 현재 노드를 거치기만 할 뿐 방문하지는 않는다. 

방문이란?

탐색에서 방문이란 탐색을 마친 상태를 의미한다. 탐색 과정에서 지나치는 것과 그렇지 않은 것을 구분하기 위해 방문이라는 표현을 사용한다. 중위 순회에 경우 부모노드부터 시작하지만 부모노드는 지나가고 왼쪽 자식부터 탐색을 한다.

 

위와 같은 트리로 설명해 보자면 다음과 같은 순서로 진행된다. 

01 단계

노드 1에서 방문 우선순위는 `4 -> 1 -> 8`이다. 우선 노드 4로 이동한다. 

노드 4에서도 방문 우선순위를 확인해 보면 `3 -> 4 -> 5`이므로 노드 3으로 이동한다.

노드 3에서 우선순위는 `2 -> 3 -> 오른쪽 자식 없음`이므로 최종적으로 노드 2로 이동한다.

 

02 단계

노드 2에서 우선순위는 자식 노드들이 없으므로 없다. 자신을 방문처리 한 후 노드 3으로 거슬러 올라간다. 노드 3은 `2 -> 3 -> 오른쪽 자식 없음`이기 때문에 방문 순서가 본인이다. 자신을 방문하고 오른쪽 자식이 없으므로 거슬러 올라간다. 

 

03 단계

노드 4에선 우선순위가 `3 -> 4 -> 5`이므로 자신을 방문한 후 노드 5로 이동하게 된다.

 

04 단계

노드 5의 경우 자식 노드들이 없으니 본인을 방문 처리한 후 노드 1까지 거슬러 올라간다.

 

05 단계

노드 1의 우선순위는 `4 -> 1 ->8`이기 때문에 자신을 방문하고 노드 8로 이동한다. 

이후 과정은 동일하며 다음과 같은 순서로 진행이 된다.

2 -> 3 -> 4 -> 5 -> 1 -> 8 -> 6 -> 7

 

3. 후위순회

후위순회는 현재 노드를 부모 노드로 생각했을 때 `왼쪽 자식 -> 오른쪽 자식 -> 부모` 순서로 방문한다.

 

01단계

• 노드 1부터 시작한다. `4 -> 8 -> 1` 순서로 진행되므로 왼쪽 자식 노드인 4로 이동한다.
• 노드 4로 이동 후 진행 순서가 `3 -> 5 -> 4`이므로 다시 왼쪽 자식인 3으로 이동한다.
• 노드 3은 `2 -> 오른쪽 자식 없음 -> 3`이므로 2로 이동한다.

 

02단계

노드 2의 경우 `왼쪽 자식 없음 -> 오른쪽 자식 없음 -> 2`이므로 본인을 방문처리 한 후 3으로 거슬러 올라간다.

 

03단계

노드 3의 경우 `2 -> 오른쪽 자식 없음 -> 3`이다. 2는 이미 방문했으니 본인을 방문 후 노드 4로 거슬러 올라간다.

 

04단계

이미 다른 순회를 이해했다면, 나머지 과정도 쉽게 이해가 가능할 것이다.

최종적으로 2 -> 3 -> 5 -> 4 -> 6 -> 7 -> 8 -> 1 순으로 방문한다.

 

전위순회, 중위순회, 후위 순회 구현(Java)

 

1. 전위순회

위에서 말했듯이 전위 순회에 경우 `부모 -> 왼쪽 -> 오른쪽`순으로 방문한다.  그래서 다음과 같은 코드 구성으로 진행된다. 

• 현재 노드 방문: System.out.print(node.data)
• 왼쪽 서브트리 재귀 호출: preOrder(node.left)
• 오른쪽 서브트리 재귀 호출: preOrder(node.right)

// 전위순회 (Preorder Traversal)
void preOrder(Node node) {
    if (node == null) return;
    System.out.print(node.data + " "); // 현재 노드 방문
    preOrder(node.left);              // 왼쪽 서브트리 순회
    preOrder(node.right);             // 오른쪽 서브트리 순회
}

 

2. 중위 순회

중위 순회에 경우 `왼쪽 -> 부모 -> 오른쪽`순으로 방문한다. 

 

• 왼쪽 서브트리 재귀 호출: inOrder(node.left)
• 현재 노드 방문: System.out.print(node.data)
• 오른쪽 서브트리 재귀 호출: inOrder(node.right)

 

// 중위순회 (Inorder Traversal)
void inOrder(Node node) {
    if (node == null) return;
    inOrder(node.left);               // 왼쪽 서브트리 순회
    System.out.print(node.data + " "); // 현재 노드 방문
    inOrder(node.right);              // 오른쪽 서브트리 순회
}

 

3. 후위 순회

후위 순회에 경우 `왼쪽 -> 오른쪽 -> 부모`순으로 방문한다. 

 

• 왼쪽 서브트리 재귀 호출: postOrder(node.left)
• 오른쪽 서브트리 재귀 호출: postOrder(node.right)
• 현재 노드 방문: System.out.print(node.data)

 

// 후위순회 (Postorder Traversal)
void postOrder(Node node) {
    if (node == null) return;
    postOrder(node.left);             // 왼쪽 서브트리 순회
    postOrder(node.right);            // 오른쪽 서브트리 순회
    System.out.print(node.data + " "); // 현재 노드 방문
}

 

4. 전체 코드 구현 및 결과값

위에 이론 설명에서 사용한 트리 구조이다. 해당 트리를 구현을 통해 결과가 같은지 확인해 보자. 

        1
      /   \
     4     8
    / \      \
   3   5      7
  /            \
 2              6

 

 

전체코드

// 노드 클래스
class Node {
    int data;
    Node left, right;

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

// 트리 클래스
class BinaryTree {
    Node root;

    // 전위순회 (Preorder Traversal)
    void preOrder(Node node) {
        if (node == null) return;
        System.out.print(node.data + " "); // 현재 노드
        preOrder(node.left);              // 왼쪽 서브트리
        preOrder(node.right);             // 오른쪽 서브트리
    }

    // 중위순회 (Inorder Traversal)
    void inOrder(Node node) {
        if (node == null) return;
        inOrder(node.left);               // 왼쪽 서브트리
        System.out.print(node.data + " "); // 현재 노드
        inOrder(node.right);              // 오른쪽 서브트리
    }

    // 후위순회 (Postorder Traversal)
    void postOrder(Node node) {
        if (node == null) return;
        postOrder(node.left);             // 왼쪽 서브트리
        postOrder(node.right);            // 오른쪽 서브트리
        System.out.print(node.data + " "); // 현재 노드
    }
}

// 실행 코드
public class Main {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        // 트리 구성
        tree.root = new Node(1);
        tree.root.left = new Node(4);
        tree.root.right = new Node(8);

        tree.root.left.left = new Node(3);
        tree.root.left.right = new Node(5);

        tree.root.left.left.left = new Node(2);

        tree.root.right.right = new Node(7);
        tree.root.right.right.right = new Node(6);

        System.out.println("Preorder Traversal:");
        tree.preOrder(tree.root); // 출력 예: 1 4 3 2 5 8 7 6

        System.out.println("\nInorder Traversal:");
        tree.inOrder(tree.root); // 출력 예: 2 3 4 5 1 8 7 6

        System.out.println("\nPostorder Traversal:");
        tree.postOrder(tree.root); // 출력 예: 2 3 5 4 6 7 8 1
    }
}

실행 결과

1. Preorder Traversal:

1 4 3 2 5 8 7 6

2. Inorder Traversal:

2 3 4 5 1 8 7 6

3. Postorder Traversal:

2 3 5 4 6 7 8 1

 

위에서 설명한 이론과 동일한 결과값이 나온 것을 확인할 수 있다.

 

포인트와 인접리스트 표현

1. 포인터로 구현

포인터로 구현하는 방식은 위에 나온 코드와 같이 클래스형태로 만들어 관리하는 것을 말한다. 

// 노드 클래스
class Node {
    int data;
    Node left, right;

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

// 포인터의 기능 코드
class PointerTree {
    Node root;

    public void setRoot(int data) {
        root = new Node(data);
    }

    public Node addLeft(Node parent, int data) {
        parent.left = new Node(data);
        return parent.left;
    }

    public Node addRight(Node parent, int data) {
        parent.right = new Node(data);
        return parent.right;
    }

    public void printPreOrder(Node node) {
        if (node == null) return;
        System.out.print(node.data + " ");
        printPreOrder(node.left);
        printPreOrder(node.right);
    }
}

// 실행 코드
public class PointerTreeDemo {
    public static void main(String[] args) {
        PointerTree tree = new PointerTree();
        tree.setRoot(1);

        Node leftChild = tree.addLeft(tree.root, 4);
        Node rightChild = tree.addRight(tree.root, 8);

        tree.addLeft(leftChild, 3);
        tree.addRight(leftChild, 5);
        Node rightSubChild = tree.addRight(rightChild, 7);
        tree.addRight(rightSubChild, 6);

        tree.printPreOrder(tree.root); // 출력: 1 4 3 5 8 7 6
    }
}

 

노드를 정의하여 관리하며 노드의 값, 왼쪽 자식의 값, 오른쪽 자식의 값을 가지고 있다. 포인터로 표현한 트리는 배열과 달리 인덱스 연산을 하지 않으므로 메모리 공간을 낭비하진 않지만, 실제 노드를 따라가도록 구현해야 하므로 구현 난이도가 배열보단 높다.

 

2. 인접리스토로 구현 

인접 리스트는 그래프를 인접 리스트로 표현한 것과 같은 방식이다. 인접 리스트로 트리를 구현하기 위해선 정점의 번호(수) 리스트를 만들어야 한다. 그런 다음 정점마다 연결된 노드의 정보들을 리스트로 삽입하는 구조이다. 

import java.util.ArrayList;
import java.util.List;

class ListTree {
    List<List<Integer>> tree;

    public ListTree(int size) {
        // 트리 초기화 (노드 개수에 맞게 리스트 생성)
        tree = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            tree.add(new ArrayList<>());
        }
    }

    // 부모와 자식 관계 추가
    public void addEdge(int parent, int child) {
        tree.get(parent).add(child);
    }

    // 트리 출력
    public void printTree() {
        for (int i = 0; i < tree.size(); i++) {
            System.out.println(i + " -> " + tree.get(i));
        }
    }
}

public class ListTreeDemo {
    public static void main(String[] args) {
        // 노드 수를 8로 설정 (0 ~ 7 노드)
        ListTree tree = new ListTree(8);

        // 트리 구성
        tree.addEdge(1, 4);
        tree.addEdge(1, 8);
        tree.addEdge(4, 3);
        tree.addEdge(4, 5);
        tree.addEdge(8, 7);
        tree.addEdge(7, 6);

        // 트리 출력
        tree.printTree();

        /*
        출력:
        0 -> []
        1 -> [4, 8]
        2 -> []
        3 -> []
        4 -> [3, 5]
        5 -> []
        6 -> []
        7 -> [6]
        8 -> []
        */
    }
}

인접 리스트로 표현 시 자식 노드가 2개 이상인 경우에서 표현하기 쉽고, 메모리 또한 크게 낭비되지 않는다. 어떤 정점에서 이동할 수 있는 다음 정점을 빠르게 탐색 가능하여 시간 복잡도 면에서도 이점이 있다. 그렇기 때문에 인접 리스트는 트리를 포함한 그래프 문제에서 가능 많이 사용하는 방식이다.