트리

  • 트리는 나무의 형태를 뒤집은 것과 같은 형태의 자료구조 이다.
  • 트리의 최상단노드를 루트노드라고 한다.
  • 노드들은 가지로 연결된다.
  • 트리에서 가장 끝 노드는 리프노드라고 한다.
  • 트리의 깊이는 루트 노드에서 특정 노드까지의 길이를 의미한다.

image.png

image.png

image.png

이진트리

이진트리는 최대 2개의 자식을 가질 수 있는 트리이다. 포화 이진 트리(Full Binary Tree)는 리프 노드를 제외한 모든 노드가 두 자식을 가지고 있는 트리 이다.

image.png

이진트리는 포인터를 이용하여 구현하면 효과적으로 자식 노드를 관리할 수 있다.

이진트리 선언 및 초기화

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

typedef struct {
    int data;
      struct Node *leftChild;
      struct Node *rightChild;
}
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;

}

이진트리 순회

이진트리를 순회하는 방법은 대표적으로 세 가지가 있다.

전위순회

현재 위치의 노드를 출력하고, 왼쪽 자식노드를 방문하고, 오른쪽 자식노드를 방문하는 방식으로 수회를 한다.

image.png

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);
    }
}

image.png

후위순회

왼쪽 노드방문, 오른쪽 노드방문 후 자기 자신을 출력하는 순회방식이다.

void postorder(Node* root) {
        if(root) {

        postorder(root->leftChild);
        postorder(root->rightChild);
          printf("%d",root->data);
    }
}

image.png

전체코드

# 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() {

    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;
}