구조
이진 트리(二進-, 영어: binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조이다.
자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.
특징
트리 구조의 가장 큰 특징으로는 재귀적 성질을 갖는다는 것이다.
위 이미지에서 루트 노드인 노드 2의 왼쪽 자식 노드는 노드 7을 루트로 갖는 또 하나의 트리가 된다.
이렇게 만들어진 트리는 부트리(sub tree)라고 부른다.
용어
왼쪽 자식 노드(left child node)는 왼쪽 부트리의 노드이다.
오른쪽 자식 노드(right child node)는 오른쪽 부트리의 노드이다.
부모 노드(parent node)는 그 노드를 자식으로 하는 노드이다.
형제 노드(sibling node)는 부모가 같은 두 노드이다.
차수(degree)는 자식의 수이다.
잎 노드(external/leaf node)는 차수가 0인 노드이다. 즉, 자식이 없는 노드이다.
내부 노드(internal/branch node)는 차수가 0이 아닌 노드이다. 즉, 자식이 있는 노드이다.
방향 간선(directed edge)은 부모 노드가 첫째, 자식 노드가 둘째 원소인 순서쌍이다. 그림의 화살표라고 생각할 수 있다.
경로(path)는 이웃하는 두 노드가 앞이 부모, 뒤가 자식인, 노드의 열이다.
경로의 길이(length)는 경로가 포함하는 방향 간선의 수이다. 특히, 시작점과 출발점이 같은 경로의 길이는 0이다.
노드의 깊이(depth)는 루트 노드에서 자신까지 가는 경로의 길이이다. 특히, 루트 노드의 깊이는 0이다.
노드의 레벨(level)는 루트 노드에서 자신까지 가는 경로의 길이 더하기 1이다. 특히, 루트 노드의 레벨은 1이다. 간혹 트리의 특정 깊이를 가지는 노드의 집합을 레벨이라고 하기도 한다.
노드의 높이(height)는 그 노드와 단말 노드 사이의 경로의 최대 길이이다.
노드의 크기(size)는 자기 자신 및 모든 자손 노드의 수이다.
참고 문서
이진 트리 - 위키백과, 우리 모두의 백과사전 - https://ko.wikipedia.org/wiki/이진_트리