자료구조 공부 #16 (트리)

2021.04.22 - [이론공부/자료구조] - 자료구조 공부#15 (연결리스트3)

자료구조 공부#15 (연결리스트3)

---

트리(Tree)

계층적인 구조를 나타내는 자료구조

 

맨위를 루트노드, 아래를 서브트리

부모-자식 관계의 노드들로 이루어져 있다.

 

ex)

• 계층조직 표현
• 컴퓨터 디렉토리 구조
• 인공지능에서 결정트리

 

결정트리

 

트리에서의 용어

 

 

트리용어(1)

 

트리용어 (2)

 

 

트리의 종류

이진트리는 차수가 2이하이며, 일반트리는 제각각인 느낌

 

이진트리(Binary Tree)

모든 노드가 2개의 서브트리를 가지고 있는 트리

 - 서브트리는 공집합일 수 있다.

 

• 이진 트리의 노드에는 최대 2개 까지의 자식 노드가 존재
• 모든 노드의 차수가 2 이하가 된다 - 구현이 편리함
• 이진 트리에는 서브트리 간의 순서가 존재

이진 트리 구조

이진 트리의 성질

노드의 개수가 n 개이면 간선(Edge)의 개수는 n-1개

 

노드(n개) 간선(n-1개)

 

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

 

 

이진 트리의 분류

 

포화 이진 트리

 

완전 이진 트리

왼쪽에서 오른쪽 순서로 채워져 있는걸 알아야 한다.

 

---

표현 방법

배열, 링크로 구현이 가능하다

 

 

배열표현

배열 표현에서 부모와 자식 인덱스 관계

• 노드 i 의 부모 노드 인덱스 = i/2
• 노드 i 의 왼쪽 자식 노드 인덱스 = 2i
• 노드 i 의 오른쪽 자식 노드 인덱스 = 2i+1

 

링크표현

링크를 이용한 표현 방법

• 노드는 구조체로 표현
• 링크는 포인터로 표현

---

느낀점 : 화일 처리및 응용에서 봤던 내용과 어느정도 연관이 되는 자료구조 형식이다 참고하자.