자료구조 강의 8화 :: 스레드 트리

자료구조 8화를 듣고 배운내용

 

 

KEYWORDS

• 스레드(thread): 정해진 순회 방법에 따른 방문순서를 유지하는 포인터
  
  
• 스레드 트리: 스레드라는 포인터를 갖는 이진 트리
  
  
• 오른쪽 스레드: 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리킴
  
  
• 왼쪽 스레드: 정해진 순회 순서에 따른 그 노드의 선행 노드를 가리킴
  
  
• 이진 트리의 null 포인터 개수: 2(n - (n - 1) = n + 1

 

 

스레드 트리

이진 트리의 null 포인터를 활용하기 위한 스레드 트리

자식 노드가 없는 노드의 포인터는 null을 갖는다

 

스레드라는 포인터를 추가해서 순회를 편리하게 했다.

스레드를 사용하면 노드를 빨리 찾아다닐 수 있다.

구현이 복잡하고, 추가 기억장소를 사용하는 부담이 있다.

 

 

스레드 트리의 구현 1

• 포인터 필드 추가
  1. 왼쪽 스레드 포인터
  2. 왼쪽 자식 포인터
  3. 데이터
  4. 오른쪽 자식 포인터
  5. 오른쪽 스레드 포인터 필드 노드 구조 필요

왼쪽 스레드

왼쪽 자식 포인터

INFO

오른쪽 자식 포인터

오른쪽 스레드

 

 

스레드 구현 2 - 노드의 빈 포인터 활용

기존 이진 트리의 노드 구조를 그대로 사용,

노드에 사용하지 않는(null) 포인터를 활용

 

전위 순회시 원래 포인터와 스레드가 겹치는 경우가 있다.

왼쪽으로 내려갈 때는 왼쪽 자식 포인터를 따라가고(출력),

따라갈 수 없을 때 비어있는 오른쪽 자식 포인터를 사용