EDWARD EDWARD

이진 트리 : 노드가 left child와 right child만을 갖는 트리를 이진트리(binay tree)라고 한다. 이때 두 자식 가운데 하나 또는 둘 다 존재하지 않는 노드가 있어도 상관없다. 이진 트리의 특징은 왼쪽 자식과 오른쪽 자식을 구분한다는 점이다. 예를 들어 노드 B의 left child는 D이고, right child는 E이다. 또 왼쪽 자식을 루트로 하는 서브 트리를 왼쪽 서브트리(left subtree), 오른쪽 자식을 루트로 하는 서브트리를 오른쪽 서브 트리라고 한다. 완전 이진 트리 루트부터 아래쪽 레벨로 노드가 가득 차 있고, 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져 있는 이진 트리를 완전 이진 트리(complete binary tree)라고 한다. 노드를 채우는 ..

트리의 구조와 관련 용어 트리는 아래의 사진과 같이 노드(node)와 가지(edge)로 구성된다. 각 노드는 가지를 통해 다른 노드와 연결된다. 루트 : 트리의 가장 위쪽에 있는 노드를 루트라고 한다. 루트는 트리 하나에 1개만 존재한다. 리프 : 가장 아래쪽에 있는 노드를 의미한다. 단말 노드(terminal node), 외부 노드(external node)라고도 한다. 물리적으로 가장 밑에 위치한다는 의미가 아니라 가지가 더 이상 뻗어나갈 수 없는 마지막에 노드가 있다는 뜻이다. 비단말 노드(non-terminal node) : 리프를 제외한 노드. 내부 노드(internal node)라고도 한다. 자식 : 어떤 노드와 가지가 연결되었을 때 아래쪽 노드. 노드는 자식을 몇개라도 가질 수 있다. 부모 ..