트리

트리(Tree)

계층적 구조를 갖는 데이터를 표현하기 위한 자료구조

노드 : 데이터를 표현
간선 : 노드의 계층 구조를 표현하기 위하여 사용

이미지 출처: 나무위키

트리는 이처럼 트리안에 또 다른 트리가 있기에 재귀 함수를 많이 사용한다.

---

라는 간단한 트리를 코드로 구현 해보자.

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 = "기획실" };
        {
        	{
        	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 = "스토리" });
        	}
        	{
        	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 = "엔진" });
        	}
        	{
        	TreeNode<string> node = new TreeNode<string>() { Data = "아트팀"};
            node.Children.Add(new TreeNode<string>() { Data = "배경" });
            node.Children.Add(new TreeNode<string>() { Data = "캐릭터" });
        	}
        }
        return root;
	}
    static void Main(string[] args)
    {
    	TreeNode<string> root = MakeTree();
    }
}

이제 이 트리를 순회하면서 트리를 출력해보자.

static void PrintTree(TreeNode<T> root)
{
	Console.WriteLine(root.Data);
    
    foreach(TreeNode<string> child in root.Children)
    	PrintTree(child);
}

트리의 높이를 알아보자.

static int GetHeight(TreeNode<T> 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;
}