[알고리즘] 기본 추상자료형(7) - 설명(트리ADT, 이진트리ADT)

트리ADT는 어떤 단체의 조직구성이나 동식물의 분류체계처럼 맨 위의 대표적 체계(트리)로 시작하여 아래 방향의 가지치기로 표현되는 계층구조를 트리(tree)라고 한다

트리의 용어

루트 - 트리의 맨 위의 부모가 없는 노드

내부노드 - 적어도 한개의 자식을 가진 노드

외부노드 - 자식이 없는 노드

형제 - 같은 부모를 가진 노드

부트리 - 더 작은 트리

경로 - 조상 또는 자손을 따라 이어진 길을 말한다 EX) ABE / ABFK 등등

경로길이 - 경로내 간선의 수를 말한다. EX) ABE(2) / ABFK(3)

깊이 - 루트로부터 그 노드에 이르는 유일한 경로의 길이 EX) J의 깊이 - 3

높이 - 그 노드로부터 외부노드에 이르는 가장 긴 경로의 길이 EX) B의 높이 - 2

트리ADT메소드

1) 일반메소드

boolean isEmpty() - 트리가 비어 있는지 여부를 반환

integer size() - 트리의 노드 수를 반환

2) 접근메소드

node root() - 트리의 루트 위치를 반환

node children(v) - 노드v의 부모노드의 위치를 반환

node children(v) - 노드v의 자식노드들의 위치를 반환

element element(v) - 노드 v에 저장된 원소를 반환

3) 질의메소드

boolean isInternal(v) - 노드v가 내부노드인지 여부를 반환

boolean isExternal(v) - 노드v가 외부노드인지 여부를 반환

boolean isRoot(v) - 노드v가 루트인지 여부를 반환

4) 갱신메소드

swapElements(v, w) - 노드v와 w에 저장된 원소를 교환

element setElement(v, e) - 노드 v에 저장된 원소를 e로 대체

5) 예외메소드

invalidNodeException() - 불법노드(전제하지 않는 노드)에 대한 접근 시 발령

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

이진트리ADT는 두 개의 자식을 가지며 , 각각 왼쪽, 오른쪽 자식을 가지며, 모든 내부노드가 왼쪽, 오른쪽 자식을 가진 이진트리를 적정이진트리라고 부른다

이진트리 속성(n = 이진트리의 노드 수, e = 외부노드의 수, i = 내부 노드의 수, h = 트리의 높이(루트의높이))

이진트리ADT메소드 - 트리ADT의 메소드를 모두 상속 받는다 / 이외의 메소드만 적는다

node leftChild(v) - 노드v의 왼쪽 자식의 위치를 반환

node rightChild(v) - 노드v의 오른쪽 자식의 위치를 반환

node sibling(v) - 노드v의 형제의 위치를 반환

출처

제목: 알고리즘 원리와 응용

저자: 국형준

출판사: 21세기사