[자료구조&알고리즘] 트리(Tree)

 

 

1. 트리의 기본 개념

1.1 노드(Node)

트리는 노드들로 구성되어 있다. 각 노드는 데이터와 부모-자식 관계를 나타내는 링크(포인터)로 이루어져 있다.

* 노드(node) : 데이터가 저장된 부분

* 엣지(edge) : 노드와 노드 사이를 잇는 선

트리는 노드와 노드 사이를 연결하는 엣지를 이용하여 계층을 구성한다. 트리의 계층 구조를 도식적으로 표현하면 나무 형태로 나타낼 수 있으며 이때 엣지는 나뭇가지처럼 표현된다. 트리의 중심이 되는 노드를 루트 노드라고 하며, 보통 가장 맨 위에 나타낸다. 

public class TreeNode<T>
{
    public T Data { get; set; }
    public List<TreeNode<T>> Children { get; set; }

    public TreeNode(T data)
    {
        Data = data;
        Children = new List<TreeNode<T>>();
    }
}

 

1.2 트리(Tree)

트리는 루트 노드에서 시작하여 각 노드가 여러 자식 노드를 가질 수 있는 계층적인 구조를 가진다. 

public class Tree<T>
{
    public TreeNode<T> Root { get; set; }

    public Tree(T rootData)
    {
        Root = new TreeNode<T>(rootData);
    }
}

 

2. 트리 구현 및 기본 동작

2.1 트리에 노드 추가

Tree<int> tree = new Tree<int>(1);

tree.Root.Children.Add(new TreeNode<int>(2));
tree.Root.Children.Add(new TreeNode<int>(3));

tree.Root.Children[0].Children.Add(new TreeNode<int>(4));
tree.Root.Children[0].Children.Add(new TreeNode<int>(5));

 

 

2.2 트리 순회 (Traversal)

트리를 순회하는 방법에는 전위 순회(pre-order), 중위 순회(in-order), 후위 순회(post-order) 등이 있다.

2.2.1 전위 순회

현재 노드를 먼저 방문하고, 그 다음은 현재 노드의 왼쪽 하위 노드를, 마지막으로는 현재 노드의 오른쪽 하위 노드를 재귀적인 방식으로 방문한다. 

public void PreOrderTraversal(TreeNode<T> node)
{
    if (node != null)
    {
        Console.Write(node.Data + " ");
        foreach (var child in node.Children)
        {
            PreOrderTraversal(child);
        }
    }
}

 

2.2.2 중위 순회

왼쪽 노드를 먼저 방문하고, 그 다음은 현재 노드, 마지막으로 오른쪽 노드를 방문한다. 

public void InOrderTraversal(TreeNode<T> node)
{
    if (node != null)
    {
        foreach (var child in node.Children)
        {
            InOrderTraversal(child);
        }
        Console.Write(node.Data + " ");
    }
}

 

2.2.3 후위 순회

두 자식 노드를 먼저 방문한 후, 현재 노드를 방문한다. 

public void PostOrderTraversal(TreeNode<T> node)
{
    if (node != null)
    {
        foreach (var child in node.Children)
        {
            PostOrderTraversal(child);
        }
        Console.Write(node.Data + " ");
    }
}

 

 

3. 이진 트리(Binary Tree)

이진 트리는 각 노드가 최대 두 개의 자식을 가질 수 있는 트리 구조이다. 각 노드는 두 개의 서브 트리를 가지거나 왼쪽이나 오른쪽 서브 트리 중 하나가 없을 수 있다. 

 

◇ 루트 노드 (Root Node): 트리의 가장 상위에 있는 노드로, 다른 모든 노드는 이 루트 노드에서 시작하는 서브 트리의 일부이다.

◇ 부모 노드 (Parent Node): 어떤 노드의 바로 위에 있는 노드를 부모 노드라고 한다.

◇ 자식 노드 (Child Node): 어떤 노드에 연결된 하위 레벨의 노드들을 자식 노드라고 한다.

ex. 이진 트리에서 각 노드는 최대 두 개의 자식 노드를 가질 수 있다.

◇ 리프 노드 (Leaf Node): 어떤 노드에 자식이 없는 노드를 리프 노드라고 한다.

◇ 서브 트리 (Subtree): 어떤 노드와 그 자손 노드들로 이루어진 트리를 서브 트리라고 한다.

