방송대 자료구조 8강 : 스레드 트리의 순회와 포인터 활용

방송대 자료구조 8강: 스레드 트리의 순회와 포인터 활용

이진 트리를 중위 순회하다가 한 노드를 방문한 뒤, 다음 노드를 어떻게 곧바로 찾을 수 있을까? 재귀 호출이나 스택 대신 방문 순서를 포인터로 저장한 것이 스레드 트리다. 이 글에서는 포인터가 자식을 가리키는지 순회 후속 노드를 가리키는지 판별하고, 중위 순회·삽입·삭제에서 연결을 안전하게 갱신하는 기준까지 익힌다.

순회의 다음 목적지를 미리 연결하면 되돌아갈 필요가 줄어든다

일반 이진 트리의 전위·중위·후위 순회는 같은 노드를 여러 번 경유한다. 재귀 함수는 호출 기록을 스택에 쌓아 어느 노드로 돌아가야 하는지 기억하고, 비재귀 순회는 별도 스택으로 같은 역할을 수행한다. 스레드 트리는 정해진 순회 순서에서 다음 또는 이전에 방문할 노드의 주소를 노드 안에 기록해 이 보조 경로를 만든다.

스레드는 정해진 순회 방법에 따른 방문 순서를 유지하는 포인터다. 오른쪽 스레드는 현재 노드의 후속 노드를, 왼쪽 스레드는 선행 노드를 가리킨다. 따라서 같은 이진 트리라도 전위·중위·후위 중 어떤 순서를 기준으로 삼았는지에 따라 스레드의 목적지가 달라진다.

첫 판단: 점선 화살표만 보고 스레드를 외우지 않는다. 먼저 기준 순회 순서를 한 줄로 적고, 각 노드의 바로 앞이 선행 노드, 바로 뒤가 후속 노드라고 판정한다.

전위·중위·후위 스레드는 같은 트리를 서로 다르게 잇는다

루트가 +이고 왼쪽 서브트리가 2×3, 오른쪽 자식이 4인 수식 트리를 생각하자. 전위 순회는 +, ×, 2, 3, 4이고 중위 순회는 2, ×, 3, +, 4이며 후위 순회는 2, 3, ×, 4, +다. 예를 들어 노드 3의 오른쪽 스레드는 전위 기준이면 4, 중위 기준이면 +를 가리킨다. 후위 기준에서는 ×가 3의 후속 노드가 된다.

순회 기준	방문 규칙	예시 방문 순서	노드 3의 후속 노드
전위	루트 → 왼쪽 → 오른쪽	+ → × → 2 → 3 → 4	4
중위	왼쪽 → 루트 → 오른쪽	2 → × → 3 → + → 4	+
후위	왼쪽 → 오른쪽 → 루트	2 → 3 → × → 4 → +	×

오개념 교정: 오른쪽 스레드가 언제나 부모를 가리키는 것은 아니다. 중위 순회에서 후속 노드가 조상일 수는 있지만, 순회 순서상 다음 노드가 다른 서브트리에 있으면 그 노드를 가리킨다.

구현 방법은 포인터를 추가할지 빈 포인터를 재활용할지로 갈린다

첫째 방법은 왼쪽·오른쪽 자식 포인터 외에 왼쪽·오른쪽 스레드 포인터를 별도로 두는 것이다. 자식 관계와 순회 관계가 필드 차원에서 분리되어 판별은 단순하지만, 노드마다 포인터 두 개가 추가된다. 강의의 구조를 일관된 C 표기로 옮기면 다음과 같다.

typedef struct thread_node {
    struct thread_node *left;
    struct thread_node *left_thread;
    char data;
    struct thread_node *right;
    struct thread_node *right_thread;
} thread_node;

둘째 방법은 기존 이진 트리 노드의 비어 있는 자식 포인터를 스레드로 재활용한다. 추가 포인터 공간은 줄지만, 그 주소가 실제 자식인지 스레드인지 알려 주는 태그가 필요하다. 특히 삽입·삭제 과정에서 태그를 함께 갱신하지 않으면 순회가 자식 서브트리를 건너뛰거나 스레드를 자식으로 따라가 반복될 수 있다.

구현 방식	노드 구조	장점	주의점
스레드 포인터 추가	자식 2개와 스레드 2개	포인터 역할이 필드로 분리됨	노드마다 추가 기억장소가 필요함
빈 포인터 활용	기존 자식 포인터와 태그	널 포인터 공간을 재사용함	자식·스레드 여부를 반드시 판별함

노드가 n개라면 재활용할 수 있는 널 포인터는 n+1개다

