본문으로 바로가기

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

category 이론공부/자료구조 2021. 5. 4. 16:20

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

 

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

2021.04.20 - [이론공부/자료구조] - 자료구조 공부#14 (연결리스트2) 이전내용을 참고하자 이중 연결 리스트 단순 연결리스트, 원형 연결리스트의 단점인 선행 노드를 찾기가 힘든걸 극복해낸 리스

thesauro.tistory.com


트리(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

 

링크표현

링크를 이용한 표현 방법

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

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