khon98

이진 트리

- 이진 트리는 포인터를 이용하여 구현하면 효과적인 데이터 관리가 가능

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int data;
    struct Node *leftChild;
    struct Node *rightChild;
} Node;

Node* initNode(int data, Node* leftChid, Node* rightChild) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->leftChild = leftChid;
    node->rightChild = rightChild;
    return node;
}

이진 트리 순회

- 이진 트리에 담긴 데이터를 하나씩 방문하는 방법으로는 대표적으로 세 가지가 있음

1. 전위 순회

- 자기 자신을 출력

- 왼쪽 자식을 방문

- 오른쪽 자식을 방문

void preorder(Node* root) {
    if (root) {
        printf("%d ", root->data);
        preorder(root->leftChild);
        preorder(root->rightChild);
    }
}

2. 중위 순회

- 왼쪽 자식을 방문

- 자기 자신을 출력

- 오른쪽 자식을 방문

void inorder(Node* root) {
    if (root) {
        preorder(root->leftChild);
        printf("%d ", root->data);
        preorder(root->rightChild);
    }
}

3. 후위 순회

- 왼쪽 자식을 방문

- 오른쪽 자식을 방문

- 자기 자신을 출력

void postorder(Node* root) {
    if (root) {
        preorder(root->leftChild);
        preorder(root->rightChild);
        printf("%d ", root->data);
    }
}

* 이진 트리 사용해보기

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int data;
    struct Node *leftChild;
    struct Node *rightChild;
} Node;

Node* initNode(int data, Node* leftChid, Node* rightChild) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->leftChild = leftChid;
    node->rightChild = rightChild;
    return node;
}

void preorder(Node* root) {
    if (root) {
        printf("%d ", root->data);
        preorder(root->leftChild);
        preorder(root->rightChild);
    }
}

void inorder(Node* root) {
    if (root) {
        preorder(root->leftChild);
        printf("%d ", root->data);
        preorder(root->rightChild);
    }
}

void postorder(Node* root) {
    if (root) {
        preorder(root->leftChild);
        preorder(root->rightChild);
        printf("%d ", root->data);
    }
}

int main(void) {
    Node* n7 = initNode(50, NULL, NULL);
    Node* n6 = initNode(37, NULL, NULL);
    Node* n5 = initNode(23, NULL, NULL);
    Node* n4 = initNode(5, NULL, NULL);
    Node* n3 = initNode(48, n6, n7);
    Node* n2 = initNode(17, n4, n5);
    Node* n1 = initNode(30, n2, n3);
    preorder(n1);
    printf("\n");
    inorder(n1);
    printf("\n");
    postorder(n1);
    system("pause");
    return 0;
}

트리

- 나무의 형태를 뒤집은 것과 같은 형태의 자료 구조

- 길이란 출발 노드에서 목적지 노드까지 거쳐야 하는 가짓수를 의미

- 깊이란 루트 노드에서 특정 노드까지의 길이를 의미

- 트리의 높이란 루트 노드에서 가장 깊은 노드까지의 길이

이진 트리

- 최대 2개의 자식을 가질 수 있는 트리

포화 이진 트리

- 리프 노드를 제외한 모든 노드가 두 자식을 가지고 있는 트리

완전 이진 트리

- 모든 노드들이 왼쪽 자식부터 차근차근 채워진 노드

높이 균형 트리

- 왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1 이상 차이 나지 않는 트리

- 이진 트리는 많은 양의 노드를 낮은 높이에서 관리할 수 있다는 점에서 데이터 활용의 효율성이 높아짐

- 데이터 저장, 탐색 등의 다양한 목적에서 사용할 수 있음