[μλ£κ΅¬μ‘°] νΈλ¦¬ (2)
γ νΈλ¦¬ γ
[ μ΄μ§νΈλ¦¬μ μν ]

- μ μμν(Preorder)
β μν μμ : λ£¨νΈ → μΌμͺ½ μλΈ νΈλ¦¬ → μ€λ₯Έμͺ½ μλΈνΈλ¦¬ μμλ‘ μν (VLR)
// C code
// μ μ μν
void preorder(TreeNode* root) {
if (root != NULL) {
printf("[%2d] ", root->data);
preorder(root->left);
preorder(root->right);
}
}

- μ€μμν(Inorder)
β μν μμ : μΌμͺ½ μλΈνΈλ¦¬ → λ£¨νΈ → μ€λ₯Έμͺ½ μλΈνΈλ¦¬ μμλ‘ μν (LVR)
// C code
// μ€μ μν
void inorder(TreeNode* root) {
if (root != NULL) {
inorder(root->left);
printf("[%2d] ", root->data);
inorder(root->right);
}
}

- νμμν(Postorder)
β μν μμ : μΌμͺ½ μλΈνΈλ¦¬ → μ€λ₯Έμͺ½ μλΈνΈλ¦¬ → λ£¨νΈ μμλ‘ μν (LRV)
// C code
// νμ μν
void postorder(TreeNode* root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
printf("[%2d] ", root->data);
}
}

μ΄μ§νΈλ¦¬μ μν | ||
μ μ μν | νμ¬ λ Έλ → μΌμͺ½ λ Έλ → μ€λ₯Έμͺ½ λ Έλ | preorder(n): if n ≠ NULL then print DATA(n); preorder(LEFT(n)); preorder(RIGHT(n)); |
μ€μ μν | μΌμͺ½ λ Έλ → νμ¬ λ Έλ → μ€λ₯Έμͺ½ λ Έλ | inorder(n): if n ≠ NULL preorder(LEFT(n)); then print DATA(n); preorder(RIGHT(n)); |
νμ μν | μΌμͺ½ λ Έλ → μ€λ₯Έμͺ½ λ Έλ → νμ¬ λ Έλ | postorder(n): if n ≠ NULL preorder(LEFT(n)); preorder(RIGHT(n)); then print DATA(n); |
[ μ΄μ§νΈλ¦¬λ₯Ό μ΄μ©ν μμ μ²λ¦¬ ]
- μμ μ²λ¦¬ : μ°μ μμ νΈλ¦¬ ννλ‘ νννκ³ , νμμνλ₯Ό μ¬μ©νμ¬ κ³μ° κ°λ₯
- λ΄λΆ λ Έλ : μ°μ°μλ‘ μ¬μ©
- 리ν λ Έλ : νΌμ°μ°μλ‘ μ¬μ©

- μ΄μ§νΈλ¦¬μ νμμνλ₯Ό νμ©ν μμ μ²λ¦¬ μμ
β β n1 κ³Ό n2λ₯Ό n3 μ°μ°μλ₯Ό κΈ°μ€μΌλ‘ μμ μ²λ¦¬ (LRV)
β‘ n4 μ n5λ₯Ό n6 μ°μ°μλ₯Ό κΈ°μ€μΌλ‘ μμ μ²λ¦¬ (LRV)
β’ β λ²κ³Ό β‘λ² κ³Όμ μ ν΅ν΄ λμΆλ νΌμ°μ°μλ₯Ό n7 μ°μ°μλ₯Ό κΈ°μ€μΌλ‘ μμ μ²λ¦¬ (LRV)

