내일배움캠프 22일차 - 자료구조 (트리)

오늘은 많이 헷갈리던 트리 자료구조에 대해서 한 번 싹 정리하는 시간을 가져보도록 하겠습니다.

 

트리(Tree)

 

트리는 1:1로 대응하는 선형적인 구조와는 다리 1:N, N:N 대응이 가능한 비선형적인 자료구조를 가지고있다.

계층적인 구조를 갖고있고, 사이클이 없는 그래프의 일종이다.

 

먼저 트리의 그림부터 보자.

츌처 : C#으로 이해하는 자료 구조

 

트리는 최상위에 있는 부모 즉, 루트 노드를 시작하여 간선(Edge)을 연결해 여러 개의 자식노드를 가지는 구조이다.

부모노드는 0개 이상의 자식노드들을 가지고 있을 수도 있고 그 자식노드에 자식노드들을 또 가질 수도 있다.

하지만 자식노드는 부모 노드를 2개 이상 연결할 수 없으며 무조건 최대 한 개의 부모의 노드와 연결할 수 있다.

 

다음은 트리에서 자주 사용 되는 용어들이다.

 

루트(Root) : 트리의 가장 꼭대기에 있는 노드
간선(Edge) : 두 노드를 잇는 링크
자식(Child) : 부모 노드 밑의 자식 노드
부모(Parent) : 부모가 같은 자식 노드들
형제(Sidling) : 부모가 같은 자식 노드들
단말(Leaf) : 트리에서 자식노드를 갖지 않는 하단의 노드
높이(Height) : 특정 노드에서 루트 사이의 길이 (윗쪽 방향으로 계산)
깊이(Deqth) : 루트 노드에서 특정 노드까지의 길이 (아래쪽 방향으로 계산)
트리 높이(Tree Height) : 가장 먼 거리에 있는 Leaf 노드와 루트 사이의 길이
트리 깊이(Tree Death) : 루트 노드에서 가장 먼 Leaf 노드와 루트 사이의 길이

레벨(Level) : 루트 노드로부터의 수평적 깊이 (루트노드 레벨 = 1)
노드의 차수(Node Degree) : 한 노드의 서브트리의 갯수. 자식 노드의 수와 동일.
트리의 차수(Tree Degree) : 트리 안 노드들의 차수 중 최대 차수

 

위의 그림에서 레벨은 4이며 트리의 깊이는 3, 트리의 최대 차수는 3개라는 걸 알 수 있다.

 

트리의 자료구조는 여러 방식으로 표현이 가능한데 가장 일반적인 N-링크 표현법, 왼쪽 자식 - 오른쪽 형제 노드 표현법에 대해 알아보자.

 

N-링크 표현법

 

N-링크 표현법은 그 트리의 최대 차수의 크기를 N개 만큼 링크를 두어서 트리를 표현하는 방법이다.

 

출처 : C#으로 이해하는 자료구조

 

그림에서 보았듯이 차수를 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링크 표현법의 장점은 직관적으로 표현이 가능해서 쉽다는 큰 장점이 있지만 고정 된 크기를 이용해서 사용하기 때문에 메모리 공간 낭비를 발생할 수 있다는 점이다.

 

다음은 이진 트리 순회에 대해 짧게 알아보겠다.

 

이진 트리

 

트리 구조에서 각 노드를 정확히 한 번만 방문하는 과정이다.

 

배열이나 연결 리스트와 같은 선형 자료 구조에서는 보통 한가지의 논리적인 순회 방법이 존재하지만 트리나 그래프 같은 비선형 자료 구조에서는 많은 순회 방법이 존재하다.

 

트리를 순회하는 방법으로는 전위, 중위, 후위 정도가 사용되는데 각 각의 의미부터 알아 보자

 

출처 : C#으로 이해하는 자료구조

 

전위 순회는 DFS알고리즘과 같은걸 알 수 있다

순회는 노드, 노드의 왼쪽, 노드의 오른쪽 순으로 순회하여 출력된다.

 

다음은 중위 순회이다

 

중위 순회는 순회의 순서가 노드의 왼쪽, 노드, 노드의 오른쪽 순으로 순회하여 출력된다.

 

마지막으로 후위 순회는 노드의 왼쪽, 노드의 오른쪽, 노드 순으로 순회하여 출력된다.

 

위의 3가지 순회는 결국 순서의 차이라 순서를 외우는게 가장 편하다고 생각된다.