[자료구조론] 스레드 이진트리(threaded binary tree)

thread란 실 이란 뜻인데, 아마 실처럼 '연결'되어 있어서 그런게 아닐까..? 생각한다.

 

기존 n개의 노드를 갖는 이진 트리에는 2n개의 링크가 존재한다.

그 중 2n개의 링크 중에 n + 1개의 링크 값은 null이 되는데,

스레드 이진트리는 널 포인터를 이용하여 이진트리를 효율적으로 운행할 수 있다.

 

- 구조

5개의 필드로 이루어져있다.

/

LT와 RT는 불 필드인데 포인터가 스레드 포인터인지, 정상 포인터인지 구별하는 역할을 한다.

struct threaded_tree
 {
  int left_thread; //왼쪽 불 필드
  struct thread_tree *left_child //자기참조구조체
  char data;
  struct thread_tree *right_child
  int right_thread;
  };

 

- 특징

 스택을 이용하지 않고 후속자를 찾을 수 있다.

 널 링크를 이용해 빠른 운행속도를 가진다

 

 

위 그래프를 전위운행(중좌우)시, ABDCEF 순이 되는데, 그때 스레드는 다음과 같이 표현된다.

 

위 그림에는 표현 되지 않았지만 중위운행(좌중우)시, DBAECF가 되는데 그럼 D는 최선행 스레드가 되어 헤드노드를 가르키게 된다.