스레드 이진 트리

일반적으로 해석하는 이진 트리는 내부 스택 혹은 외부 스택을 통해서 순회를 하였다.
BUT 스레드 이진 트리는 스택을 이용하지 않고 포인터를 이용함!

• 중위순회를 기본으로 한다.
• 장점 : 순회를 빠르게 할 수 있음
• 단점 : 스레드를 설정하기 위해 삽입이나 삭제 함수가 더 많은 일을 해야함

기본 개념

1. n개의 노드를 갖는 이진 트리에는 2n개의 링크가 존재
2. 2n개의 링크 중, n + 1개의 링크 값은 null
   • edge 수가 n - 1개이기 때문
   • 루트 노드 제외(-1) 모든 노드가 부모 노드를 향한 edge를 가지고 있음
3. n + 1개의 할당 공간이 아깝다고 생각한 사람들이 n + 1개의 링크에 다른 유용한 정보를 집어 넣자고 생각
4. Null 링크를 다른 노드에 대한 포인터로 대체 (스레드)

스레드 이진 트리는 이렇게 생겼다! 위 그림에서 점선을 스레드라고 함

typedef struct node
{
	bool leftThread; // 왼쪽에 스레드가 형성되었는지
    struct node *leftChild; // 왼쪽 부분이 어떤 노드?
    int data; // 데이터
    struct node *rightChild; // 오른쪽 부분이 어떤 노드?
    bool rightThread; // 오른쪽에 스레드가 형성되어있는지
 }

• 리프 노드는 leftThread 혹은 rightThread가 True로 되어있고
• 자식노드를 연결하고 있는 것들은 leftThread 혹은 rightThread가 F로 되어있다.

스레드는 리프노드에만 적용한다

• 중위 선행자 : 중위 순회를 할 때 현재 노드를 방문하기 전이었던 노드
• 중위 후행자 : 중위 순회를 할 때 현재 노드 다음 순회 할 노드

위 트리를 중위 순회 하면 H->D->I->B->E->A->f->C->G 이다. H의 중위 선행자와 G의 중위 후행자는 없다.

-> 이를 대비하기 위해 스레드 이진 트리에서는 root라는 dummy node 를 만들어 H와 G의 포인팅을 도와준다.

-> 노드의 위치를 잃지 않고 저장하기 위함과 스레드 이진 트리의 정의를 명확히 하기 위해서

참고

https://www.crocus.co.kr/366
https://blog.naver.com/PostView.naver?blogId=boldfaced7&logNo=222261232275&parentCategoryNo=&categoryNo=28&viewDate=&isShowPopularPosts=true&from=search