쓰레드 이진트리

(중위 순회) 스레드: 오른쪽 자식이 없으면서 마지막 순회할 노드가 아닌 노드 < 왼쪽은 이미 처리되서 순회할 필요가 없으므로 위같이 정의한다 >

스레드인 노드는 right필드에 다음 순회할 노드(중위 후속자)를 삽입한다. find_sucessor메소드를 통해 스레드면 right를 출력하고 스레드가 아니면 받은 노드의 오른쪽 서브 노드를 기준으로 다시 왼쪽으로 쭉 가게 해서 반복한다. (자세한건 책이나 ppt참고)

스레드 덕분에 중위 후속자를 계속 찾을 수 있고 반복적 버전이 가능하다!

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

typedef struct Tree {
	int data;
	struct Tree * left;
	struct Tree * right;
	int is_thread;
}TreeNode;


void insert_right(TreeNode *t, TreeNode *right, int data, int thread) { //right인수는 스레드면 중위 후속자가 전달 됨,아니면 null이 전달
	TreeNode * ptr = (TreeNode *)malloc(sizeof(TreeNode));
	ptr->data = data;
	ptr->right = right;
	ptr->left = NULL;
	ptr->is_thread = thread;
	t->right = ptr;
}

void insert_left(TreeNode *t, TreeNode *right, int data, int thread) { //right인수는 스레드면 중위 후속자가 전달 됨,아니면 null이 전달
	TreeNode * ptr = (TreeNode *)malloc(sizeof(TreeNode));
	ptr->data = data;
	ptr->right = right;
	ptr->left = NULL;
	ptr->is_thread = thread;
	t->left = ptr;
}


TreeNode * find_sucessor(TreeNode *t) {
	TreeNode * tright = t->right;

	if (tright == NULL || t->is_thread == 1)
		return tright;
	else {
		while (tright->left != NULL)
			tright = tright->left;
		return tright;
	}
}

void thread_inorder(TreeNode *t)
{
	TreeNode *r;
	r = t; // 원본 데이터가 손상되지 않게 복사본을 만들어 준 후 작업을 진행한다.
	while (r->left != NULL) r = r->left; // 가장 왼쪽 노드로 이동한다.
	do
	{
		if (r->data == '+' || r->data == '*' || r->data == '/')
			printf("%c ", r->data);
		else
			printf("%d ", r->data);
		r = find_sucessor(r); // 중위후속자를 찾는 함수를 호출한다.
	} while (r != NULL); // 중위후속자가 존재하는 한 계속 무한반복
}

void inorder_rec(TreeNode *t) {
	if (t != NULL) {
		inorder_rec(t->left);
		if (t->data == '+' || t->data == '*' || t->data == '/')
			printf("%c ", t->data);
		else
			printf("%d ", t->data);
		inorder_rec(t->right);
	}
}

TreeNode cons_threadTree(TreeNode * root) {
	// root 노드
	root->data = '+';
	root->is_thread = 0;
	insert_left(root, NULL, '*', 0);
	insert_right(root, NULL, '/', 0);

	// root노드의 왼쪽 서브 트리
	insert_left(root->left, root->left, 3, 1);
	insert_right(root->left, root, 2, 1);

	// root노드의 오른쪽 서브 트리
	insert_left(root->right, root->right, 30, 1);
	insert_right(root->right, NULL, 6, 0);

	return *root;
}

int main() {
	TreeNode T;
	T = cons_threadTree(&T);

	printf("중위 순회의 반복적 버전: ");
	thread_inorder(&T);

}