자바에서 이진 트리 구현

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.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바꾸면 됩니다.
  • 노드에는 정확히 하나의 자식 이 있습니다. 부모 노드에서이 노드를 유일한 자식으로 바꿉니다.
  • 노드에는 두 개의 자식 이 있습니다. 트리 재구성이 필요하기 때문에 가장 복잡한 경우입니다.

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

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. 트리 횡단

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

We'll use the same tree that we used before and we'll show the traversal order for each case.

4.1. Depth-First Search

Depth-first search is a type of traversal that goes deep as much as possible in every child before exploring the next sibling.

There are several ways to perform a depth-first search: in-order, pre-order and post-order.

The in-order traversal consists of first visiting the left sub-tree, then the root node, and finally the right sub-tree:

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

If we call this method, the console output will show the in-order traversal:

3 4 5 6 7 8 9

Pre-order traversal visits first the root node, then the left subtree, and finally the right subtree:

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

And let's check the pre-order traversal in the console output:

6 4 3 5 8 7 9

Post-order traversal visits the left subtree, the right subtree, and the root node at the end:

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

Here are the nodes in post-order:

3 5 4 7 9 8 6

4.2. Breadth-First Search

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

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

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

public void traverseLevelOrder() { if (root == null) { return; } Queue 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에서 사용할 수 있습니다.