자료구조 & 알고리즘

[JAVA/자료구조] 트리(Tree), 이진트리(Binary Tree) 란?

2023. 6. 8. 20:57
목차
  1. 트리(Tree)
  2. 트리의 구조 (용어) 
  3. 트리의 특징
  4. 이진트리(Binary Tree)
  5. 이진트리의 종류
  6. 1. 포화 이진 트리 (Perfect Binary Tree)
  7. 2. 완전 이진 트리 (Complete Binary Tree)
  8. 3. 정 이진 트리 (Full Binary Tree)
  9. 4. 편향 트리(Skewed Binary Tree) = 사향 트리
  10. 5. 균형 이진 트리 (Balanced Binary Tree)
  11. 이진 트리의 순회(Traversal)
  12. 1. 전위 순회 (Preorder Traversal )
  13. 2. 중위 순회 (Inorder Traversal)
  14. 3. 후위 순회 (Postorder Traversal)
  15. 4. 레벨 순회(LevelorderTraversal)

트리(Tree)

트리는 Node와 Edge로 이루어진 자료구조이다.

각 노드들이 나무가지처럼 브랜치( = 엣지, 링크)로 연결된 비선형적, 계층적 자료구조이다.

트리의 구조 (용어) 

노드와 에지

  • 노드(Node) : 트리 구조에서 자료 값을 담고있는 단위 
  • 에지(Edge) : 각 노드 간의 연결 선
  • 루트 노드(Root) : 가장 위의 노드 (1)
  • 잎새 노드(Leaf) : 자식이 없는 노드 (8), (9), (10) ...
  • 내부 노드(Internal) : 잎새 노드를 제외한 모든 노드

노드 간의 관계

  • 부모(Parent) : 연결된 두 노드 중 상위 노드 (2번 노드는 4번 노드의 부모 노드)
  • 자식(Child) : 연결된 두 노드 중 하위 노드 (4번 노드는 2번 노드의 자식 노드)
  • 형제(Sibling) : 같은 부모를 가지는 노드 ( 4번과 5번 노드는 형제 노드)

트리 구조 관련 

  • 깊이(Depth) : 루트에서 해당 노드까지의 간선 수 (4번노드의 깊이는 2) ,  (12번 노드의 깊이는 3)
  • 레벨(Level) : 트리의 특정 깊이를 가지는 노드의 집합( 4, 5, 6, 7번 노드는 level 2), (2, 3번 노드는 level 1)
  • 높이(Height) : 트리에서 가장 큰 레벨 값 (위의 트리의 높이는 3)
  • 크기(Size) : 자신을 포함한 자식노드의 개수 (1번노드에서의 크기는 15) , (5번노드에서의 크기는 3)
  • 차수(Degree) : 각 노드가 가진 가지의 수 (1번 노드의 차수는 2 ) , ( 이 트리에서 모든 노드의 차수는 2이다.)
  • 트리의 차수 : 트리의 노드들이 가진 차수 중 가장 큰 차수

트리의 특징

트리는 하나의 루트 노드를 갖는다.

  • 루트 노드를 포함한 모든 노드는 0개 이상의 자식노드를 갖고 있다.

두 노드간의 이동 방법은 유일하다.

  • 그래프의 경우 다른 노드로 이동하는 방법이 여러개 일 수 있지만, 트리는 그렇지 않다.
  • 계층적 구조이기 때문에, 두 노드 사이에 이동경로는 한가지이다.
  • 따라서 트리에는 사이클(cycle)이 존재할 수 없다.

비선형 자료구조로 계층적 관계를 표현한다.

  • 디렉터리 구조, 조직도 등

하나의 Edge를 끊으면 2개의 Sub-Tree로 분리된다.

  • Edge가 끊어지면, 끊어진 Edge를 기준으로 서로 다른 Tree가 된다.
  • 즉, 하나의 Tree에서 모든 Node는 Edge로 연결되어있다.

이진트리(Binary Tree)

모든 노드들이 둘 이하의 자식을 가진 트리이다.

각 노드는 좌, 우를 구분한다.


이진트리의 종류

1. 포화 이진 트리 (Perfect Binary Tree)

모든 레벨에서 노드들이 가득 차있는 트리

  • 포화 이진트리의 높이가 h 일때, 노드의 수는 2^(h+1) -1 개
  • 포화 이진트리의 노드가 N개 일때, 높이는 logN개
  • 이진 트리의 노드가 N개 일때, 최대 가능한 높이는 N (편향트리 일때)


2. 완전 이진 트리 (Complete Binary Tree)

마지막 레벨을 제외하고 노드들이 가득 차 있는 트리

(자식 노드가 하나만 있을 경우, 왼쪽부터 채워져야 한다.)


3. 정 이진 트리 (Full Binary Tree)

모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리


4. 편향 트리(Skewed Binary Tree) = 사향 트리

한쪽으로 기울어진 트리

모든 노드가 왼쪽에만 있거나, 모든 노드가 오른쪽에만 있는 트리


5. 균형 이진 트리 (Balanced Binary Tree)

높이 균형이 맞는 트리

모든 노드의 좌우 서브 트리 높이가 1 이상 차이나지 않는 트리


이진 트리의 순회(Traversal)

순회 : 모든 노드를 빠뜨리거나, 중복하지 않고 모두 방문하는 연산

1. 전위 순회 (Preorder Traversal )

