트리 이론 기본편 -중위 순회의 특징 응용하기-

1. 이진 탐색 트리의 특징 이진 탐색 트리는 어떠한 경우에도 왼쪽 서브 트리의 루트 루트 > 오른쪽 서브트리 순서대로 순회를 하게 된다. 그렇다면 주어진 이진 트리의 노드를 중위순회한다면, 트리에 넣어야할 데이터의 순서가 주어지며 그러한 순서대로 데이터를 작은 값부터 넣으면 "왼쪽 서브 트리의 루트 2 > 3 > 4 > 5 > ..

• format_list_bulleted 그래프 이론 정복기
• · 2022. 9. 15.
• textsms

트리 이론 기본편2 -이진 트리 용어 + 트리의 순회 -

1. 이진트리 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리 모든 노드들이 자식 노드를 "최대" 2개까지만 가질 수 있는 트리 각 자식 노드를 왼쪽 자식 노드(left child node), 오른쪽 자식 노드(right child node) 이진 트리 예시 4가지.. 모든 노드가 자식 노드를 "최대" 2개만 가지면 이진 트리가 된다 자식 노드가 아예 없어도 된다는 소리 2. 특징 레벨 i에서(높이 i에서) 노드의 최대 개수는 $2^{i}$개 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 h+1개 최대 개수는 $2^{h+1}-1$개 3. 종류 이진트리의 종류에 따라 저장, 표현, 알고리즘 등이 달라질 수 있으므로 잘 구분해야한다 3-1) 포화 이진 트리(full binary tree..

• format_list_bulleted 그래프 이론 정복기
• · 2022. 9. 13.
• textsms