[JAVA] ⚙️ 자료구조 : Tree & Binary Search Tree 🌲 | 트리 순회 | 간단 정리 및 비교 💬

Tree & Binary Search Tree 🌲 

트리 순회(전•중•후위 순회), 이진트리 

---

Tree

🌳 트리(Tree)

• 계층적(Hierarchical) 자료 구조
• 루트(root) 노드에서 시작해서 여러 개의 자식(child) 으로 뻗어나감
• 각 노드는 0개 이상의 자식을 가질 수 있음
• 사이클(순환)이 없음

📌 트리의 기본 용어

• Root: 최상위 노드
• Leaf(리프): 자식이 없는 노드
• Depth(깊이): 루트에서 특정 노드까지의 거리
• Height(높이): 트리 전체의 깊이 (가장 깊은 리프까지)

---

🌲 트리 순회 4가지

DFS 기반 3가지 + BFS 1가지

방법	설명	순서 예시 (이진 트리 기준)
전위 순회 (Preorder)	루트 → 왼쪽 → 오른쪽	Root → Left → Right
중위 순회 (Inorder)	왼쪽 → 루트 → 오른쪽	Left → Root → Right
후위 순회 (Postorder)	왼쪽 → 오른쪽 → 루트	Left → Right → Root
레벨 순회 (Level-order, BFS)	루트부터 레벨별로 탐색	위에서 아래, 왼쪽에서 오른쪽

 

---

📌 예시 트리

        A
       / \
      B   C
     / \   \
    D   E   F

1️⃣ Preorder (전위 순회)

• A → B → D → E → C → F

2️⃣ Inorder (중위 순회)

• D → B → E → A → C → F

3️⃣ Postorder (후위 순회)

• D → E → B → F → C → A

4️⃣ Level-order (레벨 순회, BFS)

• A → B → C → D → E → F

---

✅ 정리

순회 방식	방문 순서	특징	활용
전위 Preorder	Root → Left → Right	루트를 가장 먼저 방문	트리 구조 복사, 디렉토리 구조 출력
중위 Inorder	Left → Root → Right	왼쪽-루트-오른쪽 순서	이진 탐색 트리(BST)에서 정렬된 결과
후위 Postorder	Left → Right → Root	루트를 가장 마지막에 방문	자식 노드 먼저 처리 후 부모 (삭제 연산)
레벨 Level-order (BFS)	층별 순서	큐를 이용, 층별 탐색	최단 거리 탐색, 네트워크 탐색

 

 

 

---

Binary Tree / Binary Search Tree

🌳 Binary Tree (이진 트리)

• 각 노드가 최대 2개의 자식(왼쪽, 오른쪽)을 가질 수 있는 트리 구조
• 종류:
  1. 정이진 트리(Full Binary Tree)
     → 모든 노드가 0개 또는 2개의 자식을 가짐
  2. 완전 이진 트리(Complete Binary Tree)
     → 마지막 레벨을 제외하고 꽉 차 있으며, 마지막 레벨은 왼쪽부터 채워짐 (힙에서 사용)
  3. 포화 이진 트리(Perfect Binary Tree)
     → 모든 레벨이 꽉 찬 트리
  4. 이진 탐색 트리(BST)
     → 왼쪽 < 부모 < 오른쪽 규칙을 따르는 트리

---

📌 Binary Search Tree (BST) 규칙

1. 왼쪽 서브트리에 있는 모든 노드 값 < 부모 노드 값
2. 오른쪽 서브트리에 있는 모든 노드 값 > 부모 노드 값
3. 모든 서브트리도 BST 여야 함
4. 같은 값을 가지는 노드는 일반적으로 허용하지 않음 (혹은 오른쪽에만 허용)

---

📌 예시

일반 이진 트리 (Binary Tree)

        A
       / \
      B   C
     / \
    D   E

✅ 단순히 2개의 자식까지만 허용하는 트리

---

이진 탐색 트리 (Binary Search Tree)

        8
       / \
      3   10
     / \     \
    1   6     14
       / \    /
      4   7  13

• 8의 왼쪽(3,1,6,4,7)은 모두 8보다 작음
• 8의 오른쪽(10,14,13)은 모두 8보다 큼
• 6 기준: 왼쪽(4), 오른쪽(7) → 규칙 유지

---

📊 장점과 활용

특징	설명
탐색(Search)	평균 O(log n) → 정렬된 배열보다 빠르게 탐색 가능
삽입/삭제	평균 O(log n), 규칙에 따라 왼쪽/오른쪽으로 분기
단점	한쪽으로 치우치면 O(n) (연결리스트처럼 됨) → 이를 방지하려고 균형 BST (AVL, Red-Black Tree) 사용

---

✅ 정리

• Binary Tree = 최대 2개의 자식만 가지는 트리
• BST = Binary Tree의 특수한 형태 (왼쪽 < 부모 < 오른쪽 규칙)