[자료구조] thread binary tree(쓰레드 이진 트리)

쓰레드라는 표현을 굉장히 자주 들었는데 뭔지는 몰랐었다. 여기서 살펴보고자 한다!

 

binary tree의 링크 표현을 보면, 실제 표현보다 더 많은 null link가 있다고 한다. 이진 트리에는 총 2n개의 링크 중에 n+1개의 null link가 있으니까, 과반수 이상이 놀고있는 링크인 것이다.

 

이것을 안타까워한 어떤 공머생이, null link를 Thread라는, 다른 노드를 가리키는 포인터로 대치하였다고 한다.

규칙은 다음과 같다

 

(1) ptr-> leftChild가 null이면, ptr-> leftChild를 inorder traverse 할 때, ptr 앞에 방문하는 노드에 대한 포인터로 대치한다. 이것은 null link를 ptr의 inorder predecessor에 대한 포인터로 대치하는 것이다.

(2) ptr-> rightChild가 null이면, ptr-> leftChild를 inorder traverse 할 때, ptr 뒤에 방문하는 노드에 대한 포인터로 대치한다. 이것은 null link를 ptr의 inorder successor에 대한 포인터로 대치하는 것이다.

 

thread와 정상적인 포인터를 구별하기 위해서, node구조에 leftThread와 rightThread라는 두개의 필드를 더 첨가해 줬다.

ptr->leftThread = TRUE이면 ptr-> leftChild가 스레드이고, FALSE이면 leftChild가 자식에 대한 포인터인것이다.

 

?? 그럼 2개의 short int 가 더 생기는데 이건 낭비가 아닌가 ???

 

 

 

그리고 분실 thread 문제는 root node를 가르키게 해서 해결했다.