8.10 스레드이진트리 순회 프로그램

//스레드 이진 트리 순회 프로그램
#include <stdio.h>
#define TRUE 1
#define FALSE 0

typedef struct TreeNode {
	int data;
	struct TreeNode* left, * right;
	int is_thread; //만약 오른쪽 링크가 스레드이면 TRUE
}TreeNode;
//      G
//   C     F
// A     B D E
TreeNode n1 = { 'A',NULL,NULL, 1};
TreeNode n2 = { 'B',NULL,NULL, 1};
TreeNode n3 = { 'C',&n1,&n2,0};
TreeNode n4 = { 'D',NULL,NULL,1};
TreeNode n5 = { 'E',NULL,NULL,0 };
TreeNode n6 = { 'F',&n4,&n5, 0};
TreeNode n7 = { 'G',&n3,&n6, 0 };
TreeNode* exp = &n7;

//중위후속자를 반환하는 함수
TreeNode* find_succesor(TreeNode* p)
{
	//q는 p의 오른쪽 포인터
	TreeNode* q = p->right;
	//만약 오른쪽 포인터가 NULL이거나 스레드이면 오른쪽 포인터를 반환
	if (q == NULL || p->is_thread == TRUE)
		return q;

	//만약 오른쪽 자식이면 다시 왼쪽 노드로 이동
	while (q->left != NULL)
		q = q->left;
	return q;
}

//중위 순회를 하는 함수
void thread_inorder(TreeNode* t)
{
	TreeNode* q;

	q = t;
	while (q->left)
		q = q->left; //가장 왼쪽 노드로 간다
	do {
		printf("%c -> ", q -> data);//데이터 출력
		q = find_succesor(q);//중위후속자를 찾는 코드를 호출
	} while (q); //왼쪽자식이 NULL이 아닌 동안
}


int main(void)
{
	//스레드 설정
	n1.right = &n3;
	n2.right = &n7;
	n4.right = &n6;

	//중위순회
	thread_inorder(exp);
	printf("\n");

	return 0;

}