트리 (Tree)

출처 : https://itwiki.kr/w/%ED%8A%B8%EB%A6%AC

비선형 자료구조로, 계층적인 관계를 나타내는 데 사용

 

일반 트리(General Tree)

루트 노드에서 여러 개의 자식 노드를 가질 수 있는 트리 구조
각 노드는 부모와 자식 노드를 가리키는 포인터(링크)

package datastructure.nonlinear;

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

class TreeNode {
    int data;
    List<TreeNode> children;

    TreeNode(int data) {
        this.data = data;
        children = new ArrayList<>();
    }
}

public class GeneralTreeTest {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode child1 = new TreeNode(2);
        TreeNode child2 = new TreeNode(3);

//        System.out.println(root.children.get(0));
        root.children.add(child1);
        System.out.println(root.children.get(0));
        root.children.add(child2);
        System.out.println(root.children.get(1));
        TreeNode grandchild1 = new TreeNode(4);
        child1.children.add(grandchild1);
        System.out.println(child1.children.get(0));

        // 트리 탐색 및 조작
    }
}

 

이진 트리(Binary Tree)

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리
주로 검색 알고리즘, 정렬 알고리즘 등에 활용

 

• 일반적인 이진 트리 (Binary Tree)

출처 : https://velog.io/@dlgosla/CS-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC-Binary-Tree-vzdhb2sp

• 이진 탐색 트리 (Binary Search Tree, BST)

출처 : https://velog.io/@dlgosla/CS-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC-Binary-Tree-vzdhb2sp

• 높이 균형 이진 탐색 트리 (Adelson-Velsky and Landis, AVL Tree)

출처 : https://velog.io/@dlgosla/CS-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC-Binary-Tree-vzdhb2sp

• 힙(Heap)

https://www.geeksforgeeks.org/heap-data-structure/

package datastructure.nonlinear;

//일반적인 이진 트리 (Binary Tree)
class BinaryTreeNode {
    int data;
    BinaryTreeNode left;
    BinaryTreeNode right;

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

//이진 탐색 트리 (Binary Search Tree, BST)
class BinarySearchTreeNode {
    int data;
    BinarySearchTreeNode left;
    BinarySearchTreeNode right;

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

//AVL 트리
class AVLTreeNode {
    int data;
    AVLTreeNode left;
    AVLTreeNode right;
    int height;

    AVLTreeNode(int data) {
        this.data = data;
        left = null;
        right = null;
        height = 1;
    }
}

//힙(Heap)
class MaxHeap {
    int[] heap;
    int size;

    MaxHeap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }

    // 힙 관련 연산 추가
}

public class BinaryTreeTest {
    public static void main(String[] args) {
        BinaryTreeNode root = new BinaryTreeNode(1);
        root.left = new BinaryTreeNode(2);
        root.right = new BinaryTreeNode(3);

        root.left.left = new BinaryTreeNode(4);
        root.left.right = new BinaryTreeNode(5);

        // 이진 트리 탐색 및 조작
    }
}