본문 바로가기
OS & Network

자료구조 - 스레드 트리

by 새발개발JA 2023. 12. 5.
반응형

 

스레드 트리

- 정해진 순회 방법에 따라 방문 순서를 유지하는 스레드라는 포인터를 사용 (스레드 포인터를 갖는 이진트리)

- 스레드는 오른쪽(노드의 후속 노드) / 왼쪽(노드의 선행 노드) 두가지가 있다

- 스레드 없이 순회를 그냥 하게되면 스택에 저장해서 관리해야하는 번거로움이 발생해서 사용하기 시작되었다

- 전위 순회, 중위 순회 , 후위 순회

 

 

2. 스레드 트리 구현

 

 

struct TNode {
    int info;	  // 데이터
    TNode left;   // 왼쪽 자식 포인터
    TNode right; // 오른쪽 자식 포인터
    TNode right_thread; // 왼쪽 스레드 포인터
    TNode left_thread;  // 오른쪽 스레드 포인터 
}

 

 

- 중위 순회 연산

// 루트를 가리키는 포인터(firstin)을 매개벼수로 받는다
void inorder(struct TNode *firstin){
    struct TNode *p; // 포인터 p를 만들고,
    p = firstin;          // 루트노드를 가리킨다

    while (p != NULL){          // 루트가 있으면
        printf("%d", p → info); // p의 데이터를 출력
        p = p → right_thread;   // p를 오른쪽 스레드로 변경
    }
}

 

 

그런데 이렇게 했더니 비는 포인터들이 너무 많아진다 (메모리 낭비)

→ 그래서 포인터가 null 인 친구들만 스레드 노드 값을 넣어주면 빈포인터를 활용할 수 있다

(플래그를 추가해서 자식포인터이면 0, 스레드이면 1)

 

class TFNode {
    int info;           // 데이터
    int threadFlag; // 자식인지 스레드인지 알려주는 flag
    TFNode left;    // 왼쪽 포인터 
    TFNode right;  // 오른쪽 포인터    
}

 

 

이렇게 되면 자연스럽게 자식포인터 따라가다가 포인터가 비게되면

스레드로 대체되서 따라간다. 자연스러운 흐름이 만들어진다

 

**null 포인터의 개수 구하기

노드가 n 개인 이진트리를 연결리스트로 구현할 때 2n-(n-1) = n + 1;

 

 

3. 스레드 트리 순회

다음은 전위순회함수이다

(단순하게 트리를 순회할 때는 threadFlag 를 사용하지 않는다)

 

- 스레드 트리 전위 순회 

// root를 매개변수로 받는다
void Preorder(struct TFNode *root){
	struct TFNode *p; // 포인터 p를 선언
    p = root; 		     // 루트 노드를 넣어준다

    while(p != NULL){ 	     // 루트가 값이 있으면 
    	print("%d", p →  info); // 데이터 출력하고
        p = p → left; 		   // 루트를 왼쪽 서브트리로 하나씩 내린다
    }
}

 

 

- 스레드 트리 노드 삽입

struct TNode {
    int info;	// 데이터
    TNode left;  // 왼쪽 자식 포인터
    TNode right;// 오른쪽 자식 포인터
    TNode right_thread; // 왼쪽 스레드 포인터
    TNode left_thread;   // 오른쪽 스레드 포인터 
}
// 매개변수를 노드prev(직전 노드)와 노드new(삽입할 노드)
void Insert(struct TNode *prev, struct TNode *new){
    new → left = NULL;             // new노드의 왼쪽 포인터를 null
    new → right = prev → right; // new노드의 오른쪽 포인터를 prev노드의 오른쪽으로 
    new → left_thread = prev;   // new노드의 오른쪽 스레드를 x로 지정
    new →  right_thread = prev → right_thread; // new노드의 오른쪽 스레드를 prev의 오른쪽 스레드로 지정
    prev → right = new;             // prev의 오른쪽은 new노드 값으로 
    prev → right_thread = new;  // prev의 오른쪽 스레드 값도 new 노드 값으로 
}

 

 

 

**삭제의 경우 훨씬 복잡하고 까다롭다 

1) 삭제한 노드의 모든 자식 삭제  내부노드를 수시로 삭제해야 한다면 스레드를 포기할수도...

2) 삭제한 노드의 서브트리의 루트를 삭제한 노드의 원래 자리로 이동

3) 잎만 삭제

반응형

댓글