자료구조 - 트리(Tree)에 대해 알아보자(w. 순회(Traversal)방법)

 

트리(Tree)

계층적 관계를 나타내는 비선형 자료구조입니다.

이렇게 설명하면 이해가 안 갈 텐데,

 

요소들이 연결된 모습이

마치 나무를 거꾸로 뒤집어 놓은 모양과 비슷해서 트리라고 붙여졌다고 합니다.

 

 

 

트리의 구성 요소 

 

노드(Node):

트리를 구성하는 각각의 요소

 

간선(Edge):

노드와 노드를 연결하는 선

 

루트(Root):

트리의 최상위 노드

 

부모 노드(Parent Node):

특정 노드의 상위 노드

 

자식 노드(Child Node):

특정 노드의 하위 노드

 

리프 노드(Leaf Node):

자식이 없는 말단 노드

 

레벨(Level):

루트로부터의 깊이

 

높이(Height):

트리의 최대 레벨

 

 

 

트리의 주요 특징

 

순환구조(Cycle)가 없다.

모든 노드는 서로 연결되어 있다.

계층적 구조를 표현하기에 적합하다.

N개의 노드를 가진 트리는 항상 N-1개의 간선을 가진다.

 

 

트리의 순회

순회(Traversal)는 트리의 모든 노드를 체계적으로 방문하는 과정으로

4가지 방법이 존재합니다.

 

 

전위 순회(Preorder Traversal)

루트 → 왼쪽 서브트리 → 오른쪽 서브트리 순서로 방문

방문 순서: (Root, Left, Right)

 

중위 순회(Inorder Traversal)

왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순서로 방문

방문 순서: (Left, Root, Right)

 

후위 순회(Postorder Traversal)

왼쪽 서브트리 → 오른쪽 서브트리 → 루트 순서로 방문

방문 순서: (Left, Right, Root)

 

레벨 순서 순회(Level-order Traversal)

트리의 각 레벨을 왼쪽에서 오른쪽으로 순회

 

 

예시 코드

 

public class TreeNode
{
    public int Value { get; set; }
    public TreeNode Left { get; set; }
    public TreeNode Right { get; set; }

    public TreeNode(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

public class TreeTraversal
{
    // 전위 순회: Root -> Left -> Right
    public void PreOrder(TreeNode root)
    {
        if (root != null)
        {
            Console.Write($"{root.Value} "); // Root
            PreOrder(root.Left);            // Left
            PreOrder(root.Right);           // Right
        }
    }

    // 중위 순회: Left -> Root -> Right
    public void InOrder(TreeNode root)
    {
        if (root != null)
        {
            InOrder(root.Left);             // Left
            Console.Write($"{root.Value} "); // Root
            InOrder(root.Right);            // Right
        }
    }

    // 후위 순회: Left -> Right -> Root
    public void PostOrder(TreeNode root)
    {
        if (root != null)
        {
            PostOrder(root.Left);           // Left
            PostOrder(root.Right);          // Right
            Console.Write($"{root.Value} "); // Root
        }
    }

    // 레벨 순서 순회
    public void LevelOrder(TreeNode root)
    {
        if (root == null) return;

        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);

        while (queue.Count > 0)
        {
            TreeNode node = queue.Dequeue();
            Console.Write($"{node.Value} ");

            if (node.Left != null)
                queue.Enqueue(node.Left);
            if (node.Right != null)
                queue.Enqueue(node.Right);
        }
    }
}

 

 

 

마무리  

 

오늘은 간단하게 트리(Tree)의 개념과 순회에 대해 알아보았습니다.