이진 트리는 각 노드가 최대 두 개의 자식 위치를 가지는 트리 자료구조이다. 일반적으로 왼쪽과 오른쪽 자식을 구별한다.
원리
루트에서 노드까지의 경로 길이를 깊이라 하고, 노드에서 가장 먼 잎까지의 경로 길이를 높이라고 한다. 값의 정렬 조건은 이진 트리의 정의에 포함되지 않는다.
예시
산술식 (a+b)×c를 표현할 때 곱셈을 루트에, 덧셈과 c를 자식에 놓을 수 있다. 트리 순회 순서에 따라 다른 표현을 만들 수 있다.
주의할 점
이진 트리가 곧 이진 탐색 트리나 완전 이진 트리는 아니다. 노드 수가 많아도 한쪽으로 길게 늘어지면 높이가 n에 가까워질 수 있다.