18. 이진 트리 순회(Traversal)란?

 

 

 

이진 트리 순회(Traversal)

 

 

개발을 하다보면 데이터가 계층 구조로 연결된 형태를 만나게 된다.

 

예를 들어 

메뉴 트리, 폴더 구조, 스킬 트리, 

AI 의사결정 구조처럼 부모-자식 관계로 이어진 데이터를 다룰 때가 많다.

 

 

트리에서 자주 하는 작업은 두 가지다.

순회(Traversal): 트리의 모든 노드를 정해진 규칙대로 한 번씩 방문
탐색(Search): 특정 값을 찾기 위한 방문 (순회 알고리즘을 이용해 탐색하기도 함)

오늘은 그중에서도 이진 트리(Binary Tree)를 기준으로, 대표적인 순회 방법을 정리해볼 예정이다.

 

 

----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

1) 이진 트리(Binary Tree)와 순회(Traversal) 란?

 

이진 트리는 각 노드가 자식을 최대 2개(Left/Right)까지 가질 수 있는 트리 구조다.

순회는 이진 트리를 어떤 순서로 방문할지에 대한 규칙이다.

 

----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

 

2) 순회(Traversal)의 4종류

 

 

 

(1) 전위 순회 (Preorder)

 

규칙

Root → Left → Right

(트리 구조 직렬화(Serialize), 복사, 프리픽스 표현 등)

 

 

 

 

(2) 중위 순회 (Inorder)

규칙

Left → Root → Right

 

이진 탐색 트리(BST)라면 중위 순회 결과가 오름차순이 된다.
(BST 정렬 출력, 정렬된 순서로 처리가 필요할 때 사용)

 

 

 

 

(3) 후위 순회 (Postorder)

 

규칙 

Left → Right → Root

(삭제/정리(메모리 해제), 수식 트리 평가, 하위부터 계산해야 하는 작업에 사용)

 

 

 

 

 

(4) 레벨 순회 (Level-order)

 

규칙

위에서 아래로, 같은 레벨을 왼쪽→오른쪽 

(BFS)

 

(Queue로 구현하며, 가까운 레벨부터 처리, 최소 깊이 찾기 등에 사용)

 

 

 

----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

3) 시간 복잡도

 

 

트리 노드를 N개라고 할 때, 

어떤 순회든 각 노드를 1번씩 방문하므로
시간 복잡도는 O(N)가 된다.

 

추가 메모리(재귀): 호출 스택 깊이만큼 O(H) (H = 트리 높이)

(균형 트리면 H≈logN, 한쪽으로 치우치면 H≈N)

 

 

 

----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

 

4) 순회 예시 코드

 

(A) 예시 트리 및 노드 정의

using System.Collections.Generic;

public class Node<T>
{
    public T Value;
    public Node<T> Left;
    public Node<T> Right;

    public Node(T value) => Value = value;
}

public static class TreeSample
{
    //         A
    //       /   \
    //      B     C
    //     / \   / \
    //    D  E  F  G
    
    public static Node<string> Build()
    {
        var A = new Node<string>("A");
        var B = new Node<string>("B");
        var C = new Node<string>("C");
        var D = new Node<string>("D");
        var E = new Node<string>("E");
        var F = new Node<string>("F");
        var G = new Node<string>("G");

        A.Left = B;  A.Right = C;
        B.Left = D;  B.Right = E;
        C.Left = F;  C.Right = G;

        return A;
    }
}

 

 

(B) (전위/중위/후위)순회 - (재귀)

using System.Collections.Generic;

public static class Traversal
{
    public static List<T> Preorder<T>(Node<T> root)   //전위
    {
        var result = new List<T>();
        void Dfs(Node<T> n)
        {
            if (n == null) return;
            result.Add(n.Value);  // Root
            Dfs(n.Left);          // Left
            Dfs(n.Right);         // Right
        }
        Dfs(root);
        return result;
    }

    public static List<T> Inorder<T>(Node<T> root)   //중위
    {
        var result = new List<T>();
        void Dfs(Node<T> n)
        {
            if (n == null) return;
            Dfs(n.Left);          // Left
            result.Add(n.Value);  // Root
            Dfs(n.Right);         // Right
        }
        Dfs(root);
        return result;
    }

    public static List<T> Postorder<T>(Node<T> root)   //후위
    {
        var result = new List<T>();
        void Dfs(Node<T> n)
        {
            if (n == null) return;
            Dfs(n.Left);          // Left
            Dfs(n.Right);         // Right
            result.Add(n.Value);  // Root
        }
        Dfs(root);
        return result;
    }
}

 

 

(C) 레벨 순회(Queue)

using System.Collections.Generic;

public static class LevelTraversal
{
    public static List<T> LevelOrder<T>(Node<T> root)
    {
        var result = new List<T>();
        if (root == null) return result;

        var q = new Queue<Node<T>>();
        q.Enqueue(root);

        while (q.Count > 0)
        {
            var cur = q.Dequeue();
            result.Add(cur.Value);

            if (cur.Left != null) q.Enqueue(cur.Left);
            if (cur.Right != null) q.Enqueue(cur.Right);
        }

        return result;
    }
}

 

 

(D) 출력 및 결과

var root = TreeSample.Build();

var pre  = Traversal.Preorder(root);     // A B D E C F G
var ino  = Traversal.Inorder(root);      // D B E A F C G
var post = Traversal.Postorder(root);    // D E B F G C A
var lvl  = LevelTraversal.LevelOrder(root); // A B C D E F G

 

 

 

----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

 

4) 오늘의 한 줄 요약

『 이진 트리 순회는 트리의 모든 노드를 방문 순서 규칙(전위/중위/후위/레벨)에 따라 한 번씩 도는 방법이다.  』