이진트리

이진트리란?

공집합이거나, x가 루트이고 L/R 중 어느것도 x를 포함하지 않는 분리된 이진트리일 때, 삼원소 쌍(x, L, R)

두 서브트리 L/R이 "왼쪽"과 "오른쪽"이라는 이름으로 구분

이진트리의 모든 공백이 아닌 노드는 반드시 왼쪽 서브트리와 오른쪽 서브트리를 가져야 함.

서브트리는 모두 공백 가능

특성
포화 이진트리 크기 = 2^(h+1) - 1
이진트리 크기 범위 : h+1 <= n <= 2^(h+1) - 1
이진트리 높이 : floor(lg(n)) <= h

 

크기가 2인 2개의 이진 트리 : 노드 2개로 나타낼 수 있는 두가지

크기 3인 5개 이진트리

카탈로니아 수 : 이진 트리 개수 세는 데 사용되는 폐쇄형 공식 (2n)!/n!(n+1)!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

수식 트리

수식트리 표현법!

수식트리를 표현한 후, 

이 수식트리를 전위/후위/중위 순회하며 이를 수식으로 나타낼 수 있다.

그런데, 이 수식으로 나타내서, 이를 어떻게 계산하는 것일까.

 

후위 표현식 계산법

 

필요한 것 : 남은 수식, 스택

if 숫자라면 -> 스택에 저장

else(연산자) -> 스택에서 숫자 두 개 꺼내서 연산하고 결과값 스택에 넣기

 

직렬화! 노드에 인덱스 매기기!

현재 노드를 i라고 할 때, 그 부모의 인덱스는 (i-1)/2, 그 자식의 인덱스는 2i+1 & 2i+2

완전 이진 트리의 크기가 n이라고 할 때, 리프는 n/2에서 n-1 까지 번호 매겨짐.

내부 노드는 n/2개, 리프는 (n+1)/2개

 

포리스트

포리스트 : 트리의 집합

순서 포리스트 : 순서 트리의 시퀀스

 

포리스트 -> 이진트리

첫 번째 트리의 루트가 이진트리의 루트

그 자식의 왼쪽 트리부터..

가장 아래 오른쪽 자식을 그 옆 자식의 오른쪽 자식으로 임명

그 위 오른쪽 자식을 그 위 루트노드의 오른쪽 자식으로..

사진보면 이해됨

 

 

출처 : 충남대 김경섭교수님 수업자료