자료구조 | Tree

21/08/23 자료구조 및 실습
https://euncero.tistory.com/133
참고하면 좋을 링크

16. Threaded Binary Tree

D-7 ㅠ ㅠ 살 ,,.. 려... 줘...

Threaded Binary Tree

binary를 만들었을 때 child가 없어서 null pointer가 많은 경우가 있는있다. 이때 null들을 버리는 용도로 사용하지 않고, tree를 만들었을 때 inorder traversal 인 경우 효율적으로 사용하기 위한 용도로 만든 것임.

tree를 array가 아닌 링크 리스트로 만들었을 때 놀고 있는 null들을 활용하기 위한 방안으로 사용된다.

thread는 링크라는 것이 left child, right child인거고, 의미있는 데이터들을 가진 노드들을 가리키는 것이었다. 이게 (lc, rc) 만약 존재하지 않는 것이라면, (null 처럼 비어있는게 등장한다면) 내 다음 차례의 노드를 저장하여 사용하는 것이 목적인 것이다.

점선: 다음 노드를 저장하는 용도
실선: process

indorder traversal 일 때

C - D - E - F - A - B - G 순이며
threaded binary tree일 경우,
1. root 노드를 새로 하나 생성
right child는 자기 자신을 가리키게 하고,
left child는 실제 의미있는 데이터가 들어가있는 첫 노드를 가리키게 함.
2. inorder traversal에서 가장 먼저 방문되는 C라는 노드가 root를 가리키게 함.
3. 나머지는 자기 자신의 전임과 후임을 가리키게 함.
4. 맨 마지막에 방문되는 노드의 rightchild 는 root를 가리키게 함.
5. rightc를 따라가다 보면 결과적으로 root로 돌아와서 search가 끝나는 구조로 만들어 판단함.

(얼엽다....^^...)

traversal 순서

// 스레드 이진 트리의 inorder 순회
void tinorder (threadpointer tree)
{
	threadpointer temp = tree;
    for (;;) {
    	temp = insucc(temp);
        if (temp == tree)
        //temp와 tree가 같다는 건 원점으로 다시 돌아왔다는 뜻 - 순회 끝
         break;
        printf("%3c", temp->data);
        	}
        }

//inorder successor 찾는 법

thradedPointer insucc(threadedPointer tree)
{
threadedPointer temp;
temp = tree->rightchild;
if (!tree->rightThread) 
// rigtthread가 false라는 건? 의미있는 데이터를 갖고있는 child를 갖고 있을 때 false임. (실선)
// rightthred가 true라는 건? rightchild가 inorder successor 일 때 
{
	while (!temp->leftThread)
    	temp = temp->leftchild;
        }
        return temp;
}

스레드 바이너리 트리가 만들어지는 과정

right child로 노드를 삽입하는 방법
끝 삽입

중간 삽입