[Data Structure] 스레드 이진 트리

[Data Structure] 스레드 이진 트리

728x90

이진 트리

- 이진 트리에 n개의 노드가 있을 경우

2n개의 링크 존재

2n개의 링크 중, n+1개의 링크 = NULL

2n개의 링크 중, n-1개의 링크 = 다른 노드를 가리킨다

NULL 링크 에 중위 선행자/후속자를 저장 해 놓은 트리 = 스레드 이진 트리

스레드 이진 트리

NULL 링크를 이용해서 순환호출 없이 트리의 노드들을 순회 가능

단말 노드 / 비단말 노드를 구분하기 위해 is_thread 필드 필요

노드의 right를 후속자를 가리키게 설정, is_thread = 1로 설정

typedef struct treenode { char data; struct treenode* left; struct treenode* right; int is_thread; // 1이면 ->right는 중위 후속자, 0이면, ->right는 그냥 오른쪽 자식 가리키는 포인터 }treenode; treenode n1 = {'A', NULL, NULL, 1}; treenode n2 = {'B', NULL, NULL, 1}; treenode n3 = {'D', NULL, NULL, 1}; treenode n4 = {'E', NULL, NULL, 0}; treenode n5 = {'C', &n1;, &n2;, 0}; treenode n6 = {'F' ,&n3;, &n4;, 0}; treenode n7 = {'G', &n5;, &n6;, 0}; treenode* root = &n7; // 스레드 설정 n1.right = &n5; n2.right = &n7; n3.right = &n6;

중위 후속자 반환 함수 find_successor

is_thread = 1 이면, right는 후속자를 가리키고 있는 상태 ∴ 해당 노드의 right 반환

이면, ∴ 해당 노드의 right = NULL이면, 그냥 NULL 반환 (NULL = 해당 노드의 right)

is_thread != 1 이면, 해당 노드에서 서브트리의 가장 왼쪽 노드로 가야 한다

treenode* find_successor(treenode* node) { // 중위 후속자 리턴하는 함수 ( 오른쪽 자식 리턴) treenode* q = node->right; // p = node의 오른쪽 포인터 if (q == NULL || node->is_thread == 1) return q; if (node->is_thread == 0) while (q->left != NULL) q = q->left; return q; }

스레드 이진 트리에서 중위 순회

중위 순회는 LVR순으로 순회 → left가 NULL이 될 때까지 왼쪽 링크를 타고 왼쪽 끝으로 이동

이 다음에 해당 노드의 data를 출력

그리고, find_successor를 호출해서 후속자가 NULL이 아니면 계속 루프 반복

void inorder_thread(treenode* root) { treenode* q; q = root; while (q->left) q = q->left; do { printf("%c -> ", q->data); q = find_successor(q); } while (q); }

728x90

반응형

from http://cs-ssupport.tistory.com/153 by ccl(A) rewrite - 2021-12-14 18:26:56