C# 자료구조 트리(Tree)에 대해 알아보자

트리란?

• 트리는 비선형 자료구조이다. 비선형 자료구조란 배열, 리스트와 같이 인덱스(0,1,2,...)가 순서대로 나열된 선형 자료구조의 반대라고 생각하면 된다.
• 계층모델이다.
• 노드(node)들의 집합으로 구성되어 있다. 노드란 데이터를 일컫는다.
• 각 노드는 하나의 부모 노드(루트 노드)와 여러 개의 자식 노드를 가질 수 있다.
• 트리는 하나의 루트 노드에서 간선을 통해 다양한 노드를 방문, 탐색할 수 있는 구조를 가진다.

<출처: https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FcTWXmb%2Fbtro6bw9NVX%2FQlLNvnnxI7toaTGWHxz3B1%2Fimg.png>

---

이진 트리(Binary Tree)

<출처: https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fbkguql%2Fbtro9HvnEuD%2FYHIjSpakUgVGoOjJWzXWuk%2Fimg.png>

 

• 컴퓨터에서 사용되는 데이터 구조의 하나로, 루트가 있는 트리 구조에서 어떤 노드의 자식의 수가 최대 2개를 넘지 않는 트리를 말한다.
• 이진 트리의 순회: 이진 트리의 모든 노드를 특정한 순서대로 한 번씩 방문하는 것이다.

1. 전위순회(Pre-order)

-루트 노드 - 왼쪽 서브 트리 전위 순회 - 오른쪽 서브트리 전위 순회.

-위 그림에서 전위순회를 하면 1-2-4-5-3-6-7 순으로 방문.

-루트에서 시작하여 트리를 구조적으로 탐색하는데 유용.

 

2. 중위순회(In-order)

-왼쪽 서브 트리 중위순회 - 루트 노드  - 오른쪽 서브트리 중위순회

-위 그림에서 중위순회를 하면 4-2-5-1-6-3-7 순으로 방문.

-이진 탐색 트리에서 노드들을 오름차순으로 방문하기 위해 주로 사용.

 

3. 후위순회(Post-order)

-왼쪽 서브트리 후위순회 - 오른쪽 서브트리 후위순회 - 루트 노드

-위 그림에서 후위순회를 하면 4-5-2-6-7-3-1 순으로 방문.

-루트 노드의 자식 노드들을 모두 방문한 후에 루트 노드를 처리하는데 사용. 트리의 삭제 연산 등에서 사용 가능.

---

트리 구현

• 트리는 라이브러리에서 제공되지 않기 때문에 직접 구조를 구현해야 한다.
• 다음은 위 그림의 이진 트리를 재귀함수를 사용하여 구조를 만들어주고,  전위, 중위, 후위 순회를 구현하는 코드이다.

public class TreeNode
    {
        public int Data;
        public TreeNode Left;
        public TreeNode Right;

        public TreeNode(int data)
        {
        	Data = data;
            Left = null;
            Right = null;
        }
    }
    void Start()
    {
        // 리스트를 사용하여 이진 트리 생성
        List<int> dataList = new List<int> { 1, 2, 3, 4, 5, 6, 7 };
        TreeNode root = BinaryTree(dataList, 0);

        Debug.Log("전위 순회:");
        PreOrderTraversal(root);

        Debug.Log("중위 순회:");
        InOrderTraversal(root);

        Debug.Log("후위 순회:");
        PostOrderTraversal(root);
    }

    // 리스트의 데이터를 트리 구조로 변환.
    public TreeNode BinaryTree(List<int> dataList, int index)
    {
        if (index >= dataList.Count)
            return null;

        TreeNode node = new TreeNode(dataList[index]);

        node.Left = BinaryTree(dataList, 2 * index + 1);
        node.Right = BinaryTree(dataList, 2 * index + 2); 

        return node;
    }

    // 전위 순회
    public void PreOrderTraversal(TreeNode root)
    {
        if (root != null)
        {
            Debug.Log(root.Data);
            PreOrderTraversal(root.Left);
            PreOrderTraversal(root.Right);
        }
    }

    // 중위 순회
    public void InOrderTraversal(TreeNode root)
    {
        if (root != null)
        {
            InOrderTraversal(root.Left);
            Debug.Log(root.Data);
            InOrderTraversal(root.Right);
        }
    }

    // 후위 순회
    public void PostOrderTraversal(TreeNode root)
    {
        if (root != null)
        {
            PostOrderTraversal(root.Left);
            PostOrderTraversal(root.Right);
            Debug.Log(root.Data);
        }
    }

---