Winwoo's Story

이진 트리

1. 이진 트리의 조건

- root node를 중심으로 두 개의 sub tree로 나뉘어진다.

- 나누어진 두 sub tree도 모두 이진 트리이어야 한다.

※ 트리 그리고 이진 트리는 그 구조가 재귀적이다. 따라서 트리와 관련된 연산은 재귀적 사고와 구현을 할 필요가 있다.

2. 이진 트리와 공집합 노드

- 하나의 노드에 두 개의 노드가 달리는 형태의 트리는 모두 이진 트리이다

- 공집합(Empty set)도 이진 트리에서는 노드로 간주한다.

 -> 그러므로 형제 노드가 비어 있다고 해도 공집합으로 간주하여 이진 트리      가 성립 된다.

3. 이진 트리의 레벨과 높이

- root 노드 부터 0레벨로 시작하고, 아래로 갈수록 레벨이 증가한다.

- 레벨의 최대값과 트리의 높이는 같다.

3. 완전 트리와 포화 트리

- 완전 이진 트리는 위에서 아래로 왼쪽에서 오른쪽으로 채워진 트리를 의미한다.

- 따라서 포화 이진 트리는 동시에 완전 이진 트리이다.

- 하지만 와전 이진 트리는 포화 이진 트리가 될 수 없다.

4. 이진 트리 구현의 두 가지 방법

4_1 배열을 이용한 표현

- 노드에 번호를 부여하고 그 번호를 배열의 인덱스 값으로 활용

- 편의상 배열의 첫 번째 요소는 사용하지 않음

- 트리가 완성 된 이후부터 탐색이 자주 일어날 경우 효율적

4_2 연결리스트를 이용한 표현

- 트리의 구조와 리스트의 연결 구조가 일치한다.

- 구현과 관련된 직관적인 이해가 더 좋은 편

5. 이진 트리 구현 - 노드 구조체 정의

 Javascript에서 Class 상속하기

1. Prototype을 이용한 구조

Tree란?

"개층적 관계(Hierarchical Relationship)를 표현하는 자료구조"

트리의 예

트리의 용어 정리

- 노드(node) : 트리의 구성요소에 해당하는 'A, B, C, D, E, F'와 같은 요소

- 간선(edge) : 노드와 노드를 연결하는 연결선

- 루트 노드(root node) : 트리 구조에서 최상위에 존재하는 'A'와 같은 노드

- 단말 노드(terminal node) : 아래로 또 다른 노드가 연결되어 있지 않은 'E, F, C, D'와 같은 노드

- 내부 노드(internal node) : 단말 노드를 제외한 모든 노드로 'A, B'와 같은 노드

트리의 노드간 관계

- 노드 A는 노드 B, C, D의 부모 노드(parent node)이다.

- 노드 B, C, D는 노드 A의 자식 노드(child node)이다.

- 노드 B, C, D는 부모 노드가 같아, 서로가 서로에게 형제 노드(sibling node)이다.

서브 트리의 이해

서브 트리 역시 서브 트리로 이뤄져 있으며, 그 서브 트리 역시 또 다른 서브 트리로 이뤄져 있다. 

 -> 특징 : 재귀적!

- 하나의 트리를 구성하는 왼쪽과 오른쪽의 작은 트리를 가리켜 서브 트리라 한다.