노드가 n개인 이진 트리는 노드마다 왼쪽과 오른쪽 포인터를 하나씩 가지므로 포인터 필드는 모두 2n개다. 루트를 제외한 n−1개 노드는 각각 부모에게서 들어오는 간선 하나를 가지므로, 실제 자식을 가리키는 포인터도 n−1개다. 따라서 비어 있는 포인터 수는 2n−(n−1)=n+1이다.

직접 계산하는 7노드 예

노드가 7개라면 전체 자식 포인터 필드는 14개다. 트리 간선은 7−1=6개이므로 실제 자식을 가리키는 포인터가 6개이고, 남은 널 포인터는 14−6=8개다. 식의 n+1에 7을 넣어도 8이 되어 같은 결과를 얻는다.

계산 순서: 전체 필드 2n → 실제 간선 n−1 → 차이 n+1의 순서로 유도한다. n+1을 단순 암기하면 트리가 아닌 그래프에도 잘못 적용하기 쉽다.

중위 순회는 왼쪽 끝에서 시작해 태그로 다음 행동을 고른다

빈 오른쪽 포인터를 중위 후속 노드의 스레드로 사용하는 구현을 보자. 먼저 루트에서 실제 왼쪽 자식을 계속 따라가 가장 왼쪽 노드를 찾는다. 한 노드를 방문한 뒤 오른쪽 포인터가 스레드라면 그 주소가 곧 후속 노드다. 실제 오른쪽 자식이라면 그 오른쪽 서브트리의 가장 왼쪽 노드가 후속 노드다.

typedef struct thread_node {
    struct thread_node *left;
    char data;
    struct thread_node *right;
    int right_is_thread;
} thread_node;

thread_node *leftmost(thread_node *node) {
    if (node == NULL) return NULL;
    while (node->left != NULL) node = node->left;
    return node;
}

void inorder(thread_node *root) {
    thread_node *node = leftmost(root);
    while (node != NULL) {
        printf("%c", node->data);
        if (node->right_is_thread)
            node = node->right;
        else
            node = leftmost(node->right);
    }
}

leftmost는 서브트리에서 중위 순회의 첫 노드를 찾는다. 순회 본체는 출력 뒤에 두 갈래만 판단한다. 태그가 참이면 오른쪽 주소를 후속 스레드로 사용하고, 거짓이면 오른쪽 자식의 서브트리로 들어가 다시 가장 왼쪽 노드를 찾는다.

잘못된 접근: 오른쪽 주소가 널이 아니라는 이유만으로 항상 오른쪽 자식이라고 판단하면 안 된다. 스레드도 유효한 노드 주소를 담으므로 주소값과 태그를 함께 읽어야 한다.

학습용 트리로 순회 규칙을 한 단계씩 추적한다

루트 M의 왼쪽 자식이 H, 오른쪽 자식이 T이고, H의 오른쪽 자식이 K, T의 왼쪽 자식이 R이라고 가정하자. 중위 순서는 H → K → M → R → T다. H는 실제 오른쪽 자식 K가 있으므로 K 서브트리로 이동한다. K의 오른쪽에는 자식이 없으므로 오른쪽 스레드가 후속 노드 M을 가리킨다.

M은 실제 오른쪽 자식 T를 가지므로 T 서브트리의 가장 왼쪽인 R로 이동한다. R의 오른쪽 스레드는 후속 노드 T를 가리키며, 마지막 T의 후속 노드는 없으므로 순회가 끝난다. 이 예는 오른쪽 포인터의 값만이 아니라 역할 태그가 이동 규칙을 결정한다는 점을 보여 준다.

현재 노드	오른쪽 역할	다음 노드	판단 근거
H	실제 자식 K	K	K 서브트리의 가장 왼쪽 노드
K	스레드	M	중위 후속 노드를 직접 가리킴
M	실제 자식 T	R	T 서브트리의 가장 왼쪽 노드
R	스레드	T	중위 후속 노드를 직접 가리킴
T	후속 노드 없음	종료	마지막 방문 노드임

오른쪽 삽입은 기존 후속 관계를 새 노드가 이어받게 한다

추가 포인터 방식의 중위 스레드 트리에서 노드 X의 오른쪽에 새 노드 Y를 삽입한다고 하자. X가 잎이든 내부 노드든 강의의 핵심 연결 순서는 같다. Y를 X와 X의 기존 오른쪽 부분 사이에 놓고, X가 가지고 있던 중위 후속 관계를 Y가 이어받도록 해야 한다.

