Java 바이너리 트리 구현 및 구체적인 적용 사례에 대한 자세한 설명

Java 바이너리 트리 구현 및 구체적인 적용 사례에 대한 자세한 설명

바이너리 트리는 컴퓨터 과학에서 자주 사용되는 데이터 구조로 매우 효율적인 검색 및 정렬 작업을 수행할 수 있습니다. 이 기사에서는 Java에서 이진 트리를 구현하는 방법과 일부 특정 응용 사례에 대해 설명합니다.

이진 트리의 정의

이진 트리는 루트 노드(트리의 최상위 노드)와 여러 개의 왼쪽 하위 트리 및 오른쪽 하위 트리로 구성된 매우 중요한 데이터 구조입니다. 각 노드에는 최대 2개의 자식 노드가 있으며, 왼쪽의 자식 노드를 왼쪽 하위 트리, 오른쪽의 자식 노드를 오른쪽 하위 트리라고 합니다. 노드에 자식 노드가 없으면 리프 노드 또는 터미널 노드라고 합니다.

Java의 이진 트리 구현

Node 클래스는 Java에서 이진 트리 노드를 나타내는 데 사용할 수 있습니다. 이 클래스에는 int 유형 값과 왼쪽 및 오른쪽 하위 노드를 나타내는 두 개의 노드 유형 참조가 포함되어 있습니다. 각기. 다음은 샘플 코드입니다.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

이진 트리의 기본 연산 구현

1. 이진 트리 생성

이진 트리를 재귀적으로 생성할 수 있으며, 먼저 루트 노드를 생성한 다음 왼쪽 하위 트리와 오른쪽 노드를 생성합니다. 각각 하위 트리. 다음은 샘플 코드입니다.

public class TreeBuilder {
    public TreeNode buildTree(int[] array) {
        if (array == null || array.length == 0) {
            return null;
        }
        return build(array, 0, array.length - 1);
    }

    private TreeNode build(int[] array, int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(array[mid]);
        root.left = build(array, start, mid - 1);
        root.right = build(array, mid + 1, end);
        return root;
    }
}

2. Find node

이진 트리의 검색 작업은 매우 효율적입니다. 일반적으로 노드 값의 크기를 비교하여 왼쪽 하위 트리를 검색할지 오른쪽 하위 트리를 검색할지 결정합니다. 그리고 목표값. 다음은 샘플 코드입니다.

public class TreeSearch {
    public TreeNode search(TreeNode root, int target) {
        if (root == null || root.val == target) {
            return root;
        }
        if (root.val > target) {
            return search(root.left, target);
        } else {
            return search(root.right, target);
        }
    }
}

3. Insert node

이진 트리에 새 노드를 삽입할 때 해당 노드의 값과 삽입된 값의 크기를 비교하여 새 노드를 삽입할지 여부를 결정해야 합니다. 비교 결과에 따라 노드를 왼쪽 하위 트리 또는 오른쪽 하위 트리로 이동합니다. 다음은 샘플 코드입니다.

public class TreeInsert {
    public TreeNode insert(TreeNode root, int target) {
        if (root == null) {
            return new TreeNode(target);
        }
        if (root.val > target) {
            root.left = insert(root.left, target);
        } else if (root.val < target) {
            root.right = insert(root.right, target);
        }
        return root;
    }
}

4. 노드 삭제

노드 삭제는 비교적 복잡한 작업이므로 여러 상황에서 논의해야 합니다. 노드 A가 삭제된다고 가정해 보겠습니다. 이는 다음 세 가지 상황으로 나눌 수 있습니다.

• A는 리프 노드이며 직접 삭제할 수 있습니다.
• A에는 자식 노드가 하나만 있습니다. 자식 노드를 해당 위치로 바꾸면 됩니다.
• A에는 두 개의 하위 노드가 있습니다. 오른쪽 하위 트리에서 가장 작은 노드 B를 찾아 A를 B의 값으로 바꾼 다음 B를 삭제해야 합니다.

다음은 샘플 코드입니다.

public class TreeDelete {
    public TreeNode delete(TreeNode root, int target) {
        if (root == null) {
            return null;
        }
        if (root.val > target) {
            root.left = delete(root.left, target);
        } else if (root.val < target) {
            root.right = delete(root.right, target);
        } else {
            if (root.left == null && root.right == null) {
                return null;
            } else if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            } else {
                TreeNode min = findMin(root.right);
                root.val = min.val;
                root.right = delete(root.right, min.val);
            }
        }
        return root;
    }

    private TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

특정 적용 사례

이진 트리는 k번째 요소 찾기, 가장 작은 k 요소 찾기, 이진 트리의 깊이 찾기 등과 같은 몇 가지 일반적인 데이터 구조 문제를 해결할 수 있습니다. .

다음은 구체적인 적용 사례입니다.

1. k번째 요소 찾기

이진 트리의 순차 순회 결과는 순서가 지정되므로 순차 순회를 사용하여 k번째 요소를 찾을 수 있습니다. . 다음은 샘플 코드입니다.

public class TreeFindKth {
    private int cnt = 0;

    public int kthSmallest(TreeNode root, int k) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        int left = kthSmallest(root.left, k);
        if (left != Integer.MAX_VALUE) {
            return left;
        }
        cnt++;
        if (cnt == k) {
            return root.val;
        }
        return kthSmallest(root.right, k);
    }
}

2. 가장 작은 k 요소 찾기

이진 트리에서 가장 작은 k 요소를 찾으려면 순차 순회를 사용할 수도 있습니다. 첫 번째 k 요소만 가져오면 됩니다. 다음은 샘플 코드입니다.

public class TreeFindMinK {
    public List<Integer> kSmallest(TreeNode root, int k) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            result.add(current.val);
            if (result.size() == k) {
                return result;
            }
            current = current.right;
        }
        return result;
    }
}

3. 이진 트리의 깊이 찾기

재귀를 사용하여 이진 트리의 깊이를 찾을 수 있습니다. 다음은 샘플 코드입니다.

public class TreeDepth {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

Summary

이 글에서는 Java의 바이너리 트리 구현과 일부 특정 응용 사례를 소개합니다. 이진 트리는 대용량 데이터를 처리할 때 자주 사용되는 매우 효율적인 데이터 구조입니다. 실제 적용에서는 더 나은 성능을 얻기 위해 특정 문제의 특성에 따라 다양한 구현 방법을 선택할 수 있습니다.

위 내용은 Java 바이너리 트리 구현 및 구체적인 적용 사례에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!