1. 트리란?
선형, 비선형 구조
스택과 큐는 자료구조에서 선형 구조라고 한다. 선형 구조는 데이터가 순차적으로 나열되어진 형태를 말하는데, 트리는 비선형구조로 이루어져있다. 비선형구조는 데이터가 계층적(혹은 망)으로 구성되어있다. 선형구조와 비선형구조의 차이점은 구성형태뿐만 아니라 용도에서도 차이점이 들어나느데, 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있다. 보통 컴퓨터의 폴더 구조가 대표적인 트리의 형태를 가지고 있다.
트리란?
트리(Tree)는 그래프의 일종으로 정점과 간선을 이용하여 데이터의 배치 형태를 추상화한 자료구조이다. 서로 다른 두 노드를 연결하는 길이 하나뿐인 그래프를 트리라고 부른다. 힙(Heap)을 구현하는 방법 중 하나가 트리이다.
트리의 특징
- 트리 자료구조는 일반적으로 대상 정보의 각 항목들을 계층적으로 구조화할 때 사용하는 비선형 자료구조이다.
- 트리의 구조는 '데이터 저장'의 의미보다는 '저장된 데이터를 더 효과적으로 탐색'하기 위해서 사용된다.
- 리스트와 다르게 데이터가 단순히 나열되는 구조는 아니다. 트리의 경우 부모(parent)와 자식(child)의 계층적인 관계로 표현된다.
- 트리는 사이클이 없다.
- 트리에서 루트노드를 제외한 모든 노드는 단 하나의 부모노드를 가진다.
- 계층적인 자료를 표현하는데 적합한 자료구조 이다.
2. 트리와 관련된 용어
- 노드(node)와 간선(edge)으로 구성되어 있다. 노드와 노드는 간선으로 연결되어 있다.
- 제일 최상위에 위치한 노드를 루트노드(Root Node)라 부르고 나머지 노드들을 서브트리(Sub Tree)라고 부른다.
전체 트리구조에서 A가 루트노드(Root Node)이고 그 밑에 존재한 나머지 {B,C,D,E,F,G,H,I,J}들은 서브 트리이다.
제일 왼쪽에 위치한 서브트리를 기준으로 보았을 때 B가 루트노드(Root Node)가 되어지고 그 밑 {E,F,G}들은 서브트리가 되어진다.
- 루트 노드(root node) : 부모가 없는 노드로 트리는 단 하나의 루트 노드를 가진다. (ex : A- 루트노드)
- 단말 노드(leaf node) : 자식이 없는 노드로 terminal 노드라고도 부른다. (ex : C, D, E - 단말 노드)
- 내부 노드(internal node) : 단말 노드가 아닌 노드(ex : A, B - 내부 노드)
- 간선(edge) : 노드를 연결하는 선
- 형제(sibling) : 같은 부모 노드를 갖는 노드들 (ex : D-E, B-C : 형제)
- 노드의 깊이(depth) : 루트 노드에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수(ex : D의 depth : 2)
- 노드의 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합 ( ex : level 1- {B, C} )
- 노드의 차수(degree) : 자식 노드의 개수 ( ex : B의 degree - 2, C의 degree - 0)
- 트리의 차수(degree of tree) : 트리의 최대 차수 ( ex : 위 트리의 차수는 2이다)
- 크기(size) : 트리에 포함된 모든 노드의 개수
3. 순회방법
순회 방법은 전위(pre-order), 중위(in-order), 후위(post-order) 순회가 있다.
- 전위 순회(pre-order) : 루트 노드를 먼저 순회한 이후, '왼쪽 하위 -> 오른쪽 하위' 순으로 순회하는 방법.
- 중위 순회(in-order) : 왼쪽 가장 하위 노드를 먼저 순회한 이후, '바로 상위 노드 -> 오른쪽 하위' 순으로 순회하는 방법.
- 후위 순회(pre-order) : 왼쪽 가장 하위 노드를 먼저 순회한 이후, '오른쪽 하위 노드 -> 바로 상위 노드' 순으로 순회하는 방법
- 전위 순회 순서 : 1 - 2 - 4 - 5 - 3 - 6 - 7
- 중위 순회 순서 : 4 - 2 - 5 - 1 - 6 - 3 - 7
- 후위 순회 순서 : 4 - 5 - 2 - 6 - 7 - 3 - 1
전위 순회, 중위 순회, 후위 순회 순서로 각 노드의 왼쪽, 아래, 오른쪽을 먼저 찍는 순서로 순회를 한다고 생각하면 편하다.