1. Y의 왼쪽 자식 포인터를 널로 둔다.
2. Y의 오른쪽 자식 포인터에 X의 기존 오른쪽 자식 주소를 보존한다.
3. Y의 왼쪽 스레드가 선행 노드 X를 가리키게 한다.
4. Y의 오른쪽 스레드가 X의 기존 오른쪽 스레드를 이어받게 한다.
5. X의 오른쪽 자식 포인터가 Y를 가리키게 한다.
6. X의 오른쪽 스레드도 새 후속 노드 Y를 가리키게 한다.

순서의 목적은 주소를 잃지 않는 것이다. 2번과 4번에서 X의 기존 오른쪽 연결을 Y에 보존하기 전에 5번과 6번으로 X의 필드를 덮어쓰면, 원래 오른쪽 서브트리나 후속 노드로 가는 주소를 잃을 수 있다. 삽입 뒤에는 중위 순서에서 X 다음이 Y인지, Y 다음이 원래 X의 후속 노드인지 검산한다.

삽입 검산: 기존 연결 보존 → Y의 선행·후속 연결 → X에서 Y로 연결의 순서로 확인한다. 잎과 내부 노드의 차이는 X의 기존 오른쪽 자식이 비어 있는지 여부이지, 보존해야 한다는 원칙은 같다.

삭제는 자식 수와 스레드 복구를 함께 판단해야 한다

잎 노드는 실제 자식이 없으므로 들어오는 자식 연결을 끊고, 주변 노드의 선행·후속 스레드를 다시 이어 주면 된다. 그러나 내부 노드를 삭제하면 그 자식 서브트리를 어떻게 처리할지 별도 정책이 필요하다. 강의에서는 자식 노드를 모두 삭제하는 방법, 왼쪽 또는 오른쪽 서브트리의 루트를 삭제 위치로 올리는 방법, 잎이 아닌 노드의 삭제를 허용하지 않는 방법을 제시한다.

어떤 정책을 택하더라도 일반 이진 트리의 자식 포인터만 고치고 끝내면 안 된다. 삭제 전후의 중위 방문 순서를 다시 적고, 삭제 노드를 가리키던 선행 노드의 오른쪽 스레드와 후속 노드의 왼쪽 스레드가 새 이웃을 가리키는지 확인해야 한다. 빈 포인터 활용 방식이라면 태그도 새 역할과 일치해야 한다.

삭제 대상	구조 처리	스레드 처리	추가 판단
잎 노드	부모의 자식 연결을 비움	선행·후속 노드를 직접 연결	빈 포인터 활용 방식이면 태그도 변경
자식 하나인 내부 노드	한 서브트리의 루트를 올림	새 중위 이웃에 맞춰 복구	올릴 방향과 부모 연결 확인
자식 둘인 내부 노드	정한 삭제 정책을 적용	변경된 순서 전체를 재검산	삭제 금지 정책도 선택 가능

포인터를 만날 때마다 다섯 가지 질문으로 역할을 결정한다

1. 순회 기준은 무엇인가? 전위·중위·후위 중 하나를 먼저 확정한다.
2. 이 포인터는 자식인가 스레드인가? 별도 필드 방식이면 필드 이름을, 빈 포인터 방식이면 태그를 확인한다.
3. 스레드라면 누구를 가리켜야 하는가? 기준 순서에서 바로 앞 또는 바로 뒤 노드를 찾는다.
4. 연결을 덮어쓰기 전에 보존했는가? 삽입·삭제 전 기존 자식과 선행·후속 주소를 기록한다.
5. 변경 뒤에도 순회가 한 번씩 방문하는가? 처음부터 끝까지 따라가 누락·중복·무한 반복을 검사한다.

자가 점검으로 중위 방문 순서가 P → Q → R이고 Q에 실제 오른쪽 자식이 없다고 하자. Q의 오른쪽 포인터를 스레드로 쓴다면 목적지는 R이고 태그는 스레드 상태여야 한다. 이 주소를 자식으로 오해해 다시 가장 왼쪽으로 내려가려 하면 순회 규칙이 깨진다.

핵심 개념 정리

• 스레드는 정해진 순회 순서의 선행·후속 노드를 가리키는 포인터이며, 스레드 트리는 이를 이용하는 이진 트리다.
• 스레드는 별도 포인터 필드에 저장하거나 기존의 빈 자식 포인터를 태그와 함께 재활용할 수 있다.
• 노드 n개의 이진 트리에는 2n−(n−1)=n+1개의 널 자식 포인터가 있다.
• 중위 순회에서는 가장 왼쪽에서 시작해, 오른쪽이 스레드면 후속 노드로 바로 가고 실제 자식이면 그 서브트리의 가장 왼쪽으로 간다.
• 삽입과 삭제는 자식 연결뿐 아니라 선행·후속 스레드와 태그까지 함께 갱신하고 방문 순서로 검산해야 한다.

