스레드 트리
스레드 트리를 이야기하기 앞서 배웠던 원형 연결리스트를 떠올려보면 마지막 노드의 링크노드를 첫 노드를 가리키게 해서 순환하게 했다. 결국 스레드 트리도 잎노드에서 빈 공간으로 있는 NULL링크를 활용하는 것이다.
앞서 이진트리를 순회할 때 방문하지 않고 지나 온 노드들은 스택에 저장하여 관리한다. 이는 컴퓨터가 하는 일을 더 많게 하는데 스트레드 트리는 정해진 순회방법에 따른 방문순서를 유지하는 스레드라는 포인터를 사용하는 방법이다.
there : (실등을) 꿰다.
이진트리의 노드 순회는 전위순회, 중위 순회, 후위순회가 있다고 했는데 스레드라는 포인터를 잎노드의 NULL링크에 사용하여 트리순회를 편하게 하는 것이 목적이다.
스레드 : 순회방법에 따라 방문순서를 유지하는 포인터
스레드 트리 구현
1. 스레드의 구현방법 : 포인터 필드의 추가
▶포인터 필드를 추가하는 방법으로 왼쪽스레드포인터, 왼쪽 자식포인터, 데이터 오른쪽자식포인터, 오른쪽 스레드포인터 필드로 노드 구조를 정의한다.
left_thread | *left | data | *right | right_thread |
오른쪽 스레드는 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리키고 왼쪽 스레드는 그 선행노드를 가리킨다.
포인터 필드의 추가
typedef struct tfNode {
struct tfnode *left;
struct tfnode *lthread;
char data;
struct tfnode *right;
struct tfnode *rthread;
} tfnode;
추가된 포인터 필드를 이용한 중위순회 연산
void inorder(tfNode * startNode){
tfNode *ptr;
ptr = startNode;
while(ptr!= NULL) {
printf("% c", ptr → data);
ptr=ptr →rthread;
}}
순회할 트리를 매개변수로 받아야 하는데 스레드는 시작할 노드를 정해줘야 한다. 그럼 루트노드가 아닐 때가 있을 것이다. 중위순회나 후위순회인 경우를 말한다. 그동안 배워왔던 루트노드 기준이었지만 스레드는 다르다.
그래서 * startNode를 매개변수로 받고 inorde를 함수이름으로 한다. 노드를 가리킬 수 있는 tfNode타입의 ptr을 생성하고 시작노드를 가리키도록 한다.
포인터 ptr이 가리키는 데이터를 출력하고 ptr을 ptr의 오른쪽 스레드 값으로 바꾼다( ptr → data) 중위 순회에 따른 다음 노드를 가리키도록 수정한다. 앞서 오른쪽스레드는 정해진 순회순서에 따른 그 노드의 후속노드를 가리킨다고 했다.
포인터 필드의 추가
스택을 운영하지 않고도 트리에 속한 모든 노드를 순회할 수 있다. 하지만 스레드를 위해 추가 기억장소를 사용한다는 부담이 존재한다.
기억해야 할 것은 기존에 스택을 이용했던 루트노드부터 시작했던 것과는 다르게 이 방법은 시작점을 지정을 해야 된다는 점이다.
2. 스레드의 구현방법 : 빈포인터의 활용
◆노드의 빈 포인터 필드를 활용한다. 기존 이진트리의 노드 구조를 그대로 사용하면서 노드에 있는 사용하지 않는 빈 포인터를 활용하는 방법으로 추가적인 기억장소를 사용하지 않아도 되는 장점이 있다.
◆어떤 노드에 대해 오른 포인터가 NULL이면 이 포인터를 노드 X의 후행 노드를 가리키게 하고 왼쪽 포인터가 NULL이면 노드 X의 선행노드를 가리키도록 한다. 이러다 보니 코드가 복잡해진다.
◇결국엔 NULL포인터가 존재하는 거는 잎노드이고 이를 활용하는 것이다. 그리고 노드의 개수를 n개라 하면 이진트리의 포인터 개수는 왼쪽 서브트리를 가리키는 포인터 n개와 오른쪽 서브트리를 가리키는 n개인 2n개의 포인터가 존재한다. 그리고 루트노드를 제외한 각노드의 개수는 모든 진입차수가 1이고 루트노드를 제외한 가리키는 노드의 개수는 n-1이다 그러므로 2n-(n-1)=n+1개의 NULL포인터 개수가 존재한다.
▷전위순회로 예를 들어보면 각 노드의 오른쪽 포인터필드를 스레드로 사용하는 제한을 가정해 보자
√ 어떤 노드의 오른쪽(오른쪽을 쓴다는 가정, 프로그래머가 정한다.) 포인터가 실제 오른쪽 자식을 가리키면 그대로 두고 NULL이면 전위 순회로 순회할 때 다음으로 순회되는 노드를 가르키도로 지정해 보자. 결국에 NULL링크가 없는 것은 프로그램으로 처리한다.
스레드 트리 순회와 삽입, 삭제
중위 순회의 스레드 트리의 중위 순회 연산(빈포인터이용방법)
typedef struct tfNode{
struct tfNode *left;
chat data
struct tfNode *right;
int threadFlag;
} tfNode;
오른쪽 노드를 이용하겠다는 것.
void inore(tfNode *root) {
tfNode *ptr = inorderStart(root); // 처음 가야 하는 노드를 불러온다.
while(ptr!= NULL){
printf("% c", ptr→data);
if(ptr→threadFlag) // 오른쪽 포인터를 스레드로 사용하겠다.
ptr = ptr → right;
else
ptr = inorderStart(ptr → right);}} // 오른쪽 포인터가 스레드가 아닐 때 다시 한번 inorderStart 해서 다시 부분적으로 가야 하는 노드를 찾는다.
tfNode * inorderStart(tfNode *ptr){ // 처음에 inorderStart(root) 루트노드부터 시작해 왼쪽으로 계속 실행시키고 왼쪽이 NULL이 되는 것을 return 한다. //
if(pptr == NULL)
return NULL;
while(ptr → left!=NULL)
ptr = ptr → left;
return ptr; }
중위 순회의 스레드 트리의 삽입연산: 노드 x가 잎노드인 경우
void insert(tfNode *x, tfNode *ttree){
ttree → left = NULL;
ttree → right = x → right;
ttree → lthread = x;
ttree → rthread = x → rthread;
x→right = ttree;
x→rthread= ttree;
중위 순회의 스레드 트리의 삽입연산: 노드 x가 내부 노드인 경우
void insert(tfNode *x, tfNode *ttree){
ttree → left = NULL;
ttree → right = x → right;
ttree → lthread= x;
ttree → rthread = x → rthread;
x → right = ttree;
x → rthread = ttree;}
과정을 보면 삽입되는 노드 U의 포인터를 NULL로 설정하고
삽입되는 노드의 오른쪽 포인터는 노드의 오른쪽 포인터값으로 설정
삽입되는 노드의 왼쪽 스레드포인터가 X를 가리키도록 설정(선행노드를 가리키니)
삽입되는 노드 오른쪽 스레드가 노드 X의 오른쪽 스레드와 같게(x의 원래 후행노드를 가리켜야 하니까)
노드 x의 오른쪽 포인터와 오른쪽 스레드가 삽입되는 노드를 가리키도록 설정
'척척학사 > 자료구조' 카테고리의 다른 글
선택트리,숲,이진트리 개수 ::= 자료구조 (0) | 2023.11.05 |
---|---|
자료구조 힙(heap) (1) | 2023.10.29 |
자료구조 트리 (2) | 2023.10.17 |
연결 리스트의 응용 (1) | 2023.10.06 |
자료구조 연결 리스트 (0) | 2023.09.18 |