Fundamentals of Data Structure - Threaded Binary Trees

#Threads

: Threads 란 A.J. Perlis 와 C. Thornton이 고안한 방법으로 Left child와 Right child를 NULL형태로 비효율적이게 낭비하는 것이 아닌 다른 방법으로 쓰이게끔 하는 방법이다. 이 개념은 정해진 규칙이 있다.

첫 번째 : 만약 bt->leftchild가 NULL이라면, Tree를 inorder traversal 했을시 leftchild의 전 Node를 가르키게 한다. 예를 들어, Root가 A이고 B가 A의 Leftchild, C가 A의 Rightchild인 Tree가 있다고 가정하면, C의 LeftChild는 NULL이므로, Threads이용시 이 값은 A를 가르키게 된다.

두 번째 : 만약 bt->rightchild가 NULL이라면, inorder traversal를 적용용하여 rightchild의 후 Node를 가르키게 한다. 앞의 예의 경우 B의 Rightchild는 A를 가르킨다.

세 번째 : 맨 왼쪽 leaf node이거나 맨 오른쪽 leaf node 일 경우 각각 left child 와 right child 는 root를 가르키게 한다. 이 때 root는 실제 root가 아닌 Dummy root로 dummy root의 leftchild에 해당하는 node가 진짜 root 이다. Dummy root의 Rightchild는 자기 자신을 가르킨다. 이렇게 되면 실제 inoder traversal을 했을 시 dummy root의 successor는 다름 아닌 진짜 tree의 맨 왼쪽에 해당하는 leaf Node부터 출력하게된다. 약간 Circular List와 비슷한 느낌.

<Figure 5.23 : Memory representation of threaded tree>

Thread 헤더파일

//
//  ThreadedBT.h
//  Threads
//
//  Created by Skia on 2015. 8. 4..
//  Copyright (c) 2015년 Skia. All rights reserved.
//

#ifndef __Threads__ThreadedBT__
#define __Threads__ThreadedBT__

#include <stdio.h>
#include <stdlib.h>

#define FALSE 0
#define TRUE 1

typedef struct _threadedTree{
    short int leftThread;
    short int rightThread;
    struct _threadedTree* left;
    struct _threadedTree* right;
    char data;
}Thread;

Thread* Tcreate();
Thread* insucc(Thread* tbt);
void Tinorder(Thread* tbt);
void InsertRight(Thread* tbt, Thread* rt);
void InsertLeft(Thread* tbt, Thread* lt);

#endif /* defined(__Threads__ThreadedBT__) */

Thread 함수 정의파일

//
//  ThreadedBT.c
//  Threads
//
//  Created by Skia on 2015. 8. 4..
//  Copyright (c) 2015년 Skia. All rights reserved.
//

#include "ThreadedBT.h"

Thread* Tcreate(){
    Thread* tbt =(Thread*) malloc(sizeof(Thread));
    
    tbt->left = NULL;
    tbt->leftThread = FALSE;
    tbt->right = NULL;
    tbt->rightThread = FALSE;
    
    return tbt;
}

Thread* insucc(Thread* tbt){
    Thread* temp;
    temp = tbt->right;
    
    if(!tbt->rightThread){
        while(!temp->leftThread){
            temp = temp->left;
        }
    }
    
    return temp;
}

void Tinorder(Thread* tbt){
    Thread* temp = tbt;
    
    while(1){
        temp = insucc(temp);
        
        if(temp == tbt){
            break;
        }
        printf("%c ", temp->data);
    }
    
}

void InsertRight(Thread* tbt, Thread* rt){
    Thread* temp;
    
    rt->right = tbt->right;
    rt->rightThread = tbt->rightThread;
    rt->left = tbt;
    rt->leftThread = TRUE;
    tbt->right = rt;
    tbt->rightThread = FALSE; // 여기까지 case a 와 case b가 동일함.
    if(!rt->rightThread){
        temp = insucc(rt);
        temp->left = rt;
    }

}

void InsertLeft(Thread* tbt, Thread* lt){
    Thread* temp;
    
    lt->left = tbt->left;
    lt->leftThread = tbt->leftThread;
    lt->right = tbt;
    lt->rightThread = TRUE;
    tbt->left = lt;
    tbt->leftThread = FALSE;
    if(!lt->leftThread){
        temp = insucc(lt->left);
        temp->right = lt;
    }
}

Thread 테스트 파일

//
//  main.c
//  Threads
//
//  Created by Skia on 2015. 8. 4..
//  Copyright (c) 2015년 Skia. All rights reserved.
//

#include "ThreadedBT.h"

int main(int argc, const char * argv[]) {
    Thread* tbt = Tcreate(); // 첫 데이터가 들어갈 트리
    Thread* root = Tcreate(); // 가상 루트
    Thread* temp;
    Thread* left;
    Thread* right;
    
    root->left = tbt;
    root->leftThread = FALSE;
    root->right = root;
    root->rightThread = FALSE; // root 초기설정
    
    tbt->data = 'A'; // 첫 번째 진짜 root에 데이터 삽입
    tbt->right = root;
    tbt->rightThread = TRUE;
    tbt->left = root;
    tbt->leftThread = TRUE;
    
    temp = Tcreate();
    temp->data = 'B';
    InsertLeft(tbt, temp);
    
    temp = Tcreate();
    temp->data = 'C';
    InsertRight(tbt, temp);
    
    left = tbt->left; // 이 때 left의 data는 B
    
    temp = Tcreate();
    temp->data = 'D';
    InsertLeft(left, temp);
    
    temp = Tcreate();
    temp->data = 'E';
    InsertRight(left, temp);
    
    right = tbt->right; // 이 때 Right의 Data는 C
    
    temp = Tcreate();
    temp->data = 'F';
    InsertLeft(right, temp);
    
    temp = Tcreate();
    temp->data = 'G';
    InsertRight(right, temp);
    
    Tinorder(root);
    
    
    return 0;
}

테스트 결과

D B E A F C G 

1. 책과는 다르게 몇 가지 문제가 되는 부분이 있어서 메인 테스트를 할 때 dummy root의 해당하는 부분과 진짜 root의 값들을 일일이 대입하여 구현하였다. 왜냐하면 처음에 dummy root에 InsertLeft 호출하여 진짜 root(A)를 삽입하니 다소 문제가 발생하였기 때문이다.

3. Insertleft는 책에서 나오지 않아 Exercise에 해당한 내용을 구현한 것이다.