여기에 스레드 이진 트리 데이터 구조가 표시됩니다. 우리는 바이너리 트리 노드가 최대 두 개의 자식을 가질 수 있다는 것을 알고 있습니다. 그러나 자식이 하나만 있거나 자식이 없는 경우 연결 목록 표현의 링크 부분은 null로 유지됩니다. 스레드 이진 트리 표현을 사용하여 스레드를 만들어 빈 링크를 재사용할 수 있습니다.
한 노드에 왼쪽 또는 오른쪽 자식 영역이 비어 있으면 스레드로 사용됩니다. 스레드 이진 트리에는 두 가지 유형이 있습니다. 단일 스레드 트리 또는 전체 스레드 이진 트리. 단일 스레드 모드에는 또 다른 두 가지 변형이 있습니다. 왼쪽 나사산 및 오른쪽 나사산.
왼쪽 스레드 모드에서 일부 노드에 왼쪽 자식이 없으면 왼쪽 포인터는 순서가 없는 선행 작업을 가리키고 오른쪽 스레드 모드에서는 일부 노드에 오른쪽 자식이 없으면 오른쪽 포인터가 순서 없는 후속 작업을 가리킵니다. 두 경우 모두 후속 작업이나 선행 작업이 없으면 헤더 노드를 가리킵니다.
완전 스레드 이진 트리의 경우 각 노드에는 5개의 필드가 있습니다. 일반 바이너리 트리 노드와 같은 3개의 필드, 해당 면의 링크가 실제 링크인지 스레드인지 여부를 나타내는 부울 값을 저장하는 또 다른 2개의 필드.
| 왼쪽 스레드 플래그 | 왼쪽 링크 | 데이터 | 오른쪽 링크 | 오른쪽 스레드 플래그 |
이것은 왼쪽 및 오른쪽 스레드 트리의 예입니다.
이것은 완전히 스레드된 바이너리 트리입니다.
