8-2. 스레드 트리의 구현

02. 스레드 트리의 구현

- 포인터 필드의 추가 : 스레드를 저장하는 포인터를 추가하는 것

-> 왼쪽 스레드 포인터, 왼쪽 자식 포인터,데이터, 오른쪽 자식 포인터, 오른쪽 스레드 포인터 필드로 노드 구조를 정의함

 

- 오른쪽 스레드 : 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리키고

 

- 왼쪽 스레드 : 그 노드의 선행 노드를 가리킴

// 포인터 필드의 추가

struct TNode {
	int info;
	TNode left;
	TNode right;
	TNode right_thread ;
	TNode left_thread ;		 }

void inorder(struct TNode *firstin){
	struct TNode *p;
	p = firstin ;
	while(p!=NULL){
		printf("%d",p->info);
		p=p->right_thread ;		 }		 }

추가된 포인터 필드를 이용한 중위 순회 연산과정

1. 순회할 트리의 루트 노드를 가리키는 포인터 firstin을 매개변수로 하는 함수의 이름을 inorder()로 합니다.

2. 노드를 가리킬 수 있는 (TNode) 타입의 포인터 p를 생성하고 루트 노드를 가리키도록 합니다.

3. 포인터 p가 가리키는 데이터(info)를 출력하고 p를 p의 오른쪽 스레드 값으로 바꾸어 (p -> right thread) 중위 순회에 따른 다음 노드를 가리키도로 수정.

4. 이 과정을 p가 null이 될 때까지 반복

 

추가된 포인터 필드에 의한 스레드 구현

- 스택을 운영하지 않고도 쉽게 트리에 속한 모든 노드를 순회 할 수 있음

- 하지만 스레드를 위해 추가 기억장소를 사용한다는 부담이 생김

 

스레드의 구현방법(2)

- 노드의 빈 포인터 필드를 활용 : 기존 이진 트리의 노드 구조를 그대로 사용하면서, 노드에 있는 사용하지 않는 포인터를 활용 하는 방법

- 추가 기억장소를 사용하지 않아도 되는 장점이 있음

 

잎 오드의 빈 포인터 필드의 활용

-> 이진 트리의 포인터 갯수( 노드의 개수를 n개라 가정함) :

---> 왼쪽 서브트리를 가리키는 포인터 n개 + 오른쪽 서브트리를 가리키는 n개 = 2n개의 포인터

 

노드의 빈 포인터 필드의 활용

- 루트 노드를 제외한 각 노드 개수는 모두 진입 차수는 '1'이 되므로

- 루트 노드를 제외한 전체 노드 즉, 누군가로부터 가리켜져야 할 노드의 개수 : n-1

- null이 아닌 포인터 개수 : n-1

- 2n - (n-1) = n+1개의 null 포인터가 노드에 존재함

 

- 2n - (n-1) = n+1개의 null 포인터를 스레드로 활용함

 

- 이진 트리의 중위 순회 : 어떤 노드 x에 대해 오른쪽 포인터가 null이면 이 포인터를 x 노드의 다음으로 순회되는 노드(후행노드)를 가리키도록 하고, 왼쪽 포인터가 null이면 x노드의 바로 직전에 순회된 노드를 가리키게 함

 

- 각 노드에 대해 포인터가 스레드로 사용 중인지 아니면 서브트리에 대한 포인터인지를 구분하기 위해 태그 필드가 필요함 ( 삽입/삭제 연산에서 반드시 필요함)

 

전위 순회 : 각 노드의 왼쪽 포인터 필드를 스레드로 사용하는 제한을 가정함

- 어떤 노드의 왼쪽 포인터가 실제 왼쪽 자식을 가리키면 그대로 두고,

- null이면 전위 순회로 순회할 때 다음으로 순회되는 노드를 가리키도록 지정함

 

03. 스레드 트리 순회, 삽입, 삭제

전위 순회 스레드 트리의 전위 순회 연산

void perordthr(struct TFNode *root){
	struct TFNode *p:
    p = root;
    while(p != null){
    printf("%d", p-> info);
    p = p -> left; 		}		}

- 스레드 트리의 노드 삽입 연산 (1)

void Insert(struct Tnode *x, struct Tnode *ttree){
	ttree -> left = NULL;
	ttree -> right = x-> right;
	ttree -> right_thread = x -> right_thread;
	x->right = ttree;
	x->right_thread = ttree;		}

- 스레드 트리의 노드 삽입 연산(2)

void Insert(struct Tnode *x,struct Tnode *ttree)	{
	ttree -> left = NULL;
	ttree -> right = x-> right;
	ttree -> right_thread = x -> right_thread;
	x -> right = ttree;
	x -> right_thread = ttree;	}

스레드 트리의 삭제 연산

스레드 트리의 내부 노드 삭제 : 삭제된 노드의 자식 노드를 처리 방법이 필요함

1. 노드의 자식 노드를 모두 삭제하는 방법

2. 삭제하려는 노드 X의 왼쪽 서브 트리나 오른쪽 서브 트리의 루트를 X가 있던 위치로 옮기는 방법

3. 잎 노드가 아닌 노드를 삭제하지 못하게 하는 것