3.1. 완전 이진 트리(Complete Binary Tree)

완전 이진 트리는 모든 레벨에서 왼쪽에서 오른쪽으로 노드가 순서대로 채워진 이진 트리이다. 마지막 레벨을 제외한 모든 레벨은 노드로 완전히 채워져 있어야 한다. 만약 마지막 레벨이 완전히 채워져 있지 않다면, 노드는 왼쪽에서 오른쪽으로 순서대로 채워져야 합니다.

3.2. 완전 이진 트리의 활용 예시

완전 이진 트리의 특성은 배열을 이용하여 구현할 때 효율적으로 사용될 수 있다. 각 노드에 인덱스를 부여하면 배열에 노드를 저장하고, 부모와 자식 간의 관계를 쉽게 유지할 수 있습니다.

using System;

public class CompleteBinaryTree
{
    private int[] array;
    private int size;

    public CompleteBinaryTree(int capacity)
    {
        array = new int[capacity];
        size = 0;
    }

    // 완전 이진 트리에 노드 추가
    public void AddNode(int value)
    {
        if (size < array.Length)
        {
            array[size] = value;
            size++;
        }
        else
        {
            Console.WriteLine("트리가 가득 찼습니다.");
        }
    }

    // 완전 이진 트리 출력
    public void PrintTree()
    {
        for (int i = 0; i < size; i++)
        {
            Console.Write(array[i] + " ");
        }
        Console.WriteLine();
    }
}

public class Program
{
    public static void Main()
    {
        CompleteBinaryTree completeBinaryTree = new CompleteBinaryTree(10);

        // 완전 이진 트리에 노드 추가
        completeBinaryTree.AddNode(1);
        completeBinaryTree.AddNode(2);
        completeBinaryTree.AddNode(3);
        completeBinaryTree.AddNode(4);
        completeBinaryTree.AddNode(5);
        completeBinaryTree.AddNode(6);
        completeBinaryTree.AddNode(7);
        completeBinaryTree.AddNode(8);
        completeBinaryTree.AddNode(9);
        completeBinaryTree.AddNode(10);

        // 완전 이진 트리 출력
        Console.WriteLine("완전 이진 트리:");
        completeBinaryTree.PrintTree();
    }
}

3. 트리의 활용 예시: 이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리는 모든 노드에 대해 왼쪽 서브트리의 값이 현재 노드의 값보다 작고, 오른쪽 서브트리의 값이 현재 노드의 값보다 큰 조건을 만족하는 트리이다. 즉, 왼쪽 노드 ≤ 부모노드 ≤ 오른쪽 노드의 관계를 가진다. 

public class BinarySearchTree<T> where T : IComparable<T>
{
    public TreeNode<T> Root { get; set; }

    public void Insert(T value)
    {
        Root = InsertRec(Root, value);
    }

    private TreeNode<T> InsertRec(TreeNode<T> root, T value)
    {
        if (root == null)
        {
            return new TreeNode<T>(value);
        }

        if (value.CompareTo(root.Data) < 0)
        {
            root.Children.Add(InsertRec(root.Children[0], value));
        }
        else if (value.CompareTo(root.Data) > 0)
        {
            root.Children.Add(InsertRec(root.Children[1], value));
        }

        return root;
    }
}

 

 

4. 트리의 활용 예시: Unity에서의 활용

Unity에서 트리는 주로 게임 오브젝트의 계층 구조를 표현하는 데 사용된다. Scene 내의 게임 오브젝트들은 부모-자식 관계로 연결되어 있어 트리 구조를 이루고 있다. 이를 통해 오브젝트 간의 상속과 계층 구조를 쉽게 표현할 수 있습니다.

// Unity에서의 트리 활용 예시
public class TreeExample : MonoBehaviour
{
    void Start()
    {
        Tree<GameObject> gameObjectTree = new Tree<GameObject>(gameObject);

        // 부모-자식 관계로 게임 오브젝트를 추가
        GameObject childObject1 = new GameObject("Child1");
        gameObjectTree.Root.Children.Add(new TreeNode<GameObject>(childObject1));

        GameObject childObject2 = new GameObject("Child2");
        gameObjectTree.Root.Children.Add(new TreeNode<GameObject>(childObject2));

        // 이제 Scene 뷰에서 부모-자식 관계를 확인할 수 있다.
    }
}