C# 자료구조 (트리)
트리 (Tree)
트리는 1 : 1 로 대응하는 선형적인 구조와는 달리 1 : 다, 다 : 다 대응이 가능한 비선형적인 자료구조를 가지고있다.
트리는 계층적인 구조를 갖고있고 사이클이 없는 그래프의 일종이다.
일단 트리 구조의 그림을 보겠다.
트리는 최상위에 있는 부모(Root) 노드를 시작하여 간선(Edge)을 연결해 여려 개의 자식 노드를 가지는 구조를 가지고있다.
부모노드는 0개 이상의 자식노드들을 가지고 있을수도 있고 그 자식노드에 자식노드들을 또 가질수도 있다.
하지만 자식노드는 부모 노드를 2개 이상을 연결할수 없으면 무조건 하나인 부모의 노드를 연결할수 있다.
트리에서 자주 사용하는 용어들의 설명이다.
루트(Root) : 트리의 가장 꼭대기에 있는 노드
간선(Edge) : 두 노드를 잇는 링크
자식(Child) : 부모 노드 밑의 자식 노드
부모(Parent) : 부모가 같은 자식 노드들
형제(Sidling) : 부모가 같은 자식 노드들
단말(Leaf) : 트리에서 자식노드를 갖지 않는 하단의 노드
높이(Height) : 특정 노드에서 루트 사이의 길이 (윗쪽 방향으로 계산)
깊이(Deqth) : 루트 노드에서 특정 노드까지의 길이 (아래쪽 방향으로 계산)
트리 높이(Tree Height) : 가장 먼 거리에 있는 Leaf 노드와 루트 사이의 길이
트리 깊이(Tree Death) : 루트 노드에서 가장 먼 Leaf 노드와 루트 사이의 길이
레벨(Level) : 루트 노드로부터의 수평적 깊이 (루트노드 레벨 = 1)
노드의 차수(Node Degree) : 한 노드의 서브트리의 갯수. 자식 노드의 수와 동일.
트리의 차수(Tree Degree) : 트리 안 노드들의 차수 중 최대 차수
저 그림의 나와있는 레벨은 최상위 부모 A부터 시작되서 맨 끝 K노드 까지 가서 레벨은 4이고
트리 깊이는 가장 먼 단말 노드인 0부터 시작해서 K의 높이가 3이고
H의 노드를 기준으로한 깊이는 아래쪽 방향으로 2이고
트리의 최대차수는 A의 자식노드들인 B, C, D 3개인걸 알수있다.
트리의 자료구조는 여러 방식으로 표현이 가능한데 가장 일반적인 N-링크 표현법, 왼쪽 자식 - 오른쪽 형제노드
표현법에 대해 설명하겠다.
N-링크 표현법
N-링크 표현법은 그 트리의 최대 차수의 크기를 N개만큼 링크를 두어서 트리를 표현하는 방식이다.
그림에서 보았듯이 일단 최대의 차수인 3의 크기로 지정해서 부모 노드에 간선으로 연결되있는 자식 노드들을 추가한다.
N- Link 표현법을 간단하게 구현한 코드를 보겠다.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace N_LInk_Node_Tree
{
class TreeNode<T>
{
public T Data { get; set; }
public List<TreeNode<T>> Links { get; private set; }
public TreeNode(T data)
{
Data = data;
Links = new List<TreeNode<T>>();
}
/* public TreeNode(T data, int maxDegree = 3)
{
Data = data;
Links = new TreeNode<T>[maxDegree];
}*/
}
class Program
{
static void Main(string[] args)
{
TreeNode<string> A = new TreeNode<string>("A");
TreeNode<string> B = new TreeNode<string>("B");
TreeNode<string> C = new TreeNode<string>("C");
TreeNode<string> D = new TreeNode<string>("D");
A.Links.Add(B);
A.Links.Add(C);
A.Links.Add(D);
B.Links.Add(new TreeNode<string>("E"));
B.Links.Add(new TreeNode<string>("F"));
D.Links.Add(new TreeNode<string>("G"));
foreach (TreeNode<string> node in A.Links)
{
Console.WriteLine(node.Data);
}
}
}
}
일단 노드 클래스를 만들어서 data를 넣을 Data 프로퍼티를 선언하고 노드들을 연결할 리스트를 추가한다.]
N링크 표현법의 장점은 직관적으로 표현이 가능해서 쉽다는 큰 장점이 있지만 고정된 크기를 이용해서 사용하기 때문에 메모리 공간 낭비를 발생이 클수있다.
이건 이제 동적배열을 이용해서 그나마 최소한 공간 낭비를 지울려고 List로 만든것이다.