ν”„λ‘œκ·Έλž˜λ° μ–Έμ–΄/C

[자료ꡬ쑰] 트리 (2)

めけゃくけゃ ι–‹η™Ίθ€…πŸ¦Ύ 2022. 5. 26. 10:36

γ€Š 트리 》

 

[ μ΄μ§„νŠΈλ¦¬μ˜ 순회 ]

더보기
μ΄μ§„νŠΈλ¦¬ ꡬ쑰 ν‘œν˜„

 

- μ „μœ„μˆœνšŒ(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) : μ΄μ§„νŠΈλ¦¬ 기반의 탐색을 μœ„ν•œ 자료 ꡬ쑰

 β””  λͺ¨λ“  μ›μ†Œμ˜ ν‚€λŠ” μœ μΌν•œ ν‚€λ‹€(쀑볡을 ν—ˆμš©ν•˜μ§€ μ•ŠμŒ).

       λ…Έλ“œμ˜ μ™Όμͺ½  ν•˜μœ„νŠΈλ¦¬λŠ” λ…Έλ“œμ˜ 킀보닀 μž‘μ€ ν‚€κ°€ μžˆλŠ” λ…Έλ“œλ§Œ ν¬ν•¨λœλ‹€.

       λ…Έλ“œμ˜ 였λ₯Έμͺ½ ν•˜μœ„νŠΈλ¦¬λŠ” λ…Έλ“œμ˜ 킀보닀 큰 λ…Έλ“œλ§Œ ν¬ν•¨λœλ‹€.

       μ™Όμͺ½κ³Ό 였λ₯Έμͺ½ μ„œλΈŒνŠΈλ¦¬λ„ 각 이진탐색 νŠΈλ¦¬μ΄λ‹€.

       μ°Ύκ³ μž ν•˜λŠ” ν‚€ 값이 루트 λ…Έλ“œλ³΄λ‹€ μž‘μ„ 경우 μ™Όμͺ½ μ„œλΈŒνŠΈλ¦¬, 클 경우 였λ₯Έμͺ½ μ„œλΈŒνŠΈλ¦¬λ‘œ μ΄λ™ν•˜μ—¬ 탐색할 수 μžˆμ–΄ νš¨μœ¨μ μ΄λ‹€.

       μ΄μ§„ 탐색 νŠΈλ¦¬λŠ” μ€‘μœ„ μˆœν™˜μ„ ν•  경우 μ •λ ¬λœ 값을 얻을 수 μžˆλ‹€.   

이미지 좜처 : https://imgur.com/po0R4GB

 

 

 

[ μ΄μ§„νƒμƒ‰νŠΈλ¦¬ 탐색 μ—°μ‚° ]

 β‘  탐색은 트리의 루트 λ…Έλ“œμ—μ„œ μ‹œμž‘

 β‘‘ 탐색킀 κ°’κ³Ό 루트 λ…Έλ“œμ˜ ν‚€κ°’κ³Ό 비ꡐ

      - 탐색킀가 루트 λ…Έλ“œμ˜ 킀값보닀 μž‘μ„ 경우 μ™Όμͺ½ μ„œλΈŒνŠΈλ¦¬λ‘œ μž¬κ·€

      - 탐색킀가 루트 λ…Έλ“œμ˜ 킀값보닀 클 경우 였λ₯Έμͺ½ μ„œλΈŒνŠΈλ¦¬λ‘œ μž¬κ·€  

 β‘’ μΌμΉ˜ν•˜λŠ” 값을 찾을 경우 λ°˜ν™˜

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인 ν•˜λ‚˜μ˜ ν•˜μœ„ μ„œλΈŒνŠΈλ¦¬λ₯Ό κ°€μ§„ λ…Έλ“œλ₯Ό μ‚­μ œν•  경우 ─

ν‚€ 값이 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