트리 구현 연습

Jaemyeong Lee·2024년 10월 11일

C#C#과 유니티로 만드는 MMORPG 게임 개발 시리즈 Rookiss 자료구조와 알고리즘

C#과 유니티로 만드는 MMORPG 게임 개발 시리즈

목록 보기

80/208

전체 코드

namespace Tree
{
    class TreeNode<T>
    {
        public T Data { get; set; }  // 노드가 저장하는 데이터
        public List<TreeNode<T>> Children { get; set; } = new List<TreeNode<T>>();  // 자식 노드 목록
    }
    internal class Program
    {
        // 노드 기반으로 구현
        // 따로 라이브러리를 제공하지 않음

        static TreeNode<string> MakeTree()
        {
            TreeNode<string> root = new TreeNode<string>() { Data = "R1 개발실" };

            {
                TreeNode<string> node1 = new TreeNode<string>() { Data = "디자인팀" };
                node1.Children.Add(new TreeNode<string>() { Data = "전투" });
                node1.Children.Add(new TreeNode<string>() { Data = "경제" });
                node1.Children.Add(new TreeNode<string>() { Data = "스토리" });
                root.Children.Add(node1);
            }
            {
                TreeNode<string> node2 = new TreeNode<string>() { Data = "프로그래밍팀" };
                node2.Children.Add(new TreeNode<string>() { Data = "서버" });
                node2.Children.Add(new TreeNode<string>() { Data = "클라" });
                node2.Children.Add(new TreeNode<string>() { Data = "엔진" });
                root.Children.Add(node2);
            }
            {
                TreeNode<string> node3 = new TreeNode<string>() { Data = "아트팀" };
                node3.Children.Add(new TreeNode<string>() { Data = "배경" });
                node3.Children.Add(new TreeNode<string>() { Data = "캐릭터" });
                root.Children.Add(node3);
            }

            return root;
        }
        // 재귀 함수로 구현
        static void PrintTree(TreeNode<string> root)
        {
            // 접근
            Console.WriteLine(root.Data);
            foreach (TreeNode<string> child in root.Children) PrintTree(child);
        }
        static void PrintTree(TreeNode<string> root, int depth = 0)
        {
            Console.WriteLine(new string(' ', depth * 2) + root.Data);

            foreach (TreeNode<string> child in root.Children)
            {
                PrintTree(child, depth + 1);
            }
        }
        // 트리의 높이 구하기
        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, GetHeight(child) + 1);
            }

            return height;
        }
        static void Main(string[] args)
        {
            TreeNode<string> root = MakeTree();
            PrintTree(root);
            Console.WriteLine($"트리의 높이: {GetHeight(root)}");

        }
    }
}

디버깅으로 확인
순회

1. 트리(Tree)란?

트리(Tree)는 계층적 데이터 구조를 표현하는 비선형 자료구조입니다. 루트 노드(root node)를 기준으로 부모-자식 관계를 가지며, 순환(cycle)이 없는 구조입니다.

트리의 주요 특징

하나의 루트(root) 노드가 존재
각 노드는 여러 개의 자식(child) 노드를 가질 수 있음
부모(parent) 노드는 한 개만 존재하며, 자신을 가리키는 노드는 하나뿐
리프(leaf) 노드는 자식이 없는 노드
깊이(depth): 루트에서 해당 노드까지의 거리
높이(height): 루트에서 가장 깊은 리프까지의 거리

2. C# 트리 구현

트리를 구현하기 위해 제네릭 클래스를 활용하여 트리 노드를 생성합니다.

2.1 트리 노드 클래스 (`TreeNode<T>`)

using System;
using System.Collections.Generic;

namespace TreeExample
{
    class TreeNode<T>
    {
        public T Data { get; set; }  // 노드가 저장하는 데이터
        public List<TreeNode<T>> Children { get; set; } = new List<TreeNode<T>>();  // 자식 노드 목록
    }
}

📌 `TreeNode<T>` 클래스 설명

