순차 자료구조1 [자료구조] 이진 트리 구현 1. 순차 자료구조를 이용한 이진 트리 구현 1) 1차원 배열의 순차 자료구조 사용 높이가 h인 포화 이진 트리의 노드 번호를 배열의 인덱스로 사용 인덱스 0번 : 실제로 사용하지 않고 비워둔다. 인덱스 1번 : 루트 저장 2) 이진 트리의 1차원 배열에서의 인덱스 관계 노드 인덱스 성립 조건 노드 i의 부모 노드 [ i/2 ] 정수로 만듦 (가우스 기호) i > 1 노드 i의 왼쪽 자식 노드 2 * i (2 * i) ≤ n 노드 i의 오른쪽 자식 노드 (2 * i) + 1 (2 * i + 1) ≤ n 루트 노드 1 0 < n 3) 이진 트리의 순차 자료구조 표현 단점 사향(Skewed) 이진 트리의 경우에 사용하지 않는 배열 원소에 대한 메모리 공간 낭비 발생 트리의 원소 삽입, 삭제에 대한 배열의 크.. 2020. 6. 24. 이전 1 다음