방문 순서 : 현재노드 > 왼쪽노드 > 오른쪽 노드

  • 현재 노드 먼저 방문 한다.
  • 왼쪽 노드가 있으면 왼쪽노드가 없는 노드가 나올때까지 계속 왼쪽노드를 방문한다. 
  • 더이상 왼쪽노드를 찾을 수 없으면, 부모노드의 오른쪽 노드를 탐색한다.


2. 중위 순회 (Inorder Traversal)

방문 순서 : 왼쪽노드 > 현재노드 > 오른쪽 노드

  • 왼쪽 끝의 노드를 찾아서 왼쪽으로 이동한다.
  • 왼쪽 노드를 방문 후 부모노드(현재)를 방문한다.
  • 부모노드의 오른쪽노드를 방문한다. 
  • 만약 해당 노드의 왼쪽노드가 존재한다면 그 왼쪽노드 먼저 방문한다. (4번째 -> 6번째 노드의 경우)


3. 후위 순회 (Postorder Traversal)

방문 순서 : 왼쪽노드 > 오른쪽 노드 > 현재 노드

  • 왼쪽 끝의 노드를 찾아서 왼쪽으로 이동한다.
  • 왼쪽노드를 방문 후 형제노드(오른쪽) 노드를 방문한다.
  • 왼쪽, 오른쪽 노드를 모두 방문했으면 부모노드(현재)를 방문한다.
  • 만약 오른쪽노드를 방문했는데, 그 노드의 왼쪽 노드가 존재한다면 그 왼쪽 노드 먼저 방문한다. (3 -> 5 -> 4의 경우)


4. 레벨 순회(LevelorderTraversal)

방문 순서 : 위쪽 레벨부터 왼쪽노드 -> 오른쪽 노드 순으로 방문

BFS(Breadth-first search)와 같다.

 

반응형
저작자표시 (새창열림)

'자료구조 & 알고리즘' 카테고리의 다른 글

[JAVA/자료구조] 그래프(Graph)의 개념, 탐색, 구현  (2) 2023.06.11
[JAVA/자료구조] HashSet  (0) 2023.06.09
[JAVA/자료구조] Map / HashMap / Hashtable  (0) 2023.06.06
[JAVA/자료구조] DEQUE 데크 (양방향 큐)  (0) 2023.06.06
[JAVA/자료구조] Queue 큐  (0) 2023.06.05
  1. 트리(Tree)
  2. 트리의 구조 (용어) 
  3. 트리의 특징
  4. 이진트리(Binary Tree)
  5. 이진트리의 종류
  6. 1. 포화 이진 트리 (Perfect Binary Tree)
  7. 2. 완전 이진 트리 (Complete Binary Tree)
  8. 3. 정 이진 트리 (Full Binary Tree)
  9. 4. 편향 트리(Skewed Binary Tree) = 사향 트리
  10. 5. 균형 이진 트리 (Balanced Binary Tree)
  11. 이진 트리의 순회(Traversal)
  12. 1. 전위 순회 (Preorder Traversal )
  13. 2. 중위 순회 (Inorder Traversal)
  14. 3. 후위 순회 (Postorder Traversal)
  15. 4. 레벨 순회(LevelorderTraversal)
'자료구조 & 알고리즘' 카테고리의 다른 글
  • [JAVA/자료구조] 그래프(Graph)의 개념, 탐색, 구현
  • [JAVA/자료구조] HashSet
  • [JAVA/자료구조] Map / HashMap / Hashtable
  • [JAVA/자료구조] DEQUE 데크 (양방향 큐)
HSRyuuu
HSRyuuu
Web Backend Developer happyhsryu
HSRyuuu
HS_dev_log
HSRyuuu
전체
오늘
어제
  • 전체 글 보기 (233)
    • Java (25)
    • Spring (27)
    • JPA & QueryDSL (13)
    • Database (17)
    • 자료구조 & 알고리즘 (30)
    • DevOps (10)
    • [ Computer Science ] (47)
      • Web & Network (14)
      • 프로그래밍 이론 (11)
      • 운영체제 (3)
      • 데이터베이스 이론 (5)
      • Linux 리눅스 (7)
    • [ Frontend ] (17)
      • Vue.js & Nuxt.js (9)
      • JSP_Thymeleaf (7)
    • [ 기타 ] (47)
      • 오픈소스 라이브러리 (5)
      • 코딩테스트 (13)
      • Trouble Shooting (7)
      • Tech Interview (6)
      • Book Review (9)
      • 끄적끄적... (5)
      • 개인 프로젝트 (2)

블로그 메뉴

  • 홈
  • 태그
  • github

공지사항

  • GitHub
  • 공부한 내용을 정리하고 기록하는 블로그 입니다.

인기 글

태그

  • MySQL
  • HTTP
  • 자료구조
  • SQL
  • 백엔드기술면접
  • 백엔드스쿨
  • SpringBoot
  • mybatis
  • 리눅스
  • web
  • 클린코드
  • Database
  • cleancode
  • Java
  • TechInterview
  • 개발자
  • 제로베이스
  • vue3
  • springsecurity
  • Redis
  • Linux
  • 기술면접
  • JPA
  • 트랜잭션
  • 백준
  • Nuxt3
  • 백엔드
  • Spring
  • Redisson
  • 백엔드공부

최근 댓글

최근 글

hELLO · Designed By 정상우.
HSRyuuu
[JAVA/자료구조] 트리(Tree), 이진트리(Binary Tree) 란?
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.