문과생이 이해한 트리(순회-스레드 이진트리)

출처 : <c언어로 쉽게 풀어쓴 자료구조> + 학교 수업

 

#include<stdio.h>
#define TRUE 1
#define False 0

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

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_successor(TreeNode* p) {
	TreeNode* q = p->right;
	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_successor(q);
	} while (q);
}

int main() {
	n1.right = &n3;
	n2.right = &n7;
	n4.right = &n6;

	thread_inorder(exp);
	printf("\n");

	return 0;
}

 

 으아아아 게으른 자의 최후... 코드 자체는 첨 보는 거라 재밌는데 구현할 게 많넹..?ㅎㅎ

 

 일단 스레드 이진 트리란. 이전의 전위/중위/후위/레벨 순회는 순환함수를 사용하였기 때문에 빠른 순회가 어렵다. 그래서 반복문을 사용하여 속도를 높이는 것이 큰 특징인데 여기서 스레드란...??!! 어떤 프로그램에서 실행되는 흐름의 단위라고(위키백과가 그랬다) 한다. 

 

 이게 뭔 개소리야....

 

 겨수님은.. 

 

 

 

 트리 구조에서 저 빨간 색 선이 스레드라 생각하라 하셨다.. 움... 알듯 말듯... 암튼 일단 코드 해석 ㄱㄱ 

 

 

 

 

 

#main()

 

 일단 트리는 전역변수로 저래 설정되었고, main문의 36,37,38이 스레드 설정 되겠다. 

 

 

 스레드 설정하면 이리 됨.

 

 

#tread_inorder()

 

자 while(q->left) q=q->left를 할껀데. 반복문 조건식에 주소값이 들어가면 NULL이 아니면 true이기 때문에 NULL이 아닐 때까지 반복해보쟈. 그럼 q는 n1까지 가게 된다. 

 

 그러케 'A'가 출력되고 find_succssor()를 호출하게 된다. 

 

 

 

 

#find_successor()

 현재 q는 n1이고, 이 인자값은 find_succesoor의 매개변수 p로 받았다. 대게 복잡한데 그림으로 보면 대충 이런 식. 

 

 

 

일단 q는 NULL이 아니지만 p가 tread이기 때문에 if문을 실행해서 현재 q값인 n3를 리턴한다. 

 

 

#쟈 이제 시작이야

 그럼 또 do-while문을 통해 'C'가 출력된다. 

 이제 이 두개만 열심히 하면 된다. 

 

-'B' 출력

-'G' 출력

 

 여기서 find_succesor 함수가 좀 다르게 작동한다. p가 null도 아니고, q가 tread도 아니라서 if문 실행이 안 되고 while문을 실행하게 된다. 

 

 

 요래 요래. 그래서 전부 출력하면 요렇게 나온다.

 

 

 

 

 이거 교재 코드 그대로 치면서 q랑 p를 엄청 헷갈려서 시간 많이 잡아먹었다.. 특히 

 저기 p->is_thread를 q로 잘못써서 대환장 파티함ㅋㅋㅋㅋㅋ