트리 응용 알고리즘 몇가지 - 자손, 루트, 조상찾기, 서브트리 부분순회 -

1. 완전이진트리 기본 순회 3가지 다음과 같은 완전이진트리에서 전위순회, 중위순회, 후위순회를 구해본다면..? ##노드 번호로 순회함수 정의 ##완전이진트리의 왼쪽 자식은 2*v ##오른쪽 자식은 2*v+1 ##전위순회 def preorder(v): if v

• format_list_bulleted 그래프 이론 정복기
• · 2022. 9. 30.
• 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