1. 소개

이 기사에서는 Java에서 이진 트리 구현을 다룰 것입니다.

이 기사를 위해 int 값 을 포함 하는 정렬 된 이진 트리 를 사용 합니다 .

2. 바이너리 트리

이진 트리는 각 노드가 최대 2 개의 자식을 가질 수있는 재귀 데이터 구조입니다.

일반적인 이진 트리 유형은 이진 검색 트리 입니다. 모든 노드는 왼쪽 하위 트리의 노드 값보다 크거나 같고 오른쪽 하위 트리의 노드 값보다 작거나 같은 값을 갖습니다. 나무.

다음은 이러한 유형의 이진 트리에 대한 빠른 시각적 표현입니다.

구현 을 위해 int 값 을 저장 하고 각 자식에 대한 참조를 유지 하는 보조 Node 클래스를 사용할 것입니다 .

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

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

그런 다음 일반적으로 루트 라고하는 트리의 시작 노드를 추가하겠습니다 .

public class BinaryTree {

    Node root;

    // ...
}

3. 일반적인 작업

이제 이진 트리에서 수행 할 수있는 가장 일반적인 작업을 살펴 ​​보겠습니다.

3.1. 요소 삽입

우리가 다룰 첫 번째 작업은 새 노드의 삽입입니다.

먼저, 트리를 정렬 상태로 유지하기 위해 새 노드를 추가 할 위치를 찾아야합니다 . 루트 노드에서 시작하여 다음 규칙을 따릅니다.

  • 새 노드의 값이 현재 노드의 값보다 낮 으면 왼쪽 자식으로 이동합니다.
  • 새 노드의 값이 현재 노드의 값보다 크면 오른쪽 자식으로 이동합니다.
  • 현재 노드가 null이면 리프 노드에 도달했으며 해당 위치에 새 노드를 삽입 할 수 있습니다.

먼저 삽입을 수행하는 재귀 메서드를 생성합니다.

private Node addRecursive(Node current, int value) {
    if (current == null) {
        return new Node(value);
    }

    if (value < current.value) {
        current.left = addRecursive(current.left, value);
    } else if (value > current.value) {
        current.right = addRecursive(current.right, value);
    } else {
        // value already exists
        return current;
    }

    return current;
}

다음으로 루트 노드 에서 재귀를 시작하는 퍼블릭 메서드를 만듭니다 .

public void add(int value) {
    root = addRecursive(root, value);
}

이제이 메서드를 사용하여 예제에서 트리를 만드는 방법을 살펴 보겠습니다.

private BinaryTree createBinaryTree() {
    BinaryTree bt = new BinaryTree();

    bt.add(6);
    bt.add(4);
    bt.add(8);
    bt.add(3);
    bt.add(5);
    bt.add(7);
    bt.add(9);

    return bt;
}

3.2. 요소 찾기

이제 트리에 특정 값이 포함되어 있는지 확인하는 메서드를 추가해 보겠습니다.

이전과 마찬가지로 먼저 트리를 순회하는 재귀 메서드를 만듭니다.

private boolean containsNodeRecursive(Node current, int value) {
    if (current == null) {
        return false;
    } 
    if (value == current.value) {
        return true;
    } 
    return value < current.value
      ? containsNodeRecursive(current.left, value)
      : containsNodeRecursive(current.right, value);
}

여기서는 현재 노드의 값과 비교하여 값을 검색 한 다음 그에 따라 왼쪽 또는 오른쪽 자식에서 계속합니다.

다음으로 루트 에서 시작하는 공용 메서드를 만들어 보겠습니다 .

public boolean containsNode(int value) {
    return containsNodeRecursive(root, value);
}

이제 트리에 삽입 된 요소가 실제로 포함되어 있는지 확인하는 간단한 테스트를 만들어 보겠습니다.

@Test
public void givenABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements() {
    BinaryTree bt = createBinaryTree();

    assertTrue(bt.containsNode(6));
    assertTrue(bt.containsNode(4));
 
    assertFalse(bt.containsNode(1));
}

추가 된 모든 노드는 트리에 포함되어야합니다.

3.3. 요소 삭제

또 다른 일반적인 작업은 트리에서 노드를 삭제하는 것입니다.

먼저 이전과 비슷한 방식으로 삭제할 노드를 찾아야합니다.

private Node deleteRecursive(Node current, int value) {
    if (current == null) {
        return null;
    }

    if (value == current.value) {
        // Node to delete found
        // ... code to delete the node will go here
    } 
    if (value < current.value) {
        current.left = deleteRecursive(current.left, value);
        return current;
    }
    current.right = deleteRecursive(current.right, value);
    return current;
}

삭제할 노드를 찾으면 세 가지 주요 사례가 있습니다.

  • 노드에는 자식이 없습니다. 이것이 가장 간단한 경우입니다. 이 노드를 부모 노드에서 null 로 바꾸면 됩니다.
  • 노드에는 정확히 하나의 자식 이 있습니다. 부모 노드에서이 노드를 유일한 자식으로 바꿉니다.
  • 노드에는 2 개의 자식 이 있습니다. 트리 재구성이 필요하기 때문에 가장 복잡한 경우입니다.

