가라멜의 달달한 세상 탐방

1. 스레드 트리

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

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

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

2. 스레드 트리의 구현

<방법1>

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

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

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

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

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

-> 유지 관리가 힘듬..

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

<방법2>

- 잎 노드의 빈 포인터 필드를 활용