[자료구조]트리(Tree)

트리란

나무 뿌리 형태의 자료 구조.

조직도, 수식, 집합, 데이터 탐색에 사용 되는 자료구조.

트리의 용어

단말 : 더 이상 뻗어나가지 않는 마지막 단위

관계 : 부도, 형제, 자식의 계층

깊이 : 루트 노드에서 해당 노드까지의 경로의 길이

레벨 : 깊이가 같은 노드의 집합

높이 : 가장 말단 노드까지의 깊이

차수

노드의 차수 : 해당 노드의 자식 노드 개수

트리의 차수 : 트래 내 노드들 중 자식 노드가 가장 많은 노드

트리의 표현

 - 중첩 된 괄호

 - 중첩 된 집합

 - 들여쓰기

1. 중첩 된 괄호

    

(A(B(C)(D(E)(F)))(G(H))(I(J(K)))

2. 중첩 된 집합

3. 들여 쓰기

노드의 표현

노드의 표현이란 부모와 자식, 형테 노드를 연결 하는 방법

N-링크는 자식 노드의 수가 노드마다 달라지는 트리에 적용하기 어렵습니다.

이를 보완한 방법이 다음 노드의 포인터를 가지고 있는 왼쪽 자식-오른쪽 형제입니다.

 - N-링크

1부터 N까지의 노드를 가진 표현

 - 왼쪽 자식-오른쪽 형제

왼쪽, 오른쪽 포인터로 다음 대상을 표현

이진 트리

루트-왼쪽 하위트리-오른쪽하위트리로 자식이 없거나 하나 혹은 둘이 있는 트리구조

구분

포화 이진 트리 / 완전 이진 트리

포화 이진 트리 : 자식을 둘씩 가지고 있는 트리

완전 이진 트리 : 왼쪽부터 차곡 차곡 자식을 가지고 있는 트리

상태

높이 균형 트리 / 완전 높이 트리 

순회

전위 순회                                중위 순회                                후위 순회

전위 순회 : 루트, 왼쪽 하위 트리, 오른쪽 하위 트리 방향

중위 순회 : 왼쪽 하위 트리, 루트, 오른쪽 하위 트리 방향 -> 대표적으로 수식 트리

후위 순회 : 왼쪽 하위 트리, 오른쪽 하위 트리, 루트 순서 -> 트리 제거 시 사용, 후위표기법

수식 트리

하나의 연산자가 두 개의 피연산자를 가진다는 가정.

1. 피연산자는 잎 노드

2. 연산자는 루트 노드 또는 가지 노드

43-21-+ : 후위 표기법 -> 후위 순회 방식

참고

분리 집합

교집합을 갖지 않는 집합들

서로 공통 된 원소를 갖지 않는 집합.

필드를 생성 하지 않고 특정 상태를 가짐

ex)

남자,여자 데이터 중 군대를 가지 않은 사람들만 뽑고 싶은 상황

군필에 대한 정보는 필드에 존재 하지 않음

군대를 대녀온 사람들을 군필이라는 부모 루트를 바라보게 함

소스

소스가 많아서 깃에 올렸습니다.

복습을 한번 더 해야하는 파트