// C code
// μ΄μ§νΈλ¦¬λ₯Ό νμ©ν μμμ²λ¦¬(νμ μν)
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode* left, * right;
}TreeNode;
// λ£¨νΈ λ
Έλ λ° μλΈ νΈλ¦¬ μ μ
TreeNode n1 = { 1, NULL, NULL };
TreeNode n2 = { 4, NULL, NULL };
TreeNode n3 = { '*', &n1, &n2};
TreeNode n4 = { 16, NULL, NULL };
TreeNode n5 = { 25, NULL, NULL };
TreeNode n6 = { '+', &n4, &n5};
TreeNode n7 = { '+', &n3, &n6 };
TreeNode* root = &n7;
int evaluate(TreeNode* root) {
int cnt = 0;
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL) // 리ν λ
ΈλμΈ κ²½μ°(νΌμ°μ°μ)
return root->data;
else { // λ΄λΆ λ
ΈλμΈ κ²½μ°(μ°μ°μ)
int op1 = evaluate(root->left);
int op2 = evaluate(root->right);
printf(" %2d %c %2dλ₯Ό κ³μ°\n", op1, root->data, op2);
switch (root->data) {
case '+':
return op1 + op2;
case '-':
return op1 - op2;
case '*':
return op1 * op2;
case '/':
return op1 / op2;
}
}
return 0;
}
int main(void) {
printf("\n μμμ κ°μ %dμ
λλ€\n", evaluate(root));
return 0;
}

[ μ΄μ§νμνΈλ¦¬ ]
- μ΄μ§νμ νΈλ¦¬ (Binary Search Tree) : μ΄μ§νΈλ¦¬ κΈ°λ°μ νμμ μν μλ£ κ΅¬μ‘°
β λͺ¨λ μμμ ν€λ μ μΌν ν€λ€(μ€λ³΅μ νμ©νμ§ μμ).
λ Έλμ μΌμͺ½ νμνΈλ¦¬λ λ Έλμ ν€λ³΄λ€ μμ ν€κ° μλ λ Έλλ§ ν¬ν¨λλ€.
λ Έλμ μ€λ₯Έμͺ½ νμνΈλ¦¬λ λ Έλμ ν€λ³΄λ€ ν° λ Έλλ§ ν¬ν¨λλ€.
μΌμͺ½κ³Ό μ€λ₯Έμͺ½ μλΈνΈλ¦¬λ κ° μ΄μ§νμ νΈλ¦¬μ΄λ€.
μ°Ύκ³ μ νλ ν€ κ°μ΄ λ£¨νΈ λ Έλλ³΄λ€ μμ κ²½μ° μΌμͺ½ μλΈνΈλ¦¬, ν΄ κ²½μ° μ€λ₯Έμͺ½ μλΈνΈλ¦¬λ‘ μ΄λνμ¬ νμν μ μμ΄ ν¨μ¨μ μ΄λ€.
μ΄μ§ νμ νΈλ¦¬λ μ€μ μνμ ν κ²½μ° μ λ ¬λ κ°μ μ»μ μ μλ€.

[ μ΄μ§νμνΈλ¦¬ νμ μ°μ° ]
β νμμ νΈλ¦¬μ λ£¨νΈ λ Έλμμ μμ
β‘ νμν€ κ°κ³Ό λ£¨νΈ λ Έλμ ν€κ°κ³Ό λΉκ΅
- νμν€κ° λ£¨νΈ λ Έλμ ν€κ°λ³΄λ€ μμ κ²½μ° μΌμͺ½ μλΈνΈλ¦¬λ‘ μ¬κ·
- νμν€κ° λ£¨νΈ λ Έλμ ν€κ°λ³΄λ€ ν΄ κ²½μ° μ€λ₯Έμͺ½ μλΈνΈλ¦¬λ‘ μ¬κ·
β’ μΌμΉνλ κ°μ μ°Ύμ κ²½μ° λ°ν
TreeNode* search(TreeNode* root, element key) {
while (root != NULL) {
if (key == root->key)
return root;
else if (key < root->key)
return search(root->left, key);
else
return search(root->right, key);
}
return NULL;
}
β νμν λ Έλμ ν€κ°μ΄ 4μΈ κ²½μ° β




[ μ΄μ§νμνΈλ¦¬ μ½μ μ°μ° ]
β μ½μ ν ν€λ λ°λμ 리ν λ Έλ(λ¨λ§ λ Έλ)μ μ½μ λλ€.
β‘ μ½μ ν ν€κ°κ³Ό λ£¨νΈ ν€κ°κ³Ό λΉκ΅
- ν€ κ°μ΄ μμκ²½μ° μΌμͺ½ μλΈνΈλ¦¬λ‘ μ¬κ·
- ν€ κ°μ΄ ν΄ κ²½μ° μ€λ₯Έμͺ½ μλΈνΈλ¦¬λ‘ μ¬κ·
⒠리ν λ Έλ(λ¨λ§ λ Έλ)μ λλ¬ν κ²½μ°
- ν€ κ°μ΄ 리ν λ Έλλ³΄λ€ μμ κ²½μ° μΌμͺ½μ μ½μ
- ν€ κ°μ΄ 리ν λ Έλλ³΄λ€ ν΄ κ²½μ° μ€λ₯Έμͺ½μ μ½μ
TreeNode* new_node(element item) {
TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
TreeNode* insert_node(TreeNode* root, element key) {
// 리ν λ
Έλμ λλ¬ν κ²½μ°
if (root == NULL)
return new_node(key);
if (key < root->key)
root->left = insert_node(root->left, key);
else if (key > root->key)
root->right = insert_node(root->right, key);
return root;
}
β ν€κ°μ΄ 14μΈ λ Έλλ₯Ό μ½μ ν κ²½μ° β




[ μ΄μ§νμνΈλ¦¬ λ Έλ μμ μ°μ° ]
// μ΄μ§νμνΈλ¦¬ 맨 μΌμͺ½ λ¨λ§ λ
Έλ(νΈλ¦¬μ μ΅μκ°) νμ ν¨μ
TreeNode* min_value_node(TreeNode* root) {
TreeNode* current = root;
while (current->left != NULL)
current = current->left;
return current;
}
// μ΄μ§νμνΈλ¦¬ λ
Έλ μμ ν¨μ
TreeNode* delete_node(TreeNode* root, int key) {
if (root == NULL)
return root;
// μ λ¬λ°μ keyκ° νμ¬ λ
Έλμ ν€λ³΄λ€ μμ κ²½μ° [μΌμͺ½ μλΈ νΈλ¦¬μ μ‘΄μ¬]
if (key < root->key)
root->left = delete_node(root->left, key);
// μ λ¬λ°μ keyκ° νμ¬ λ
Έλμ ν€λ³΄λ€ ν΄ κ²½μ° [μ€λ₯Έμͺ½ μλΈ νΈλ¦¬μ μ‘΄μ¬]
else if (key > root->key)
root->right = delete_node(root->right, key);
// μμ ν λ
Έλλ₯Ό μ°Ύμ κ²½μ°
else {
TreeNode* temp = root;
// νμ¬ μμ ν λ
Έλμ νμ μλΈνΈλ¦¬κ° νλ μ΄κ±°λ μμ κ²½μ°
if (root->left == NULL) {
temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) {
temp = root->left;
free(root);
return temp;
}
// νμ¬ μμ ν λ
Έλμ νμ μλΈνΈλ¦¬κ° μ λΆ(λ λ€) μλ κ²½μ°
temp = min_value_node(root->right); // μμμ΄ λλ€ μλ κ²½μ° μ€μ νμμ κ°μ Έμ€κΈ°(μ€λ₯Έμͺ½ μλΈνΈλ¦¬μ μ΅μκ° λ
Έλ)
root->key = temp->key; // μ€μ νμμμ ν€κ°μ μ λ¬
root->right = delete_node(root->right, temp->key); // νμ¬ λ£¨νΈ λ
Έλμ μ€μ νμμ μ κ±°
}
return root;
}
[ μμ ν λ Έλκ° λ¦¬ν λ Έλ(λ¨λ§ λ Έλ)μΈ κ²½μ° ]
β ν€κ°μ΄ 4μΈ λ¦¬νλ Έλλ₯Ό μμ ν κ²½μ° β


[ μμ ν λ Έλκ° νλμ νμ μλΈνΈλ¦¬λ₯Ό κ°μ§ κ²½μ° ]
β ν€κ°μ΄ 13μΈ νλμ νμ μλΈνΈλ¦¬λ₯Ό κ°μ§ λ Έλλ₯Ό μμ ν κ²½μ° β

[ μμ ν λ Έλκ° λκ°μ νμ μλΈνΈλ¦¬λ₯Ό κ°μ§ κ²½μ° ]
β ν€κ°μ΄ 10μΈ λκ°μ νμ μλΈνΈλ¦¬λ₯Ό κ°μ§ λ Έλλ₯Ό μμ ν κ²½μ° β

[ νΈλ¦¬μ λμ΄ μ°μ° ν¨μ ]
int get_height(TreeNode* node) {
int height = 0;
if (node != NULL)
height = max(get_height(node->left), get_height(node->right)) + 1;
return height;
}
[ νΈλ¦¬μ λ Έλ κ°μ μ°μ° ν¨μ ]
int get_node_count(TreeNode* node) {
int count = 0;
if (node != NULL)
count = 1 + get_node_count(node->left) + get_node_count(node->right);
return count;
}
μ°Έκ³ λΈλ‘κ·Έ : https://yoongrammer.tistory.com/71