[자료구조] 트리 (2)

프로그래밍 언어/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

저작자표시 비영리 변경금지 (새창열림)