최근 수정:
이진 트리(binary tree)란 한 노드가 최대 두 개의 자식 노드를 가지는 트리를 뜻한다.
보통 첫 번째 노드를 루트 노드라고 하며 자식 노드는 왼쪽(left)과 오른쪽(right)으로 불린다.
이진 트리도 그래프의 일종이므로 그래프와 같은 방식으로 구현이 가능. 하지만 최대 자식이 2개이기 때문에 배열로도 표현이 가능하다.
루트의 인덱스를 1로 했을 때, X 인덱스의 왼쪽 오른쪽 자식의 인덱스는 각각 2*X, 2*X+1로 가능하다. [1]
위에서 봤듯이 구현도 꽤나 간단하고 트리 특유의 효율성[2] 때문에 트리 자료구조 중에서 가장 흔히 쓰인다. 이진 탐색 트리와 이진 힙, 세그먼트 트리 등의 구현에 많이 쓰인다. 자세한 것은 해당 항목 참고.
트리 순회 참고 바람.
[1] 구현에 따라(루트 인덱스를 0으로 하면) 2*X+1, 2*X+2로 할 수 있다.