전체 판단 흐름: 순회 순서를 먼저 적고 → 각 포인터의 자식·스레드 역할을 판별하고 → 기존 주소를 보존한 뒤 연결을 갱신하고 → 같은 순서로 모든 노드를 한 번씩 방문하는지 확인한다. 이 흐름을 지키면 도식과 코드가 달라도 스레드의 목적지를 스스로 결정할 수 있다.

예상문제 10선

1. 스레드의 의미로 가장 적절한 것은?

① 정해진 순회 순서의 선행 또는 후속 노드를 가리키는 포인터 ② 루트의 깊이를 정수로 저장하는 필드 ③ 모든 잎 노드를 하나의 자식으로 합치는 연산 ④ 노드 데이터를 메모리 주소순으로 정렬하는 규칙

정답입니다.

다시 생각해 보세요.

정답 및 해설 보기

정답: ①

• ① 정답: 스레드는 선택한 순회의 방문 관계를 주소로 유지한다.
• ② 오답: 깊이 정보가 아니라 노드 주소를 저장한다.
• ③ 오답: 트리 구조를 합치는 연산이 아니다.
• ④ 오답: 물리 주소의 크기와 방문 순서는 무관하다.

2. 별도 스레드 포인터 방식과 빈 포인터 활용 방식을 옳게 비교한 것은?

① 두 방식 모두 자식·스레드 판별 정보가 전혀 필요 없다. ② 빈 포인터 방식은 노드마다 스레드 포인터 두 개를 반드시 추가한다. ③ 별도 포인터 방식은 공간이 더 들고, 빈 포인터 방식은 태그 판별이 필요하다. ④ 별도 포인터 방식에서는 자식 포인터를 제거한다.

정답입니다.

다시 생각해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: 재활용 방식은 포인터의 역할을 구분해야 한다.
• ② 오답: 기존의 빈 자식 포인터를 활용하는 방식이다.
• ③ 정답: 두 구현의 핵심 비용과 판별 조건을 정확히 짚었다.
• ④ 오답: 자식 포인터는 트리 구조 유지에 필요하다.

3. 노드가 12개인 이진 트리의 널 자식 포인터 수는?

① 11개 ② 12개 ③ 24개 ④ 13개

정답입니다.

다시 생각해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 11은 실제 간선 수 n−1이다.
• ② 오답: 노드 수와 널 포인터 수는 같지 않다.
• ③ 오답: 24는 전체 포인터 필드 2n이다.
• ④ 정답: 2×12−(12−1)=24−11=13이다.

4. 중위 순서가 H → K → M → R → T이고 K에 실제 오른쪽 자식이 없다. K의 오른쪽 스레드는 누구를 가리켜야 하는가?

① H ② M ③ R ④ T

정답입니다.

다시 생각해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: H는 K의 선행 노드다.
• ② 정답: 오른쪽 스레드는 K 바로 다음인 M을 가리킨다.
• ③ 오답: R은 M 다음에 방문한다.
• ④ 오답: T는 이 순서의 마지막 노드다.

5. 중위 스레드 트리에서 한 노드의 오른쪽 포인터가 실제 자식임을 태그로 확인했다. 다음 행동은?

① 현재 노드의 왼쪽 스레드로 이동한다. ② 순회를 즉시 종료한다. ③ 오른쪽 자식을 후속 노드로 보고 그대로 출력한다. ④ 오른쪽 서브트리로 들어가 가장 왼쪽 노드를 찾는다.

정답입니다.

다시 생각해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 이미 방문한 방향으로 되돌아갈 수 있다.
• ② 오답: 실제 오른쪽 서브트리에 방문할 노드가 남았다.
• ③ 오답: 오른쪽 자식보다 그 서브트리의 왼쪽 노드가 먼저일 수 있다.
• ④ 정답: 중위 순서에서 오른쪽 서브트리의 첫 노드는 가장 왼쪽 노드다.

6. 빈 오른쪽 포인터 활용 방식에서 태그 갱신을 생략한 삽입 코드의 핵심 문제는?

① 같은 주소를 자식 또는 스레드로 잘못 해석해 순회가 깨질 수 있다. ② 모든 노드의 데이터가 자동으로 0이 된다. ③ 이진 트리의 간선 수가 항상 2n개가 된다. ④ 재귀 함수만 사용할 수 있게 된다.

