λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°

Algorithm/이둠

[μ•Œκ³ λ¦¬μ¦˜] 이진 트리 탐색

이진 트리 탐색 C++

이진 νŠΈλ¦¬μ—μ„œμ˜ μ „μœ„ 순회, μ€‘μœ„ 순회, ν›„μœ„ 순회λ₯Ό μ•Œμ•„λ΄…μ‹œλ‹€.

이진 트리

  • 트리 κ΅¬μ‘°μ΄λ―€λ‘œ, μ—¬λŸ¬ λ…Έλ“œκ°€ ν•œ λ…Έλ“œλ₯Ό 가리킬 수 μ—†λŠ” ꡬ쑰이닀.
  • λ˜ν•œ 사이클 μ—­μ‹œ μ‘΄μž¬ν•  수 μ—†λ‹€.
  • 각각의 λ…Έλ“œκ°€ μ΅œλŒ€ 두 개의 μžμ‹ λ…Έλ“œλ₯Ό 가지고 있음
  • μžμ‹ λ…Έλ“œλ₯Ό 각각 μ™Όμͺ½ μžμ‹ λ…Έλ“œ, 였λ₯Έμͺ½ μžμ‹ λ…Έλ“œλΌκ³  μΉ­ν•œλ‹€.
  • μ „μœ„ 순회, μ€‘μœ„ 순회, ν›„μœ„ 순회의 탐색을 가지고 μžˆλ‹€.
  • μ΅œμƒμœ„ 루트 λ…Έλ“œλ₯Ό 가지고 μžˆλ‹€.

μ „μœ„ 순회

μ „μœ„ 순회의 진행은 깊이 μš°μ„  μˆœνšŒλΌκ³ λ„ ν•˜λ©°, λ‹€μŒμ˜ μ„Έ 가지 μˆœμ„œλ‘œ μ§„ν–‰λœλ‹€.

  • λΆ€λͺ¨ λ…Έλ“œλ₯Ό λ°©λ¬Έν•œλ‹€.
  • μ™Όμͺ½ μžμ‹ λ…Έλ“œλ₯Ό λ°©λ¬Έν•œλ‹€.
  • 였λ₯Έμͺ½ μžμ‹ λ…Έλ“œλ₯Ό λ°©λ¬Έν•œλ‹€.

즉, λΆ€λͺ¨ λ…Έλ“œκ°€ 1, μ™Όμͺ½ μžμ‹ λ…Έλ“œκ°€ 2, 였λ₯Έμͺ½ μžμ‹ λ…Έλ“œκ°€ 3이라면 1 -> 2 -> 3의 순으둜 λ°©λ¬Έν•œλ‹€.

μ€‘μœ„ 순회

μ€‘μœ„ μˆœνšŒλŠ” λ‹€μŒμ˜ μ„Έ 가지 μˆœμ„œλ‘œ μ§„ν–‰λœλ‹€.

  • μ™Όμͺ½ μžμ‹ λ…Έλ“œλ₯Ό λ°©λ¬Έν•œλ‹€.
  • λΆ€λͺ¨ λ…Έλ“œλ₯Ό λ°©λ¬Έν•œλ‹€.
  • 였λ₯Έμͺ½ μžμ‹ λ…Έλ“œλ₯Ό λ°©λ¬Έν•œλ‹€.

즉, λΆ€λͺ¨ λ…Έλ“œκ°€ 1, μ™Όμͺ½ μžμ‹ λ…Έλ“œκ°€ 2, 였λ₯Έμͺ½ μžμ‹ λ…Έλ“œκ°€ 3이라면 2 -> 1 -> 3의 순으둜 λ°©λ¬Έν•œλ‹€.

ν›„μœ„μˆœνšŒ

ν›„μœ„ μˆœνšŒλŠ” λ‹€μŒμ˜ μ„Έ 가지 μˆœμ„œλ‘œ μ§„ν–‰λœλ‹€.

  • μ™Όμͺ½ μžμ‹ λ…Έλ“œλ₯Ό λ°©λ¬Έν•œλ‹€.
  • 였λ₯Έμͺ½ μžμ‹ λ…Έλ“œλ₯Ό λ°©λ¬Έν•œλ‹€.
  • λΆ€λͺ¨ λ…Έλ“œλ₯Ό λ°©λ¬Έν•œλ‹€.

