그래프,트리의 정의

그래프(영어: graph)

일련의 꼭짓점(V)들과 그 사이를 잇는 변(E)들로 구성된 구조

트리의 구조 : cycle이 없는 graph

트리 구조(tree 構造, 문화어: 나무구조)란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.

트리에서 최상위 노드를 루트 노드(root node 뿌리 노드[*])라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드[*])라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다

이진 트리의 종류

정이진 트리(Full Binary Tree)
전체 노드의 수가 2^(k-1)개의 노드이고, 레벨 i마다 2^(i-1)개의 노드들로 꽉 찬 트리를 말한다.

전이진 트리(Complete Binary Tree)
전이진 트리는 노드의 수가 n개일 때, 정이진 트리의 각 노드에 붙인 1~n의 일련변호와 1:1로 대응되는 트리, 중간에 빈 부분이 있으면 전이진 트리가 될 수 없다.