[그림 1]에 있는 트리를 이용하여 노드 E에 대하여 수식을 사용하여 다음을 구하시오.

목차

1. 트리 용어들
2. 이진트리
3. 자료구조 과제

본문내용

1. 트리 용어들
(1) 길이 (Length)란?
출발 노드에서 목적지 노드까지의 노드 갯수를 말합니다. 예를들어 B에서 I로 가는 경로의 길이같은 경우 B에서 F를 거쳐 I에 도착하게 됩니다. (B-> F->I) 여기서 경로의 길이 값은 ‘2’를 가지게 되는데, 쉽게 설명해서 ‘징검다리를 두번 폴짝 뛰어넘으면 도착한다’ 즉 폴짝의 갯수가 길이가 된다고 생각하시면 되겠습니다.

(2) 깊이 (Depth )란?
루트에서 해당 노드 까지의 경로의 길이를 뜻합니다. 즉 위 트리에서 B노드의 깊이는 1이 되며, E노드의 깊이는 2가 됩니다.

(3) 높이란?
가장 깊은 노드와 루트 노드 까지의 길이입니다. 위 트리에서는 A에서 I까지의 길이 즉 3이 되겠습니다.

(4) 레벨이란?
‘깊이’가 갚은 노드 집합을 일컫습니다. 즉 레벨 1에 해당하는 노드 집합은 B, C, D가 되겠습니다.

(5) 차수란?
해당 노드의 자식 노드 갯수를 일컫습니다. 위 트리에서 A노드의 차수는 3, B노드의 차수는 2가 됩니다. 여기서 중요한 것은 트리 전체의 노드인데, 이는 가장 높은 차수를 기준으로 합니다. 즉 A노드의 차수인 3이 되겠습니다.

2. 이진트리
(1) 이진트리의 정의
공백이거나 두 개의 분리된 이진 트리로 구성 된 노드의 유한집합
이진트리란 자식노드가 최대 두 개인 노드들로 구성된 트리입니다.

참고자료

· https://blog.naver.com/mklmkl2001/220828242938
· https://slidesplayer.org/slide/11290967/
· https://jiwondh.github.io/2017/10/15/tree/
· 자료구조 생능출판사 천인국, 공용해
· 자료구조 성안당 권오병 저