제네릭(Generic) 클래스:
- 다양한 타입의 데이터를 저장할 수 있도록 T를 활용
속성(Data):
- 노드가 저장하는 데이터(문자열, 숫자, 사용자 정의 객체 등)
속성(Children):
- List<TreeNode<T>>를 사용하여 여러 개의 자식 노드를 가질 수 있도록 설정
- 노드 생성 시 자식 리스트가 자동으로 초기화됨 (new List<TreeNode<T>>())

3. 트리 데이터 생성

트리를 생성하는 메서드 MakeTree()를 작성합니다.

3.1 트리 생성 메서드 (`MakeTree`)

static TreeNode<string> MakeTree()
{
    TreeNode<string> root = new TreeNode<string>() { Data = "R1 개발실" };

    {
        TreeNode<string> node1 = new TreeNode<string>() { Data = "디자인팀" };
        node1.Children.Add(new TreeNode<string>() { Data = "전투" });
        node1.Children.Add(new TreeNode<string>() { Data = "경제" });
        node1.Children.Add(new TreeNode<string>() { Data = "스토리" });
        root.Children.Add(node1);
    }
    {
        TreeNode<string> node2 = new TreeNode<string>() { Data = "프로그래밍팀" };
        node2.Children.Add(new TreeNode<string>() { Data = "서버" });
        node2.Children.Add(new TreeNode<string>() { Data = "클라" });
        node2.Children.Add(new TreeNode<string>() { Data = "엔진" });
        root.Children.Add(node2);
    }
    {
        TreeNode<string> node3 = new TreeNode<string>() { Data = "아트팀" };
        node3.Children.Add(new TreeNode<string>() { Data = "배경" });
        node3.Children.Add(new TreeNode<string>() { Data = "캐릭터" });
        root.Children.Add(node3);
    }

    return root;
}

📌 `MakeTree()` 메서드 설명

root 노드: "R1 개발실" (트리의 최상위 노드)
각 부서(자식 노드):
- "디자인팀": "전투", "경제", "스토리"
- "프로그래밍팀": "서버", "클라", "엔진"
- "아트팀": "배경", "캐릭터"
각 팀은 루트 노드의 자식 노드이며, 팀 내부의 세부 항목들이 다시 자식 노드가 됨
최종적으로 트리 형태의 계층 구조가 완성됨

4. 트리 출력 (DFS 방식)

트리의 모든 데이터를 출력하기 위해 재귀 함수를 활용합니다.

4.1 트리 출력 메서드 (`PrintTree`)

static void PrintTree(TreeNode<string> root, int depth = 0)
{
    Console.WriteLine(new string(' ', depth * 2) + root.Data);

    foreach (TreeNode<string> child in root.Children)
    {
        PrintTree(child, depth + 1);
    }
}

📌 `PrintTree()` 메서드 설명

DFS(깊이 우선 탐색) 방식으로 트리를 탐색하면서 출력
depth 인자를 사용하여 계층 구조를 표현 (new string(' ', depth * 2))
재귀 호출을 통해 모든 노드를 탐색하며 출력

📌 실행 결과

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

5. 트리의 높이 계산

트리의 높이를 계산하는 메서드를 구현합니다.

5.1 트리 높이 계산 메서드 (`GetHeight`)

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

    foreach (TreeNode<string> child in root.Children)
    {
        height = Math.Max(height, GetHeight(child) + 1);
    }

    return height;
}

📌 `GetHeight()` 메서드 설명

재귀적으로 트리의 깊이를 계산
모든 자식 노드의 높이 중 가장 큰 값을 선택하여 height를 업데이트
리프 노드(자식이 없는 노드)는 기본적으로 0을 반환

📌 실행 결과

트리의 높이: 2

"디자인팀", "프로그래밍팀", "아트팀"까지가 depth = 1
"전투", "경제", "스토리" 등은 depth = 2
따라서 트리의 높이(가장 깊은 노드의 깊이)는 2가 됨

6. `Main()` 메서드 - 실행 부분