노드가 리프 노드 인 경우 첫 번째 경우를 구현하는 방법을 살펴 보겠습니다.

if (current.left == null && current.right == null) {
    return null;
}

이제 노드에 자식이 하나있는 경우를 계속해 보겠습니다.

if (current.right == null) {
    return current.left;
}

if (current.left == null) {
    return current.right;
}

여기서는 null 이 아닌 자식을 반환 하여 부모 노드에 할당 할 수 있습니다.

마지막으로 노드에 자식이 두 개인 경우를 처리해야합니다.

먼저 삭제 된 노드를 대체 할 노드를 찾아야합니다. 삭제할 노드의 가장 작은 노드의 오른쪽 하위 트리를 사용합니다.

private int findSmallestValue(Node root) {
    return root.left == null ? root.value : findSmallestValue(root.left);
}

그런 다음 삭제할 노드에 가장 작은 값을 할당하고 그 후에 오른쪽 하위 트리에서 삭제합니다.

int smallestValue = findSmallestValue(current.right);
current.value = smallestValue;
current.right = deleteRecursive(current.right, smallestValue);
return current;

마지막으로 루트 에서 삭제를 시작하는 공용 메서드를 만들어 보겠습니다 .

public void delete(int value) {
    root = deleteRecursive(root, value);
}

이제 삭제가 예상대로 작동하는지 확인하겠습니다.

@Test
public void givenABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements() {
    BinaryTree bt = createBinaryTree();

    assertTrue(bt.containsNode(9));
    bt.delete(9);
    assertFalse(bt.containsNode(9));
}

4. 트리 횡단

이 섹션에서는 깊이 우선 검색과 폭 우선 검색을 자세히 다루면서 트리를 탐색하는 다양한 방법을 살펴 봅니다.

이전에 사용한 것과 동일한 트리를 사용하고 각 사례에 대한 순회 순서를 표시합니다.

4.1. 깊이 우선 검색

깊이 우선 검색은 다음 형제를 탐색하기 전에 모든 어린이에게 최대한 깊이 들어가는 순회 유형입니다.

깊이 우선 검색을 수행하는 방법에는 여러 가지가 있습니다. 순서대로, 선주문 및 사후 주문.

순회 순회는 먼저 왼쪽 하위 트리를 방문한 다음 루트 노드를 방문하고 마지막으로 오른쪽 하위 트리를 방문하는 것으로 구성됩니다.

public void traverseInOrder(Node node) {
    if (node != null) {
        traverseInOrder(node.left);
        System.out.print(" " + node.value);
        traverseInOrder(node.right);
    }
}

이 메서드를 호출하면 콘솔 출력에 순회 순회가 표시됩니다.

3 4 5 6 7 8 9

사전 주문 순회는 먼저 루트 노드, 다음 왼쪽 하위 트리, 마지막으로 오른쪽 하위 트리를 방문합니다.

public void traversePreOrder(Node node) {
    if (node != null) {
        System.out.print(" " + node.value);
        traversePreOrder(node.left);
        traversePreOrder(node.right);
    }
}

그리고 콘솔 출력에서 ​​선주문 순회를 확인해 보겠습니다.

6 4 3 5 8 7 9

주문 후 순회는 왼쪽 하위 트리, 오른쪽 하위 트리 및 끝에있는 루트 노드를 방문합니다.

public void traversePostOrder(Node node) {
    if (node != null) {
        traversePostOrder(node.left);
        traversePostOrder(node.right);
        System.out.print(" " + node.value);
    }
}

다음은 주문 후 노드입니다.

3 5 4 7 9 8 6

4.2. 폭 우선 검색

이것은 다음 레벨로 이동하기 전에 레벨의 모든 노드 를 방문 하는 또 다른 일반적인 유형의 순회입니다 .

이러한 종류의 순회는 레벨 순서라고도하며 루트에서 시작하여 왼쪽에서 오른쪽으로 트리의 모든 레벨을 방문합니다.

구현 을 위해 큐 를 사용하여 각 레벨의 노드를 순서대로 보관합니다. List에서 각 노드를 추출하고 해당 값을 인쇄 한 다음 해당 자식을 큐에 추가합니다.

public void traverseLevelOrder() {
    if (root == null) {
        return;
    }

    Queue<Node> nodes = new LinkedList<>();
    nodes.add(root);

    while (!nodes.isEmpty()) {

        Node node = nodes.remove();

        System.out.print(" " + node.value);

        if (node.left != null) {
            nodes.add(node.left);
        }

        if (node.right != null) {
            nodes.add(node.right);
        }
    }
}

이 경우 노드의 순서는 다음과 같습니다.

6 4 8 3 5 7 9

5. 결론

이 기사에서는 Java에서 정렬 된 이진 트리를 구현하는 방법과 가장 일반적인 작업을 살펴 ​​보았습니다.

예제의 전체 소스 코드는 GitHub에서 사용할 수 있습니다 .