자료구조-트리 순회(전위 순회, 중위 순회, 후위 순회)

트리 개념, 이진 트리, C로 트리 구현: https://foxtrotin.tistory.com/184

 

이진 트리 순회

모든 원소를 빠뜨리거나 중복하지 않고 처리하는 연산

 

이진 트리의 순회를 위한 세부 작업

1. 현재 노드를 방문하여 처리

2. 현재 노드의 왼쪽 서브 트리로 이동

3. 현재 노드의 오른쪽 서브 트리로 이동

 

순회 종류

1. 전위 순회

2. 중위 순회

3. 후위 순회

 

1. 전위 순회

작업 순서: 현재 노드->왼쪽->오른쪽

이런 트리가 있다면 순회 경로는

A-B-D-H-E-I-J-C-F-G-K

 

수식에 대한 전위 순회

A*B-C/D 라는 수식을 전위 순회로 트리를 만들면 위와 같다

순회 경로: -*AB/CD

-를 킵해두고 A*B 계산, C/D 계산. 두 값으로 -계산

 

2. 중위 순회

작업 순서: 왼쪽->현재 노드->오른쪽

이런 트리가 있다면

순회 경로는 H-D-B-I-E-J-A-F-C-G-K

 

실제 코드 상의 탐색으로는 위의 사진과 같다

중위 순회라고 H부터 시작하는 게 아니라, 똑같이 A부터 시작한다

하지만 중위 순회에서는 만약 자기 자신한테 왼쪽 노드가 있다면 자기 처리를 미루고 왼쪽부터 이동한다

즉, 처음에 A->B->D->H 순으로 쭉 내려와서 H를 출력, D와 B 출력

E가 있으므로 E로 다시 내려가지만 E는 왼쪽 자식이 있으니까 I부터 출력, E출력, J출력

이런 식으로 진행된다

 

수식에 대한 중위 순회

A*B-C/D 라는 수식을 중위 순회로 트리를 만들면 위와 같다

순회 경로: A*B-C/D

 

3. 후위 순회

작업 순서: 왼쪽->오른쪽->현재 노드

이런 트리가 있다면

순회 경로는 H-D-I-J-E->B->F->K->G->C->A

 

수식에 대한 후위 순회

A*B-C/D 라는 수식을 중위 순회로 트리를 만들면 위와 같다

순회 경로: AB*CD/-

 

 

코드 구현

1. 전위 순회

/* 이진트리에서 전위 순회 과정 출력 */
void printPreorder(NODE* node)
{
     if (node == NULL)
          return;
  
     /* 출력 */
     printf("%d ", node->data);  
  
     /* 왼쪽 서브 트리로 */
     printPreorder(node->left);  
  
     /* 오른쪽 서브 트리로 */
     printPreorder(node->right);
}  

 

2. 중위 순회

/* 이진트리에서 중위 순회 과정 출력 */
void printInorder(NODE* node)
{
     if (node == NULL)
          return;
  
     /* 왼쪽 서브 트리로 */
     printInorder(node->left);
  
     /* 출력 */
     printf("%d ", node->data);  
  
     /* 오른쪽 서브 트리로 */
     printInorder(node->right);
}

 

3. 후위 순회

/* 이진트리에서 후위 순회 과정 출력 */
void printPostorder(NODE* node)
{
	 // NULL이면 반환
     if (node == NULL)
        return;
  
     // 왼쪽 서브 트리로
     printPostorder(node->left);
  
     // 오른쪽 서브 트리로
     printPostorder(node->right);
  
     // 출력
     printf("%d ", node->data);
}

 

저번 글의 트리와 합친 전체 코드

저번 글: https://foxtrotin.tistory.com/184

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

typedef struct node //구조체 정의
{
    int data;
    struct node *left;
    struct node *right;
}NODE;
  
/* newNode(): 노드에 메모리 할당하고 초기화*/
NODE* newNode(int data)
{
  //노드에 메모리 할당 
  NODE* node = (NODE*)malloc(sizeof(NODE));
  
  //데이터 넣음
  node->data = data;
  
  // 왼쪽, 오른쪽 노드를 NULL로 초기화
  node->left = NULL;
  node->right = NULL;
  return(node);
}