class Program
{
    static void Main(string[] args)
    {
        TreeNode<string> root = MakeTree();
        PrintTree(root);
        Console.WriteLine($"트리의 높이: {GetHeight(root)}");
    }
}

📌 실행 흐름

MakeTree()를 호출하여 트리 생성
PrintTree(root)를 호출하여 트리의 구조 출력
GetHeight(root)를 호출하여 트리의 높이 계산 및 출력

7. 최종 정리

📌 트리(Tree)

트리는 비선형 자료구조로 부모-자식 관계를 가짐
TreeNode<T> 클래스를 이용하여 제네릭 트리 구조를 구현

📌 트리 생성 (`MakeTree`)

"R1 개발실"을 루트로 하는 조직도 형태의 트리 생성

📌 트리 순회 (`PrintTree`)

DFS(깊이 우선 탐색) 방식으로 재귀를 사용하여 트리 구조를 출력

📌 트리의 높이 계산 (`GetHeight`)

재귀적으로 각 노드의 최대 깊이를 구하여 트리의 높이를 계산

8. 실행 결과

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

Jaemyeong Lee

李家네_공부방

이전 포스트

트리 이론

다음 포스트

트리 구현 연습

C#과 유니티로 만드는 MMORPG 게임 개발 시리즈

전체 코드

1. 트리(Tree)란?

트리의 주요 특징

2. C# 트리 구현

2.1 트리 노드 클래스 (`TreeNode<T>`)

📌 `TreeNode<T>` 클래스 설명

3. 트리 데이터 생성

3.1 트리 생성 메서드 (`MakeTree`)

📌 `MakeTree()` 메서드 설명

4. 트리 출력 (DFS 방식)

4.1 트리 출력 메서드 (`PrintTree`)

📌 `PrintTree()` 메서드 설명

📌 실행 결과

5. 트리의 높이 계산

5.1 트리 높이 계산 메서드 (`GetHeight`)

📌 `GetHeight()` 메서드 설명

📌 실행 결과

6. `Main()` 메서드 - 실행 부분

📌 실행 흐름

7. 최종 정리

📌 트리(Tree)

📌 트리 생성 (`MakeTree`)

📌 트리 순회 (`PrintTree`)

📌 트리의 높이 계산 (`GetHeight`)

8. 실행 결과

트리 이론

힙 이론

0개의 댓글

트리 구현 연습

C#과 유니티로 만드는 MMORPG 게임 개발 시리즈

전체 코드

1. 트리(Tree)란?

트리의 주요 특징

2. C# 트리 구현

2.1 트리 노드 클래스 (TreeNode<T>)

📌 TreeNode<T> 클래스 설명

3. 트리 데이터 생성

3.1 트리 생성 메서드 (MakeTree)

📌 MakeTree() 메서드 설명

4. 트리 출력 (DFS 방식)

4.1 트리 출력 메서드 (PrintTree)

📌 PrintTree() 메서드 설명

📌 실행 결과

5. 트리의 높이 계산

5.1 트리 높이 계산 메서드 (GetHeight)

📌 GetHeight() 메서드 설명

📌 실행 결과

6. Main() 메서드 - 실행 부분

📌 실행 흐름

7. 최종 정리

📌 트리(Tree)

📌 트리 생성 (MakeTree)

📌 트리 순회 (PrintTree)

📌 트리의 높이 계산 (GetHeight)

8. 실행 결과

트리 이론

힙 이론

0개의 댓글

2.1 트리 노드 클래스 (`TreeNode<T>`)

📌 `TreeNode<T>` 클래스 설명

3.1 트리 생성 메서드 (`MakeTree`)

📌 `MakeTree()` 메서드 설명

4.1 트리 출력 메서드 (`PrintTree`)

📌 `PrintTree()` 메서드 설명

5.1 트리 높이 계산 메서드 (`GetHeight`)

📌 `GetHeight()` 메서드 설명

6. `Main()` 메서드 - 실행 부분

📌 트리 생성 (`MakeTree`)

📌 트리 순회 (`PrintTree`)

📌 트리의 높이 계산 (`GetHeight`)