알고리즘 study -18-

<스택 vs 큐>

스택 -> 미로 찾기 같이 발자취를 기억하는 용도로 많이 사용
"상태"의 의존관계가 생길 때 (재귀 호출에서 많이 사용)
A라는 일을 마치기 위해서 B라는 일을 먼저 끝내야 할 때

---

큐 -> A와 B가 서로 관련이 없지만 모두 하긴 해야할 때
"상태"의 의존관계가 없을 때 사용
스케쥴링!, 병렬화!

---

스택, 큐 = 선형 자료구조

• 스택과 큐에는 많은 경우, "상태" 를 저장한다!

---

<트리(Tree)>

• 노드 와 간선 으로 구성
• 부모 <-> 자식 관계 / 위로 갈수록 부모 노드
• 해당 트리에서 제일 상위 노드 = 루트

---

<트리의 재귀적 성질>

-> 트리는 그 안에 또 트리가 존재한다

• 트리안의 트리 = 서브트리

---

<트리 순회>

-> 트리 내에 어떠한 자료가 담겨있는지를 알기 위함

• 트리의 재귀적 성질을 이용해서 순회하는 방법이 가장 유명하며 중요하다!!

---

<이진트리(Binary Tree)>

-> 자식 노드가 2개 이하인 트리

• 전위순회 : Root - L - R
• 중위순회 : L - Root - R
• 후위순회 : L - R - Root

---

• 전위순회 : 1 2 4 5 3 6 7
• 중위순회 : 4 2 5 1 6 3 7
• 후위순회 : 4 5 2 6 7 3 1

---

<구현>

#include <stdio.h>

const int MAX = 100;

struct Tree{
    int left;
    int right;
};

Tree tree[MAX];

// tree[i] = 노드 i의 정보를 담고 있음
// tree[i].left = 노드 i의 왼쪽 노드 번호
// tree[i].right = 노드 i의 오른쪽 노드 번호

void preorder(int x){
  // x를 루트로 하는 서브트리를 전위순회 하여 출력하는 함수
  if(tree[x].left == -1 && tree[x].right == -1){
    printf("%d ", x);
  }
  else{
    // 루트 출력
    printf("%d ", x);
    
    if(tree[x].left != -1)
      preorder(tree[x].left);
    
    if(tree[x].right != -1)
      preorder(tree[x].right);
  }
}

void inorder(int x){
  // x를 루트로 하는 트리를 중위순회하여 출력하는 함수
  
  if(tree[x].left == -1 && tree[x].right == -1){
    printf("%d ", x);
  }
  else{ // L -> Root -> R
    
    if(tree[x].left != -1)
      inorder(tree[x].left);
    
    printf("%d ", x);
    
    if(tree[x].right != -1)
      inorder(tree[x].right);
  }
}

void postorder(int x){
  // x를 루트로 하는 트리를 후위순회하여 출력하는 함수
  
  if(tree[x].left == -1 && tree[x].right == -1){
    printf("%d ", x);
  }
  else{ // L -> R -> Root
    
    if(tree[x].left != -1)
      postorder(tree[x].left);
    
    if(tree[x].right != -1)
      postorder(tree[x].right);
      
    printf("%d ", x);
  }
  
}

int main() {
  // 이진트리 순회
  int n;
  
  scanf("%d", &n);
  
  for(int i = 0; i<n; i++){
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    
    tree[a].left = b;
    tree[a].right = c;
  }

  preorder(0);
  printf("\n");
  inorder(0);
  printf("\n");
  postorder(0);
  
  return 0;
}

---

입력
6
0 1 2
1 3 4
2 -1 5
3 -1 -1
4 -1 -1
5 -1 -1

---

출력

0 1 3 4 2 5
3 1 4 0 2 5
3 4 1 5 2 0

---