자료구조 8강 - 스레드 트리의 구현과 순회 연산 이진 트리를 순회할 때 필요한 복귀 정보를 스레드 포인터로 표현하는 원리를 학습합니다. 전위·중위·후위 스레드 트리의 차이, 두 가지 구현 방법, 중위 순회와 삽입·삭제 시 링크 갱신 과정을 단계적으로 정리합니다. 스레드 트리의 개념 순회 과정의 복귀 정보를 포인터로 저장하기 일반 이진 트리를 순회할 때는 방문하지 않은 노드와 되돌아갈 위치를 기억해야 합니다. 재귀 함수는 호출 스택에 이 정보를 저장하고, 반복 방식은 별도 스택을 사용합니다. 스레드 트리(threaded tree)는 순회 순서에 따라 다음에 방문할 노드나 앞서 방문한 노드를 가리키는 스레드 포인터를 추가하여 이 부담을 줄인 이진 트리입니다. 스레드의 뜻 스레드는 정해진 순회 순서에서 선행 노드 또는 후속 노드를 가리키는 포인터입니다. 단순히 임의의 노드를 연결하는 링크가 아니라 방문 순서를 유지하는 연결입니다. 스레드를 이용하면 순회 함수의 재귀 호출이나 명시적 스택 없이도 다음 방문 위치를 찾을 수 있습니다. 대신 노드 구조가 복잡해지거나 자식 링크와 스레드 링크를 구분해야 하며, 삽입과 삭제에서 스레드 관계까지 함께 고쳐야 합니다. 순회 방식에 따른 스레드 트리 스레드는 어떤 순회 순서를 기준으로 만드느냐에 따라 전위·중위·후위 순회 스레드로 구분됩니다. 같은 이진 트리라도 기준 순회가 바뀌면 각 노드의 선행자와 후속자가 달라지므로 스레드 연결도 달라집니다. 종류 방문 순서 스레드가 보존하는 관계 전위 순회 스레드 루트-왼쪽 서브트리-오른쪽 서브트리 전위 순서의 선행자·후속자 중위 순회 스레드 왼쪽 서브트리-루트-오른쪽 서브트리 중위 순서의 선행자·후속자 후위 순회 스레드 왼쪽 서브트리-오른쪽 서브트리-루트 ...