즉, λΆ€λͺ¨ λ…Έλ“œκ°€ 1, μ™Όμͺ½ μžμ‹ λ…Έλ“œκ°€ 2, 였λ₯Έμͺ½ μžμ‹ λ…Έλ“œκ°€ 3이라면 2 -> 3 -> 1의 순으둜 λ°©λ¬Έν•œλ‹€.

κ΅¬ν˜„(C++)

μž¬κ·€λ₯Ό 톡해 κ΅¬ν˜„ν•  수 μžˆλ‹€.


μ „μœ„ μˆœνšŒλŠ” preOrderFunc, μ€‘μœ„ μˆœνšŒλŠ” inOrderFunc, ν›„μœ„ μˆœνšŒλŠ” postOrderFuncμ΄λΌλŠ” ν•¨μˆ˜λ₯Ό λ§Œλ“€μ–΄ κ΅¬ν˜„ν•΄λ΄…μ‹œλ‹€.

이진 νŠΈλ¦¬λŠ” λΆ€λͺ¨ λ…Έλ“œ λ²ˆν˜Έκ°€ n이라면 μ™Όμͺ½ μžμ‹ λ…Έλ“œλŠ” n2, 였λ₯Έμͺ½ λ…Έλ“œλŠ” n2+1둜 κ΅¬ν˜„ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

레벨 N을 μž…λ ₯ν•΄ μ£Όλ©΄ level이 N인 μ™„μ „ 이진 트리λ₯Ό λ§Œλ“€κ³ , 각 순회λ₯Ό ν•΄μ£ΌλŠ” μ†ŒμŠ€λ₯Ό λ§Œλ“€μ–΄λ΄…μ‹œλ‹€.

#include <iostream>
#include <vector>
using namespace std;
int N;
void preOrderFunc(int idx, int level) {
    if (level > N) return;
    cout << idx << ' ';
    preOrderFunc(idx * 2, level + 1);
    preOrderFunc(idx * 2+1, level + 1);
}
void inOrderFunc(int idx, int level) {
    if (level > N) return;
    inOrderFunc(idx * 2, level + 1);
    cout << idx << ' ';
    inOrderFunc(idx * 2 + 1, level + 1);
}
void postOrderFunc(int idx, int level) {
    if (level > N) return;
    postOrderFunc(idx * 2, level + 1);
    postOrderFunc(idx * 2 + 1, level + 1);
    cout << idx << ' ';
}
int main(void) {
    cin >> N;
    cout << "μ „μœ„ 순회 : ";
    preOrderFunc(1,1); 
    cout << '\n';
    cout << "μ€‘μœ„ 순회 : ";
    inOrderFunc(1,1);
    cout << '\n';
    cout << "ν›„μœ„ 순회 : ";
    postOrderFunc(1,1);
    cout << '\n';
    return 0;
}

μ „μœ„ μˆœνšŒλŠ” μžμ‹ λ…Έλ“œλ₯Ό μˆœνšŒν•˜κΈ° 전에 인덱슀 값을 좜λ ₯

μ€‘μœ„ μˆœνšŒλŠ” μ™Όμͺ½ μžμ‹ λ…Έλ“œλ₯Ό μˆœνšŒν•œ 뒀에 인덱슀 값을 좜λ ₯

ν›„μœ„ μˆœνšŒλŠ” μ™Όμͺ½ μžμ‹ λ…Έλ“œ, 였λ₯Έμͺ½ μžμ‹ λ…Έλ“œλ₯Ό μˆœνšŒν•œ 뒀에 인덱슀 값을 좜λ ₯ν•˜μ—¬ λ§Œλ“€μ—ˆμŠ΅λ‹ˆλ‹€.

3을 μž…λ ₯ν•΄λ΄…μ‹œλ‹€.

3
μ „μœ„ 순회 : 1 2 4 5 3 6 7
μ€‘μœ„ 순회 : 4 2 5 1 6 3 7
ν›„μœ„ 순회 : 4 5 2 6 7 3 1

μˆœνšŒμ— λ§žλŠ” κ²°κ³Όκ°€ 좜λ ₯λ©λ‹ˆλ‹€.