μ΄μ§ νΈλ¦¬ νμ 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
μνμ λ§λ κ²°κ³Όκ° μΆλ ₯λ©λλ€.
'Algorithm > μ΄λ‘ ' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[μκ³ λ¦¬μ¦] lower_bound, upper_bound (0) | 2022.03.14 |
---|---|
ν¬ν¬μΈν° μκ³ λ¦¬μ¦ (0) | 2022.03.09 |
μ ν, λ²λΈ, μ½μ μ λ ¬ (0) | 2022.03.09 |
[μκ³ λ¦¬μ¦] 8μ κ°μ ꡬνκΈ° (1~10μ΅) (0) | 2022.03.09 |
Trie(νΈλΌμ΄) μκ³ λ¦¬μ¦ (0) | 2022.03.08 |