[C언어 이진 트리 알고리즘] 이진 트리 구현 및 순회 구현하기

💡 이번에는 이진 트리로 구현 및 순회 하는 법을 배워보았다.

문제

💡 이진 트리로 구현 및 순회할 수 있게 구현하시오.

당연히 없는 문제기에 대충 내가 만들었다.

해답

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

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

Node* initNode(int data, Node* leftChild, Node* rightChild) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->leftChild = leftChild;
    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) {
        inorder(root->leftChild);
        printf("%d ", root->data);
        inorder(root->rightChild);
    }
}

void postorder(Node* root) {
    if (root) {
        postorder(root->leftChild);
        postorder(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);

    return 0;
}

설명

트리란?

• 트리(Tree)란 나무의 형태를 뒤집은 것과 같은 형태의 자료 구조이다.
• 맨 위에 루트 노드가 있으며, 가지로 이어진 자식 노드, 끝 노드를 리프 노드라고 한다.
  • 같은 부모를 가진 같은 깊이의 노드를 형제 노드라고 한다.
  • 길이(Length)란 출발 노드에서 목적지 노드까지 거쳐야 하는 가짓수를 의미한다.
  • 깊이(Depth)란 루트 노드에서 특정 노드까지의 길이를 의미한다.
  • 높이(Height)란 루트 노드에서 가장 깊은 노드까지의 길이를 의미한다.

이진트리란?

• Binary Tree 라고 하며 최대 2개의 자식을 가질 수 있는 트리이다.

• 포화 이진 트리(Full Binary Tree)는 리프 노드를 제외한 모든 노드가 두 자식을 가지고 있는 트리이다.

• 완전 이진 트리(Complete Binary Tree)는 모든 노드들이 왼쪽 자식부터 차근차근 채워진 트리이다.

• 높이 균형 트리(Height Balanced Tree)는 왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1 이상 차이나지 않는 트리이다.

• 이진 트리는 많은 양의 노드를 낮은 높이에서 관리할 수 있다는 점에서 데이터 활용의 효율성이 높아진다.
• 데이터 저장, 탐색 등의 다양한 목적에서 사용할 수 있다.

Node와 Tree형태로 초기화

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

typedef struct  Node {
    int data;   // 실제로는 정수형 데이터만 들어가는 것이 아니라 많은 데이터가 들어간다.
    struct Node *leftChild;
    struct Node *rightChild;
} Node;

Node* initNode(int data, Node* leftChild, Node* rightChild) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->leftChild = leftChild;  // 왼쪽 자식 노드 초기화
    node->rightChild = rightChild;  // 오른쪽 자식 노드 초기화

    return node;
}

• 순회 함수들은 모두 아래의 이진트리를 순회하고 있다고 가정한다.

preorder 함수

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

전위 순회함수이다.

root가 NULL값이 아닐 때 자기 자신을 먼저 출력하고 재귀적으로 leftChild를 출력하고 다음으로 rightChild를 출력한다.

출력 결과는 30 17 5 23 48 37 50 이다.

여기서 내가 헷갈린 부분은 48을 출력할 때인데 내가 생각하기에는 30 17 5 23 까지만 출력되는 것으로 예상하였었다.

이론 상으로는 이해를 했으나 코드 상에서 출력 결과가 왜 저렇게 나오는지는 설명을 해주시지 않아서 좀 더 찾아봐야겠다.

트리를 출력 후에 노드 할당 해제가 된다면 말이 될 것 같다.

inorder 함수

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

중위 순회 함수이다.

전위 순회 함수처럼 백프로 이해는 하지 못하였다.

출력 결과는 5 17 23 30 37 48 50 이다.

postorder 함수

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

후위 순회 함수이다.

위의 이유로 동일하게 백프로 이해하지는 못하였다.

출력 결과는 5 23 17 37 50 48 30 이다.

main 함수

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);    // root node

    preorder(n1);  // n1이 루트이므로 순회물을 출력하기위해 n1을 넣어준다.
    printf("\\n");
    inorder(n1);
    printf("\\n");
    postorder(n1);

    return 0;
}

n7~n4 까지는 리프노드이기 때문에 자식이 없어서 NULL 값을 넣어준다.

n3~n1 까지는 자식노드가 존재하기 때문에 해당 자식의 노드를 넣어준다.

---

마치며..

이진트리를 순회하는 것이 이해가 잘 되지 않는다.

또한 이진트리를 생성할 때 무조건 오른쪽부터 생성되는 것인지도 찾아봐야 할 것 같다.

이만 포스팅은 여기서 마치지만 후에 찾아서 다시 포스팅 하겠다.