99코딩

트리(Tree)

계층적 관계를 표현하는 자료구조이다.

트리의 활용

 - 기업 조직도

 - DBMS

 - 디렉터리 구조

트리 관련 용어

노드(Node): 트리의 구성요소

간선(Edge): 노드와 노드를 연결하는 연결선

루트 노드(Root Node): 트리 구조에서 최상위에 존재하는 노드

단말 노드(Terminal Node): 아래로 또 다른 노드가 연결되어 있지 않은 노드

내부 노드(Internal Node): 단말 노드를 제외한 모든 노드

트리의 종류

이진트리(Binary Tree): 모든 노드가 최대 2개의 서브 노드를 가지는 트리

서브트리(Sub Tree): 기존 트리에서 하위의 트리구조

포화 이진 트리(Full Binary Tree): 트리의 각 레벨에 노드가 가득 차있는 이진트리

완전 이진 트리(Complete Binary Tree): 트리의 마지막 레벨을 제외한 모든 레벨이 가득 차있는 이진트리

이진 탐색 트리(Binary Search Tree):  효율적인 탐색을 위한 이진트리 기반의 자료구조

이진 트리의 추상 자료형

데이터

연산

init(): 초기화

isEmpty(): 비어있는지 확인

createTree(): 이진 트리 생성

getRoot(): 이진 트리의 루트 노드 반환

getCount(): 이진트리의 노드 개수 반환

getLeafCount(): 이친트리의 단말 노드 개수 반환

getHeight(): 이진 트리의 높이 반환