스레드 이진 트리(Threaded Binary Tree)는 이진 트리의 한 종류로, 각 노드의 널 포인터(null pointer)를 활용하여 순회 성능을 개선한 자료구조이다. 일반적인 이진 트리를 연결 리스트로 표현할 경우, n개의 노드에 대해 총 2n개의 링크(각 노드당 왼쪽·오른쪽 자식 포인터) 중 n+1개가 널 포인터가 되어 절반 이상의 공간이 낭비된다. 스레드 이진 트리는 이 널 포인터를 버리지 않고, 가리키는 곳이 없는 모든 오른쪽 널 포인터를 중위 후속자(inorder successor) 노드로 연결하고, 가리키는 곳이 없는 모든 왼쪽 널 포인터를 중위 선행자(inorder predecessor) 노드로 연결하여 재사용한다.
이 구조의 핵심 장점은 재귀 호출이나 별도의 스택 자료구조 없이도 중위 순회(inorder traversal)를 수행할 수 있다는 점이다. 일반적인 이진 트리의 중위 순회는 재귀 함수 호출이나 명시적 스택을 필요로 하여 노드 수가 많아지고 트리 높이가 커질수록 실행 시간 측면에서 비효율적이지만, 스레드 이진 트리는 스레드 링크를 따라 순차적으로 노드를 방문하므로 순회 오버헤드가 줄어든다. 또한 부모 포인터 없이도 특정 노드의 부모를 찾을 수 있어, 스택 공간을 사용할 수 없는 제한된 환경에서 유용하게 사용될 수 있다.
스레드 이진 트리는 구현 시 각 노드의 왼쪽/오른쪽 포인터가 실제 자식 노드를 가리키는지, 아니면 스레드(중위 선행자/후속자)를 가리키는지를 구분하기 위한 플래그(보통 left_thread, right_thread 등의 불리언 값)가 추가로 필요하다. 이러한 구분 플래그가 없다면 스레드와 자식 포인터를 혼동할 수 있다.
이 자료구조는 컴퓨터 과학의 자료구조 분야에서 널리 알려진 개념이며, 특히 이진 트리의 순회 효율성을 높이기 위한 고전적인 기법으로 여러 교과서와 학술 자료에서 다루어지고 있다.
