[알고리즘] 트리2 - 이진 트리의 순회

#1 이진트리의 순회

이진트리의 순회 개념

순회(Traversal)란 모든 원소를 하나라도 빠트리거나 중복하지 않고 처리하는 연산을 의미한다.

리스트, 스택, 큐 등과 같은 선형 자료구조는 원소를 1:1 관계로 구성하기에 순회 연산이 필요가 없지만 이진트리는 1:2의 비선형 계층 구조이기에 현재 노드를 처리한 뒤에 왼쪽 노드, 오른쪽 노드 둘 중 어떤 노드를 처리할지 결정하는 순회 연산이 필요하다.

 

순회연산

작업 D: 현재 노드를 방문하여 처리. 작업 L: 현재 노드의 왼쪽 서브 트리로 이동. 작업 R: 현재 노드의 오른쪽 서브 트리로 이동.

이 3가지의 작업의 수행 순서에 따라 전위 순회, 중위 순회, 후위 순회로 나눈다.

 

전위 순회

전위 순회(Preorder Traversal)는 D -> L -> R 순서로, 현재 노드를 방문하여 처리하는 작업 D를 가장 먼저 수행한 뒤 왼쪽 서브트리와 오른쪽 서브 트리로의 재귀적 호출을 반복한다.

작업 D: 현재 노드를 방문하여 처리. 작업 L: 현재 노드의 왼쪽 서브 트리로 이동. 작업 R: 현재 노드의 오른쪽 서브 트리로 이동.

중위 순회

중위 순회(Preorder Traversal)는 L -> D -> R순서로, 현재 노드를 방문하여 처리하는 작업 D를 작업 L과 작업 R의 중간에 수행한다.

작업 L: 현재 노드의 왼쪽 서브 트리로 이동. 작업 D: 현재 노드를 방문하여 처리. 작업 R: 현재 노드의 오른쪽 서브 트리로 이동.

 

후위 순회

중위 순회(Preorder Traversal)는 L -> R -> D순서로, 현재 노드를 방문하여 처리하는 작업 D를 가장 나중에 수행한다.

작업 L: 현재 노드의 왼쪽 서브 트리로 이동. 작업 R: 현재 노드의 오른쪽 서브 트리로 이동. 작업 D: 현재 노드를 방문하여 처리.

 

이진 트리 순회의 구현

수식 이진 트리 순회 프로그램을 구현해 보았다. 전위 중위 후위를 출력한다.

//
//  ex7_1.c
//  Algorithm
//
//  Created by 권순욱 on 2023/09/11
//
#pragma once
#include <stdio.h>
#include <stdlib.h>
typedef char element; // 형 재정의, element는 문자형

typedef struct treeNode { // 연결 자료구조로 구성하기 위한 트리의 노드 정의
    element data;
    struct treeNode* left;
    struct treeNode* right;
} treeNode;

// data를 루트 노드로 하여 왼쪽 서브 트리와 오른쪽 서브 트리를 연결하는 연산
treeNode* makeRootNode(element data, treeNode* leftNode, treeNode* rightNode) {
    treeNode* root = (treeNode*)malloc(sizeof(treeNode));
    root->data = data;
    root->left = leftNode;
    root->right = rightNode;
    return root;
}

// 이진 트리에 대한 전위 순회 연산
void Preorder(treeNode* root) {
    if (root) {
        printf("%c", root->data); // 현재 노드의 데이터 출력 (작업 D)
        Preorder(root->left);     // 왼쪽 서브 트리를 전위 순회 (작업 L)
        Preorder(root->right);    // 오른쪽 서브 트리를 전위 순회 (작업 R)
    }
}

// 이진 트리에 대한 중위 순회 연산
void Inorder(treeNode* root) {
    if (root) {
        Inorder(root->left);      // 왼쪽 서브 트리를 중위 순회 (작업 L)
        printf("%c", root->data); // 현재 노드의 데이터 출력 (작업 D)
        Inorder(root->right);     // 오른쪽 서브 트리를 중위 순회 (작업 R)
    }
}

// 이진 트리에 대한 후위 순회 연산
void Postorder(treeNode* root) {
    if (root) {
        Postorder(root->left);     // 왼쪽 서브 트리를 후위 순회 (작업 L)
        Postorder(root->right);    // 오른쪽 서브 트리를 후위 순회 (작업 R)
        printf("%c", root->data);  // 현재 노드의 데이터 출력 (작업 D)
    }
}

void setNode() {
    treeNode* n9 = makeRootNode('B', NULL, NULL);
    treeNode* n8 = makeRootNode('A', NULL, NULL);
    treeNode* n7 = makeRootNode('E', NULL, NULL);
    treeNode* n6 = makeRootNode('D', NULL, NULL);
    treeNode* n5 = makeRootNode('C', NULL, NULL);
    treeNode* n4 = makeRootNode('/', n8, n9);
    treeNode* n3 = makeRootNode('/', n6, n7);
    treeNode* n2 = makeRootNode('*', n4, n5);
    treeNode* n1 = makeRootNode('-', n2, n3);
    
    printf("\n preorder : ");
    Preorder(n1); // 전위 순회 출력
    
    printf("\n intorder : ");
    Inorder(n1);  // 중위 순회 출력
    
    printf("\n postorder : ");
    Postorder(n1); // 후위 순회 출력
}

void setNode1() {
    treeNode* n7 = makeRootNode('D', NULL, NULL);
    treeNode* n6 = makeRootNode('C', NULL, NULL);
    treeNode* n5 = makeRootNode('B', NULL, NULL);
    treeNode* n4 = makeRootNode('A', NULL, NULL);
    treeNode* n3 = makeRootNode('/', n6, n7);
    treeNode* n2 = makeRootNode('*', n4, n5);
    treeNode* n1 = makeRootNode('-', n2, n3);
    
    printf("\n preorder : ");
    Preorder(n1); // 전위 순회 출력
    
    printf("\n intorder : ");
    Inorder(n1);  // 중위 순회 출력
    
    printf("\n postorder : ");
    Postorder(n1); // 후위 순회 출력
}

int main() {
    // A*B-C/D 수식 이진 트리 만들기
    setNode1();
    
    getchar();
    return 0;
}
----------------------
출력 결과
 preorder : -*AB/CD
 intorder : A*B-C/D
 postorder : AB*CD/-

2023.11.03 - [알고리즘] - [알고리즘] 트리1

[알고리즘] 트리1