/* 이진트리에서 전위 순회 과정 출력 */
void printPreorder(NODE* node)
{
     if (node == NULL)
          return;
    
     /* 출력 */
     printf("%d ", node->data);  
  
     /* 왼쪽 서브 트리로 */
     printPreorder(node->left);  
  
     /* 오른쪽 서브 트리로 */
     printPreorder(node->right);
}  

/* 이진트리에서 중위 순회 과정 출력 */
void printInorder(NODE* node)
{
     if (node == NULL)
          return;
  
     /* 왼쪽 서브 트리로 */
     printInorder(node->left);
  
     /* 출력 */
     printf("%d ", node->data);  
  
     /* 오른쪽 서브 트리로 */
     printInorder(node->right);
}

/* 이진트리에서 후위 순회 과정 출력 */
void printPostorder(NODE* node)
{
	 // NULL이면 반환
     if (node == NULL)
        return;
  
     // 왼쪽 서브 트리로
     printPostorder(node->left);
  
     // 오른쪽 서브 트리로
     printPostorder(node->right);
  
     // 출력
     printf("%d ", node->data);
}
  
int main()
{
  /*루트 노드를 만든다*/
  NODE *root = newNode(1);  
  /* 루트 노드를 만든 상태
  
        1
      /   \
     NULL  NULL  
  */
    
  
  root->left        = newNode(2);
  root->right       = newNode(3);
  /* 루트 노드1에 왼쪽, 오른쪽에 각각 2, 3이라는 자식 노드 추가한 상태
           1
         /   \
        2      3
     /    \    /  \
    NULL NULL NULL NULL
  */
  
  
  root->left->left  = newNode(4);
  /* 2의 왼쪽 자식으로 4를 추가한 상태
           1
       /       \
      2          3
    /   \       /  \
   4    NULL  NULL  NULL
  /  \
NULL NULL
*/
  
  printf("\n전위 순회: ");
  printPreorder(root);
  printf("\n중위 순회: ");
  printInorder(root);
  printf("\n후위 순회: ");
  printPostorder(root);
  
  getchar();
  return 0;
}

 

 

 

+추가 내용

후위순회의 예시: 컴퓨터 폴더 구조에서 전체 용량 계산하기

왼쪽 전체 서브 트리 용량+오른쪽 전체 서브 트리 용량이 내 캄퓨터 용량이니까 후위 순회로 더해야 한다

 

스레드 이진 트리

재귀호출 없이 순회할 수 있도록 수정한 이진 트리

 

재귀호출 방식-알고리즘이나 함수 구현은 간단하지만, 수행 성능 측면에서는 시스템 스택을 사용하면서 호출과 복귀를 관리해야 하고 이진 트리의 하위 레벨로 내려갈수록 재귀호출 깊이가 깊어지므로 비효율적이다

void printPreorder(NODE* node) {
     if (node == NULL)
          return;

     printf("%d ", node->data);  

     printPreorder(node->left); //이 부분
     printPreorder(node->right); //이 부분
}  

 

스레드: 원래 이진 트리에서 자식 노드가 없는 경우 링크 필드에 널 포인터를 넣는데, 널값대신 순회 순서상의 다른 노드를 가리키도록 설정. 이런 링크 필드를 스레드라 함

 

정의

-이진 트리 노드 구조에 isThread 필드를 추가하여 정의한다

-isThread 필드는 링크 필드가 자식 노드에 대한 포인터인지 아니면 자식 노드 대신 스레드가 저장되어 있는지 구별하기 위한 태그 필드로 쓴다

-isThread가 TRUE면 자식이 아니라 다른 순회 대상을 가리킨다

 

예시

-A*B-C/D 수식의 이진 트리에서 중위 순회를 한다면, 왼쪽 스레드에는 선행자를 설정하고 오른쪽 스레드에는 후속자를 설정

-중위 순회 경로가 A → * → B → - → C → / → D이므로 B의 선행자는 ‘*’이고 B의 후속자는 ‘-’임

-B를 방문한 뒤에 원래는 *, - 2번 가지만 이제는 B에서 -로 바로 감

 

만약 선행자 필요없고 후속자 정보만 필요한 경우에는 오른쪽 링크 필드만 스레드로 사용하는 스레드 이진 트리를 사용할 수 있음