트리(tree)

Rookiss님의 [c#과 유니티로 만드는 mmorpg 게임 개발 시리즈] part2 : 자료구조와 알고리즘 강의 내용을 정리했습니다.

Rookiss님의 [c++과 언리얼로 만드는 mmorpg 게임 개발 시리즈] part3: 자료구조와 알고리즘 강의 내용을 정리했습니다.

 

특징

- 노드와 간선으로 이루어져 있다.

- 노드는 데이터를 표현

- 간선은 노드의 계층 구조를 표현

- 트리는 재귀적인 특성을 갖는다. (트리는 서브  트리로 이루어진다)

 

트리 용어

 

노드 출력하기

- 트리는 재귀적인 특성을 갖기 때문에 재귀함수로 구현

        static void PrintTree(TreeNode<string> root)
        {
            Console.WriteLine(root.Data);

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

void PrintTree(NodeRef root, int depth)
{
    for (int i = 0; i < depth; i++)
    {
        cout << "-";
    }

    cout << root->data << endl;

    for (NodeRef& child : root->childeren)
    {
        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;
                height = Math.Max(height, newHeight); // 높이가 다른 경우 큰값으로 치환.
            }

            return height;
        }

// 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해서 거쳐야하는 간선의 수(aka 몇층?)
// 높이(height) : 가장 깊숙히 있는 노드의 깊이 max(depth)
int GetHeight(NodeRef root)
{
    int height = 1;

    for (NodeRef& child : root->childeren)
    {
        height = max(height, GetHeight(child) + 1);
    }

    return height;
}