[자료구조] 스레드 트리

스레드트리

• 이진트리의 노드 순회 : 전위, 중위, 후위 순회
• 이진트리의 노드를 순환 함수를 사용하지 않고, 순회할 때, 방문하지 않고 지나쳐 온 노드들은 스택에 저장하여 관리 해야 하는 번거로움이 발생.

→ 스레드라는 포인터를 추가하여 트리 순회를 편리하게 한 것

스레드

• 순회 방법에 따라 방문 순서를 유지하는 포인터

스레드 트리 구현

스레드의 구현 방법 : 포인트 필드의 추가

• 포인터 필드의 추가 : 스레드를 저장하는 포인터를 추가 하는 것

→ 왼쪽 스레드 포인터, 왼쪽 자식 포인터, 데이터, 오른쪽 자식 포인터, 오른쪽 스레드 포인터 필드로 노드 구조를 정의 함

• 오른쪽 스레드 : 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리킨다.
• 왼쪽 스레드 : 그 노드의 선행 노드를 가리킨다.
• 스택을 운영하지 않고도 트리에 속한 모든 노드를 순회 할 수 있다.
• 스레드를 위해 추가 기억장소를 사용한다는 부담이 생긴다.

스레드의 구현방법 : 빈 포인터의 활용

• 노드의 빈 포인터 필드를 활용 : 기존 이진 트리의 노드 구조를 그대로 사용하면서, 노드에 있는 사용하지 않는 포인터(빈 포인터)를 활용 하는 방법
• 추가 기억장소를 사용하지 않아도 되는 장점이 있음
• 어떤 노드 x에 대해 오른쪽 포인터가 null 이면 이 포인터를 노드 x의 후행 노드를 가리키도록 함
• 왼쪽 포인터가 null 이면 노드 x의 선행 노드를 가리키도록 함
• 각 노드에 대해 포인터가 스레드로 사용 중인지 아니면 서브트리에 포인터인지 구분하기 위해 사용여부 태그 필드가 필요함

잎 노드의 빈 포인터 필드의 활용

→ 이진 트리의 포인터 갯수 (노드의 개수를 n개라 가정) : 왼쪽 서브트리를 가리키는 포인터 n개 + 오른쪽 서브트리를 가리키는 n개 → 2n개의 포인터

노드의 빈 포인터 필드를 활용

→ 루트노드를 제외한 각 노드 개수는 모드 진입 차수가 1이므로 루트 제외 가리켜져야 할 노드의 개수 n - 1

→ (각 노드의) NULL 이 아닌 포인터 개수 n-1

→ 2n - (n-1) = n + 1 개의 NULL 포인터가 노드에 존재 함