자료구조 - 스레드 트리

 

스레드 트리

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

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

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

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

 

 

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) 잎만 삭제