스레드 트리

 

이진 트리의 노드를 순회활 때, 방문하지 않고 지나쳐 온 노드들은 스택에 저장하여 관리해야 하는 번거로움이 발생함

 

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

'스레드' : 순회 방법에 따른 방문순서를 유지하는 포인터

 

 

 

스레드 트리 구현방법

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

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

오른쪽 스레드 : 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리키고

왼쪽  스레드 : 그 노드의 선행 노드를 가리킴

 

추가된 포인터 필드에 의한 스레드 구현

- 스택을 운영하지 않고도 쉽게 트리에 속한 모든 노드를 순회 가능

- 하지만 스레드를 위해 추가 기억장소를 사용한다는 부담

 

2. 노드의 빈 포인터 필드를 활용 : 기존 이진 트리의 노드 구조를 그대로 사용하면서, 노드에 있는 사용하지 않는 포인터를 활용하는 방법

추가 기억장소를 사용하지 않아도 되는 장점이 있음

 

루트 노드를 제외한 각 노드 개수는 모두 진입 차수는 '1'이 되므로,

루트 노드를 제외한 전체 노드 즉, 누군가로부터 가리켜져야 할 노드의 개수 : n-1

null이 아닌 포인터 개수 : n-1

2n - (n-1) = n+1개의 null 포인터가 노드에 존재, 스레드로 활용

 

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

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