Data Structure - Tree(Vol.1), (자료구조-트리)

안녕하세요.

공상 개발입니다.

 

오늘은 트리(Tree)에 대해 간단히 알아보는 시간을 갖겠습니다.

 

---

 

1. 트리(Tree)란? 2. 트리의 용어 3. 트리의 종류         - 이진 트리(Binary Tree)  - 이진 트리의 분류  - 이진 트리의 표현 4. 이진 트리의 순회 5. 레벨 순회 (level order) 6. 이진 트리 연산

 

---

 

1. 트리(Tree)란?

 

트리(TREE) 리스트, 스택, 큐 등은 선형 구조 트리 : 계층적인 구조를 나타내는 자료구조

 

 

 

자료구조에서는 부모-자식 관계의 노드들로 구성되어 있는 구조를 트리라고 부릅니다.

응용 분야로는

1. 계층적인 조직 표현

2. 컴퓨터 디스크의 디렉터리 구조

3. 인공지능에서의 결정 트리(decision tree) 등이 있습니다.

 

 

 

---

 

2. 트리의 용어

 

 

노드(node): 트리의 구성요소   루트(root): 부모가 없는 노드(A)   서브 트리(subtree): 하나의 노드와 그 노드의 자손들로 이루어진 트리   간선(edge): 노드와 노드의 연결선  단말 노드(terminal node, leaf node): 자식이 없는 노드(E, F, G, H, I, J)  비 단말 노드: 적어도 하나의 자식을 가지는 노드(A, B, C, D)  자식, 부모, 형제, 조상, 자손 노드: 인간과 동일  레벨(level): 트리의 각층의 번호  높이(height): 트리의 최대 레벨(3)  노드의 차수(degree): 노드가 가지고 있는 자식 노드의 개수  트리의 차수(degree): 트리가 가지고 있는 차수 중 가장 큰 값

 

---

 

3. 트리의 종류

 

 

이진 트리(Binary Tree)

 

 

이진 트리는 공집합이거나 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의합니다.

또한, 이진 트리의 서브 트리들은 모두 이진 트리이어야 합니다

높이가 h인 이진 트리의 경우, 최소 h개의 노드를 가지며, 최대 2h-1개의 노드를 가집니다.

---

포화 이진 트리(Full Binary Tree)

 

 

용어 그대로 트리의 각 레벨에 노드가 꽉 차있는 이진 트리를 의미합니다.

전체 노드 개수: 2h-1개이며,

포화 이진 트리에는 다음과 같이 각 노드에 번호를 붙일 수 있습니다.

---

 

완전 이진 트리(complete binary tree)

 

 

완전 이진 트리(complete binary tree)는 레벨 1부터 k-1까지는 노드가 모두 채워져 있고,

마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진 트리를 말합니다.

포화 이진 트리와 노드 번호가 일치합니다.

 

완전 이진 트리(complete binary tree) 구분법

 

 

왼쪽 그림은 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있으므로 완전 이진 트리입니다.

오른쪽 그림은 마지막 레벨 k에서 오른쪽으로 노드가 먼저 채워져 있으므로 완전 이진 트리가 아닙니다.

---

---

 

4. 이진 트리의 순회

 

이진 트리의 표현 방법으로는 2가지 방법이 있습니다.

바로 배열 표현법과 링크 표현법입니다.

배열 표현법

 

링크 표현법

 

배열표현법: 모든 이진 트리를 포화 이진 트리라고 가정하고 각 노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아                  노드의 데이터를 배열에 저장하는 방법 링크 표현법: 포인터를 이용하여 부모노드가 자식노드를 가리키게 하는 방법

 

이번 시간에는 링크 표현법으로 이진 트리의 순회에 접근하겠습니다.

 

 

 

 

위의 3가지 순회 방법은 매번 나오는 개념입니다.

가장 좋은 방법은 손으로 직접 순회를 해보는 것이라고 생각합니다.

항상 언급하듯이, 직접 구현을 해보면 머릿속에 더 오래 남아 문제를 해결할 때 도움이 됩니다.

 

트리 순회 구현 코드

 

---

 

5. 레벨 순회 (level order)

 

 

레벨 순회(level order)는 각 노드를 레벨 순으로 검사하는 순회 방법입니다.

지금까지 3가지 순회에서는 스택을 사용했지만, 레벨 순회에서는 큐를 사용해 접근합니다.

 

레벨 순회 구현 코드

'

 

---

 

6. 이진 트리 연산

 

구현 로직 : 각각의 서브 트리에 대하여 순환 호출한 다음, 반환되는 값에 1을 더하여 반환합니다.

 

개수 연산

 

구현 로직 : 서브 트리에 대하여 순환 호출하고 서브 트리들의 반환 값 중에서 최댓값을 구하여 반환합니다.

 

높이 연산

 

---

 

피드백

 

작성된 내용 중 잘못된 정보나 접근이 있을 시, www.instagram.com/hong_.98/을 통해 말씀해 주시면 감사하겠습니다.

읽어주셔서 감사합니다