정답입니다.

다시 생각해 보세요.

정답 및 해설 보기

정답: ①

• ① 정답: 주소의 역할을 잘못 판단하면 누락이나 반복 이동이 생긴다.
• ② 오답: 태그는 데이터값을 바꾸지 않는다.
• ③ 오답: 트리의 간선 수 n−1은 변하지 않는다.
• ④ 오답: 태그 누락과 재귀 사용 가능성은 직접 관계가 없다.

7. 같은 수식 트리에서 노드 3의 후속 노드를 옳게 구분한 것은?

① 전위와 중위 모두 +이다. ② 전위와 후위 모두 4이다. ③ 전위에서는 4, 중위에서는 +, 후위에서는 ×이다. ④ 모든 순회에서 후속 노드는 ×이다.

정답입니다.

다시 생각해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: 전위에서 3 다음은 4다.
• ② 오답: 후위에서 3 다음은 ×다.
• ③ 정답: 순회별 방문 순서를 각각 적용한 결과다.
• ④ 오답: 후속 노드는 트리 모양만이 아니라 순회 기준에도 달렸다.

8. X의 오른쪽에 Y를 삽입할 때 연결 손실을 막는 원칙으로 가장 적절한 것은?

① X의 모든 연결을 먼저 널로 바꾼다. ② X의 기존 오른쪽 자식·스레드를 Y에 보존한 뒤 X를 Y에 연결한다. ③ Y의 왼쪽 스레드가 Y 자신을 가리키게 한다. ④ 순회 기준을 바꾸어 기존 주소를 무시한다.

정답입니다.

다시 생각해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: 기존 서브트리와 후속 관계를 잃는다.
• ② 정답: 덮어쓸 주소를 먼저 보존하는 안전한 순서다.
• ③ 오답: Y의 왼쪽 스레드는 선행 노드 X를 가리켜야 한다.
• ④ 오답: 삽입 중 순회 기준을 임의로 바꾸면 스레드 의미가 불일치한다.

9. 내부 노드를 삭제하는 정책으로 강의에서 제시하지 않은 것은?

① 삭제 노드의 주소를 아무 처리 없이 부모와 자식 양쪽에 그대로 둔다. ② 삭제 노드의 자식 노드를 모두 삭제한다. ③ 왼쪽 또는 오른쪽 서브트리의 루트를 삭제 위치로 옮긴다. ④ 잎이 아닌 노드의 삭제를 허용하지 않는다.

정답입니다.

다시 생각해 보세요.

정답 및 해설 보기

정답: ①

• ① 정답: 삭제된 주소를 그대로 참조하면 유효한 삭제 처리가 아니다.
• ② 오답: 강의가 제시한 자식 처리 정책 중 하나다.
• ③ 오답: 한 서브트리의 루트를 올리는 정책도 제시된다.
• ④ 오답: 내부 노드 삭제를 제한하는 정책 역시 제시된다.

10. 스레드 트리 코드를 검토하는 가장 적절한 순서는?

① 데이터 크기순 정렬만 확인하고 포인터 역할은 생략한다. ② 모든 포인터를 스레드로 가정한 뒤 순회를 실행한다. ③ 삽입·삭제 후 루트 값만 같으면 완료로 판단한다. ④ 순회 기준 확정 → 포인터 역할 판별 → 기존 주소 보존 → 연결·태그 갱신 → 전체 방문 검산

정답입니다.

다시 생각해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 스레드 트리의 핵심은 값 정렬이 아니라 방문 관계다.
• ② 오답: 실제 자식 포인터를 스레드로 오해한다.
• ③ 오답: 루트가 같아도 하위 연결이나 스레드가 손상될 수 있다.
• ④ 정답: 의미 결정부터 변경 후 도달성 확인까지 필요한 판단을 모두 포함한다.

참고 자료와 작성 기준

이 글은 방송대 컴퓨터과학과 「자료구조」 8강 ‘스레드 트리’ 강의록을 바탕으로 순회 기준, 구현 방법, 중위 순회와 삽입·삭제 절차를 학습 목적에 맞게 재구성한 비공식 학습자료입니다. 7노드 널 포인터 계산과 H·K·M·R·T 순회 추적은 강의 원리를 연습하도록 직접 구성한 예입니다.

• 작성·편집: 올에이클래스 학습연구팀
• 주요 근거: 방송대 컴퓨터과학과 자료구조 8강 강의록
• 외부 보충 자료: 사용하지 않음
• 편집 원칙: 올에이클래스 편집 정책
• 최종 내용 검토일: 2026년 8월 18일