Part 2-5-1. 트리 : 트리 이론과 구현

 

 

트리

 

[트리 이론]

트리 👉 계층적 구조를 갖는 데이터를 위한 자료 구조 ex) 회사 조직도, 

노드(Node) : 데이터 표현

• 루트(Root) 노드는 트리를 상징하며, 부모가 없다. 즉 최상위 조상이 되는 트리의 첫 노드.
• 잎(Leaf) 노드는 자식이 없는, 트리의 말단 노드들을 뜻한다.

 

간선(Edge) : 노드의 계층 구조를 표현하기 위해 사용
이름 그대로 나무와 같다. 뻗어 나가는 구조.

 

트리도 그래프의 일종이라고 볼 수 있다. 단, 제한적인 모양의 그래프라고 생각할 수 있다.

• 또한 트리는 사이클이 있어선 안된다. 👉 한 쪽 방향으로만 뻗어야 한다.
• 각 노드의 부모는 딱 하나만 있어야 한다.

 

트리는 재귀적인 속성을 가진다. 따라서 트리에서 일부분을 떼보면 그 부분도 트리다.(서브 트리)

 

---

 

트리 구현

트리는 재귀적 속성을 가진다. 또한 트리이므로 사이클이 없고 각각 한 방향으로만 뻗어 내려갈 수 있다. 그리고 트리 역시 라이브러리에서 제공되지 않는다. 직접 구현해야 한다.

 

[트리 생성]

 

 

using System;
using System.Collections.Generic;

namespace Excercise
{
    class TreeNode<T>
    {
        public T Data { get; set; }
        public List<TreeNode<T>> Children { get; set; } = new List<TreeNode<T>>();
    }

    class Program
    {
        static TreeNode<string> MakeTree()
        {
            TreeNode<string> root = new TreeNode<string>() { Data = "R1 개발실" };
            {
                {
                    TreeNode<string> node = new TreeNode<string>() { Data = "디자인팀" };
                    node.Children.Add(new TreeNode<string>() { Data = "전투" });
                    node.Children.Add(new TreeNode<string>() { Data = "경제" });
                    node.Children.Add(new TreeNode<string>() { Data = "스토리" });
                    root.Children.Add(node);
                }

                {
                    TreeNode<string> node = new TreeNode<string>() { Data = "프로그래밍팀" };
                    node.Children.Add(new TreeNode<string>() { Data = "서버" });
                    node.Children.Add(new TreeNode<string>() { Data = "클라" });
                    node.Children.Add(new TreeNode<string>() { Data = "엔진" });
                    root.Children.Add(node);
                }

                {
                    TreeNode<string> node = new TreeNode<string>() { Data = "아트팀" };
                    node.Children.Add(new TreeNode<string>() { Data = "배경" });
                    node.Children.Add(new TreeNode<string>() { Data = "캐릭터" });
                    root.Children.Add(node);
                }
            }

            return root;
        }


        static void Main(string[] args)
        {
            TreeNode<string> root = MakeTree();
        }
    }
}

 

'TreeNode'라는 하나의 노드 생성하고 데이터 Data 를 가진다. 그리고 자식 노드들을 가진다.

• Children 👉 해당 노드의 자식 노드들을 리스트에 저장
• 오직 한 방향으로만 내려가므로 부모 노드를 굳이 저장하여 알아야 할 필요가 없다.
• 자식 노드들이 누군지만 알면 됨.

 

트리 생성하기

• 루트 노드 root 부터 차례 차례 각각의 노드들의 Children 리스트에 자식 노드들을 추가해준다.
• root 루트 노드를 리턴한다. (루트 노드만 알면 해당 트리 정보를 모두 얻은 것이나 마찬가지다. 오직 한 방향으로만 내려가므로.)

 

[트리 순회]

        static void PrintTree(TreeNode<string> root)
        {
            // 현재 노드의 데이터 접근
            Console.WriteLine(root.Data);

            // 재귀적으로 자식들의 데이터 접근
            foreach (TreeNode<string> child in root.Children)
                PrintTree(child);
        }

        static void Main(string[] args)
        {
            TreeNode<string> root = MakeTree();

            PrintTree(root);

            Console.WriteLine(GetHeight(root));  // 2
        }

출력

R1 개발실
디자인팀
전투
경제
스토리
프로그래밍팀
서버
클라
엔진
아트팀
배경
캐릭터

 

DFS 방식으로, 재귀적으로 자식 노드들에게 접근한다.

1. R1 개발실
1 - 1. 디자인팀
1 - 1 - 1. 전투
1 - 1 - 2. 경제
1 - 1 - 3. 스토리

 

1 - 2. 프로그래밍팀

1 - 2 - 1. 서버
1 - 2 - 2. 클라
1 - 2 - 3. 엔진

 

1 - 3. 아트팀
1 - 3 - 1. 배경
1 - 3 - 2. 캐릭터

 

[트리의 높이]

해당 트리의 높이는 2이다.

        static int GetHeight(TreeNode<string> root)
        {
            int height = 0;

            foreach (TreeNode<string> child in root.Children)
            {
                int newHeight = GetHeight(child) + 1;
                if (height < newHeight)
                    height = newHeight;
                // 👉 height = Math.Max(height, newHeight); 와 같음
            }
            return height;
        }

        static void Main(string[] args)
        {
            TreeNode<string> root = MakeTree();

            PrintTree(root);

            Console.WriteLine(GetHeight(root));  // 2
        }

 

• 재귀적으로 트리의 높이는 (깊이가 가장 깊은 서브 트리의 깊이 + 1) 이어야 한다.
• 모든 자식들을 재귀적으로 순회 하여 깊이를 리턴한다.  (잎 노드들은 0 을 리턴한다.)
• 더 큰 값의 깊이를 가진 서브 트리가 있다면 해당 깊이를 height로 업뎃한다. (최대값 찾기 알고리즘)

 

R1 개발실 ⭐
디자인팀 - 1 리턴 👉 newHeight= 2 ✔

전투 - 0 리턴

경제 - 0 리턴

스토리 - 0 리턴

 

프로그래밍팀 - 1 리턴 👉 newHeight = 2
서버 - 0 리턴
클라 - 0 리턴
엔진 - 0 리턴

 

아트팀 - 1 리턴 👉 newHeight= 2

배경 - 0 리턴

캐릭터 - 0 리턴

따라서 리턴할 height의 값은 2가 된다.