🎄트리 순회

---

트리의 모든 노드들을 방문하는 과정을 트리 순회라고 한다.
선형 자료 구조(연결 리스트, 스택, 큐 등)는 순차적으로 요소에 접근하지만 트리 자료구조는 다른 방식을 사용해야 한다.

일반적으로 트리 순회에는 다음과 같은 방법들이 있다.

• 전위 순회 (Preorder) : ROOT-L-R
• 중위 순회 (Inorder) : L-ROOT-R
• 후위 순회 (Postorder) : L-R-ROOT

이러한 순회는 보통 재귀로 쉽게 구현할 수 있다.

1️⃣ 전위 순회 Preorder

---

전위 순회는 깊이 우선 순회(DFT, Depth-First Traversal)라고도 한다.

트리를 복사하거나, 전위 표기법을 구하는데 주로 사용된다.
트리를 복사할 때 전위 순회를 사용하는 이유는 트리를 생성할 때 자식 노드보다 부모 노드가 먼저 생성되어야 하기 때문이다.

전위 순회는 다음과 같은 방법으로 진행한다.

1. Root 노드를 방문한다.

2. 왼쪽 서브 트리를 전위 순회한다.

3. 오른쪽 서브 트리를 전위 순회한다.

   

   전위 순회 결과 : A→B→D→E→C→F→G

구현

struct node {
  char data;
  struct node *left;
  struct node *right;
} Node;

void printPreorder (Node *root) {
  // 노드가 없다면 종료한다.
  if (root == NULL)
    return;

  // root data를 출력(방문)한다.
  printf("%c ", root->data);

  // 왼쪽 서브트리로 재귀한다.
  printPreorder(root->left);

  // 오른쪽 서브트리로 재귀한다.
  printPreorder(root->right);
}

Output:

A B D E C F G

2️⃣ 중위 순회 Inorder Traversal

---

중위 순회는 왼쪽 오른쪽 대치 순서로 순회를 하기 때문에 대칭 순회(symmetric traversal)라고도 한다.

중위 순회는 이진 검색트리(BST)에서 오름차순 또는 내림차순으로 값을 가져올 때 사용된다.
내림차순으로 값을 가져오기 위해서는 역순(오른→root→왼)으로 중위 순회를 하면 된다.

중위 순회는 다음과 같은 방법으로 진행한다.

1. 왼쪽 서브 트리를 중위 순회한다.

2. Root 노드를 방문한다.

3. 오른쪽 서브 트리를 중위 순회한다.

   

   중위 순회 결과 : D→B→E→A→F→C→G

구현

struct node {
  char data;
  struct node *left;
  struct node *right;
} Node;

void printInorder (Node *root) {
  // 노드가 없다면 종료한다.
  if (root == NULL)
    return;

  // 왼쪽 서브트리로 재귀한다.
  printInorder(root->left);

  // root data를 출력(방문)한다.
  printf("%c ", root->data);

  // 오른쪽 서브트리로 재귀한다.
  printInorder(root->right);
}

Output:

D B E A F C G

3️⃣ 후위 순회 Postorder Traversal

---

후위 순회는 트리를 삭제하는데 주로 사용된다.
이유는 부모노드를 삭제하기 전에 자식 노드를 삭제하는 순으로 노드를 삭제해야 하기 때문이다.

후위 순회는 다음과 같은 방법으로 진행한다.

1. 왼쪽 서브 트리를 후위 순회한다.

2. 오른쪽 서브 트리를 후위 순회한다.

3. Root 노드를 방문한다.

   

   후위 순회 결과 : D→E→B→F→G→C→A

구현

struct node {
  char data;
  struct node *left;
  struct node *right;
} Node;

void printPostorder (Node *root) {
  // 노드가 없다면 종료한다.
  if (root == NULL)
    return;

  // 왼쪽 서브트리로 재귀한다.
  printPostorder(root->left);

  // 오른쪽 서브트리로 재귀한다.
  printPostorder(root->right);

  // root data를 출력(방문)한다.
  printf("%c ", root->data);
}

Output:

D E B F G C A

---

출처
https://yoongrammer.tistory.com/70?category=956616 yoongrammer 블로그
프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 2 - 구종만 지음
https://blog.encrypted.gg/1013?category=773649 바킹독 실전 알고리즘 이진트리