[Data Structure] #Tree

이번 시간에는 data structure중 비선형 구조인 트리에 대해 알아보겠습니다.

트리?

많은 분 들이 아실테지만 트리는 나무의 모습을 거꾸로 뒤집은 구조를 가집니다. 선형구조를 나타내는 리스트, 스택, 큐와는 달리 비선형 구조를 나타냅니다. 뭐 디렉토리 구조, 의사결정 구조같은 것을 말이죠.

루트노드, 간선, leaf노드와 같이 기본적인 개념은 따로 설명하지 않겠습니다.

제가 생각할때 트리에서 가장 중요한 점은 트리안의 트리입니다. 즉, 서브트리가 있다는 것이죠. 트리 내부에 서브트리가 구현되어있고 서브트리안에 또 다른 서브트리가 존재합니다. 이 특징을 활용하면 여러가지 연산을 구현할 수 있습니다.(검색, 삽입, 삭제 등등) 반복되는 트리구조가 있으므로 우린 순환을 활용할 수가 있죠.

아래의 구현 코드는 순환을 활용해 inorder(중위), preorder(전위), postorder(후위)을 구현한 것입니다.

구현하면서 느낀건데 확실히 순환을 활용하는 알고리즘은 참 어려운 것 같습니다. 참고할 수 있는 코드가 없었으면 매우 헤맸을 것 같네요...

코드

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

typedef struct TreeNode {
  int data;
  struct TreeNode *left;
  struct TreeNode *right;
} TreeNode;

TreeNode n1 = {1, NULL, NULL};
TreeNode n2 = {4, &n1, NULL};
TreeNode n3 = {16, NULL, NULL};
TreeNode n4 = {25, NULL, NULL};
TreeNode n5 = {20, &n3, &n4};
TreeNode n6 = {15, &n2, &n5};
TreeNode *root = &n6;

// 중위
void inorder(TreeNode *root) {
  if (root != NULL) {
    inorder(root->left);
    printf("[%d]", root->data);
    inorder(root->right);
  }
}

// 전위
void preorder(TreeNode *root) {
  if (root != NULL) {
    printf("[%d]", root->data);
    preorder(root->left);
    preorder(root->right);
  }
}

// 후위
void postorder(TreeNode *root) {
  if (root != NULL) {
    postorder(root->left);
    postorder(root->right);
    printf("[%d]", root->data);
  }
}

int main(void) {
  printf("중위 순환=");
  inorder(root);
  printf("\n");

  printf("전위 순환=");
  preorder(root);
  printf("\n");

  printf("후위 순환=");
  postorder(root);
  printf("\n");
  return 0;
}

반복을 활용해서 이를 구현할 수도 있는데 이 경우는 스택을 활용합니다. 순환을 활용한 알고리즘도 내부적으로는 스택을 활용하죠.(함수가 호출되면서 생성되는 스택)

아래는 반복을 활용해 inorder을 구현한 코드입니다.

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


typedef struct TreeNode {
  int data;
  struct TreeNode *left;
  struct TreeNode *right;
} TreeNode;

#define STACK_SIZE 100
int top = -1;
TreeNode *stack[STACK_SIZE];

void push(TreeNode *p) {
  if (top < STACK_SIZE - 1) {
    stack[++top] = p;
  }
}

TreeNode* pop() {
  TreeNode *p = NULL;
  if (top > -1) {
    p = stack[top--];
  }
  return p;
}

void inorder_iter(TreeNode *root) {
  while(1) {
    for(; root; root = root->left) {
      push(root);
    }
    root = pop();
    if (!root) break;
    printf("[%d]", root->data);
    root = root->right;
  }
}

TreeNode n1 = {1, NULL, NULL};
TreeNode n2 = {4, &n1, NULL};
TreeNode n3 = {16, NULL, NULL};
TreeNode n4 = {25, NULL, NULL};
TreeNode n5 = {20, &n3, &n4};
TreeNode n6 = {15, &n2, &n5};
TreeNode *root = &n6;


int main(void) {
  printf("중위순환=");
  inorder_iter(root);
  printf("\n");
  return 0;
}