스레드 이진트리

📌 스레드 이진트리

💡 스레드 이진트리(Threaded Binary Tree)

1. 스레드 이진트리의 기본 개념
   1. n개의 노드를 갖는 이진 트리에는 2n 개의 링크가 존재한다.
   2. 2n 개의 링크 중에 n+1 개의 링크 값은 null이다.
   3. null 링크를 다른 노드에 대한 pointer 로 대체한다. (= Threads)
   4. 니는 루트를 제외한 모든 노드는 부모 노드가 있기 때문에 트리의 링크 수는 n-1 개이다.
2. 스레드의 이용
   1. ptr -> left_child = NULL 일 경우, ptr -> left_child 를 ptr의 중위행선자를 가리키도록 변경한다.
      • 중위행선자(inorder predecessor) : 중위 순회에서 현재 노드 바로 앞에 나오는 노드
   2. ptr -> right_child = NULL 일 경우, ptr -> right_child 를 ptr의 중위후속자를 가리키도록 변경한다.
      • 중위후속자(inorder successor) : 중위 순회에서 현재 노드 바로 뒤에 나오는 노드
   3. 노드의 구조

struct thread_tree{
        short int left_thread; # True or False
        struct thread_tree *left_child; # left_child = true : 스레드
                                        # left_child = false : 왼쪽 자식 노드
        char data;
        struct thread_tree *right_child; # right_thread 에 따라 결정된다.
        short int right_thread; # true or false
   }

 

💡 헤드노드(Head Node)

1. 헤드노드의 역할
   1. 가장 왼쪽 노드의 Inorder predecessor
   2. 가장 오른쪽 노드의 Inorder successor

💡 스레드를 이용한 중위순회

1. ptr이 현재 노드를 가리킨다고 가정한다.

   # 중위순회에서 ptr 다음 노드 = ptr -> right_child
   if ptr -> right_thread == TRUE
   
   otherwise
   # ptr 의 right_child 로 이동한 후, left_child 를 따라 내려간다.
   # >> left_thread == TRUE 인 노드를 만날 때까지 내려간다.

1. 중위 후속자 발견 알고리즘(insucc)

   struct thread_tree *insucc(struct thread_tree *ptr){
        # 스레드 이진 트리에서 ptr이 가리키는 노드의 inorder success를 반환
        struct thread_tree *temp = ptr -> right_child;
        
        # right_child 가 자식 노드
        if (!ptr -> right_child){
   
            # 왼쪽 끝에 도달할 때까지 반복한다.
            while(!temp -> left_child){
                temp = temp -> left_child;
            }
        }
        return temp;
   }

💡 중위 순회 알고리즘(tinorder)

   void tinorder(struct thread_tree *tree){
        // 스레드 이진트리를 중위순회, 헤드 노드부터 시작한다.
        struct thread_tree *temp = tree;

        for(;;){
            temp = insucc(temp);
            if(temp==tree){
                break;
            }
            printf("%3c", temp -> data);
        }
   }

💡 스레드 이진트리에서 노드를 추가

1. 문제 정의
   1. 새로운 노드를 parent 노드의 right_child 로 추가한다.
   2. parent -> right_thread 의 값이 true 인 경우
   3. parent -> right_thread 의 값이 false 인 경우