[자료구조] 16. 스레드 이진 트리

1. 스레드 이진 트리

1) 이진 트리의 연결 리스트 표현

• 노드의 구성: 노드들은 데이터 필드와 링크 필드를 가짐.

• NULL 링크 문제: 특정 노드가 자식 노드가 없으면 링크 필드는 NULL이 저장됨.

 

링크 개수 비교:

• n개의 노드로 구성된 이진 트리의 총 링크 개수: 2n개

• 실제 사용되는 링크 개수: n-1개

• 사용되지 않는 NULL 링크 개수: n+1개

 

2) 스레드 이진 트리(Thread Binary Tree)

개념:

• NULL 링크를 다른 노드를 가리키는 포인터로 설정한 이진 트리.

• 자식 노드가 없는 경우, NULL 대신 순회 순서상의 다른 노드를 가리키도록 설정.

 

스레드(Thread)의 역할:

• 트리의 다른 노드를 가리키는 포인터 역할 수행.

• 트리 순회 정보를 유지하는 용도로 활용.

• 순회 방법에 따라 방문 순서를 유지하는 포인터 포함.

• 왼쪽 스레드(선행 노드), 오른쪽 스레드(후속 노드) 존재.

 

태그 필드 사용:

• isThreadLeft: True(왼쪽 링크는 선행 노드를 가리킴), False(왼쪽 링크는 자식 노드를 가리킴)

• isThreadRight: True(오른쪽 링크는 후속 노드를 가리킴), False(오른쪽 링크는 자식 노드를 가리킴)

 

스레드 이진 트리의 노드 정의:

typedef struct TreeNode {
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
    int isThreadLeft;  // 왼쪽 링크가 스레드이면 TRUE
    int isThreadRight; // 오른쪽 링크가 스레드이면 TRUE
} TreeNode;

 

순회 방식 적용:

• 재귀 호출 없이 오른쪽 링크 필드를 이용하여 순회 수행.

• 전위, 중위, 후위 순회 방식 중 선택하여 스레드를 설정.

 

 

2. 트리의 이진 트리 변환

1) 트리의 이진 트리 변환

일반 트리와 차이점:

• 일반 트리는 각 노드가 가변적인 개수의 자식 포인터를 가짐.

• 일반 트리는 자식 노드 개수가 일정하지 않아 구현이 복잡하고 비효율적.

• 이진 트리로 변환하면 기억 공간을 절약하고 자료구조 활용이 용이해짐.

 

특징:

• 모든 일반 트리는 이진 트리로 변환 가능.

 

2) 일반 트리를 이진 트리로 변환하는 과정

변환 과정:

• 각 형제 노드를 수평선으로 연결.

• 부모 노드와 연결된 자식 노드 중, 맨 왼쪽 자식 노드를 제외한 나머지 연결선을 제거.

• 트리를 시계 방향으로 45도 회전하여 이진 트리 형태로 정렬.

 

변환 예시:

• 일반 트리의 노드들이 이진 트리 구조로 재배치됨.

 

---

이 내용은 휴넷사회복지평생교육원의 자료구조 강의를 듣고 정리한 것입니다.