안녕하세요. 오랜만입니다 이번에는 트리에 대해서 알아보도록 합시다
트리 ADT란?
위의 그림처럼 각 트리 원소는 부모원소와 0개 이상의 자식을 가지고 이러한 것을 트리라고 부릅니다.
이러한 트리 ADT에는 다양한 용어가 있습니다
- 루트 : 부모가 없는 노드
- 내부노드 : 적어도 한 개의 자식을 가진 노드
- 외부노드('리프'라고도 부름) : 자식이 없는 노드
- 형제 : 같은 부모를 가진 노드들
- 노드의 조상
- 노드의 자손
- 부트리 : 노드와 그 노드의 자손들로 구성된 트리
- 경로 : 조상 또는 자손을 따라 이어진 노드 시퀀스
- 경로길이 : 경로내 간선의 수
- 노드의 깊이 : 루트로부터 노드에 이르는 유일한 경로의 길이
- 노드의 높이 : 노드로부터 외부노드에 이르는 가장 긴 경로의 길이
- 트리의 높이 : 루트의 높이
이러한 트리 ADT를 응용한다면?
- 직접 응용
- 조직구성도
- 파일시스템
- 프로그래밍 환경
- 간접 응용
- 보조 데이터구조
트리 ADT는 여기까지 살펴보고 이진트리에 대해서 좀 더 알아보는 것이 좋을 것 같습니다.
이진트리 ADT
적정이진트리로 구현하는데 이는 트리의 각 내부노드가 두 개의 자식을 가집니다. 그러나 좌우 자식노드 중에 하나가 비어 있더라도 적정이진트리로 볼 수 있습니다.
이진트리의 성질
- n 노드 수
- e 외부노드 수
- i 내부노드 수
- h 트리의 높이
- e = i + 1
- n = i + e
- h ≤ i
- h ≤ (n - 1)/2
이진트리 ADT 함수
- 깊이
- 높이
- 선위순회
- 후위순회
- 수식 평가
- 중위순회 - O(n)
- 이진트리 그리기
- 수식 인쇄
- 오일러 투어 순회
- 이진트리에 대한 일반순회
- 각 노드 세 번 방문
- 선위, 중위, 후위 모두 포함
- 이진트리내 각 부트리의 노드 수 계산
배열에 기초한 이진트리
- 1D 배열
- 랭크i에 대해
- 왼쪽 자식 2i
- 오른쪽 자식 2i + 1
- 부모 [i/2]
- 링크 저장 불필요
- 순위 0은 미사용
- 비어 있는 셀은 특별값 저장 - # or 널포인터
- 최선의 경우 N = n | 완전이진트리
- 최악의 경우 N = 2^n - 1 | 부적정이진트리
연결리스트에 기초한 이진트리
- 노드 저장내용
- 원소
- 부모노드 (필요 시)
- 왼쪽 자식노드
- 오른쪽 자식노드
