컴퓨터과학 자료구조 스레드 트리

스레드 트리

 - 이진 트리의 노드 순회 : 전위 순회, 중위 순회, 후위 순회

 - 이진트리의 노드 순회 시 방문하지 않고 지나친 노드들은 스택에 저장해서 관리해야 하는 번거로움 발생

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

스레드의 구현방법

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

리프노드의 빈 포인터 필드의 활용

 - 이진트리의 포인터 개수는 2n개

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

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

연습문제

1. 스레드 트리에 대한 설명으로 옳은 것? 리프(잎) 노드의 빈 포인터필드를 활용한다.

2. 이진 트리의 노드 개수를 n이라 하면, 리프 노드의 사용하지 않는 포인터 필드의 개수는 모두 몇개인가 ?  n+1

3.  다음 그림의 스레드는 어떤 순회 방식은 무엇인가 ?  (그림 생략) 전위순회