문과생이 이해한 트리(순회-전위, 중위, 후위)

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

 

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

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

TreeNode n1 = { 1, NULL, NULL };
TreeNode n2 = { 4, &n1, NULL };
TreeNode n3 = { 16, NULL, NULL };
TreeNode n4 = { 25, NULL, NULL };
TreeNode n5 = { 20, &n3, &n4 };
TreeNode n6 = { 15, &n2, &n5 };
TreeNode* root = &n6;

//전위 순회
void preorder(TreeNode* root) {
	if (root != NULL) {
		printf("%d ", root->data);
		preorder(root->left);
		preorder(root->right);
	}
}

//중위 순회
void inorder(TreeNode* root) {
	if (root != NULL) {
		inorder(root->left);
		printf("%d ", root->data);
		inorder(root->right);
	}
}

//후위 순회
void postorder(TreeNode* root) {
	if (root != NULL) {
		postorder(root->left);
		postorder(root->right);
		printf("%d ", root->data);
	}
}

int main() {
	printf("전위 순회=");
	preorder(root);
	printf("\n");

	printf("중위 순회=");
	inorder(root);
	printf("\n");

	printf("후위 순회=");
	postorder(root);
	printf("\n");

	return 0;
}

 

~잠깐 트리 기초~

1. 루트 : 부모가 없는 노드
2. 서브 트리 : 하나의 노드와 그 노드들의 자손들로 이루어진 트리
3. 단말 노드(terminal node) : 자식이 없는 노드
4. 비단말 노드(intermediate node) : 적어도 하나의 자식을 가지는 노드

 

출처 : 강의 자료 쌔빔...

 

 

#초기화

 

 지금 연구실 행사 때문에 없어진 내 자리... 퇴근 시간 어기고 집 간 오빠 자리에서 팀뷰어 키고 하는데. 오빠 visul studio.. 그래픽 바꾸고 싶은데 오빠한테 혼날까봐 하얀 거 보고 하고 있다...ㅜ

 

 일단 트리 구조의 노드들은 전역 변수로 선언하고 초기화 해준다. 

 

 

#main()

 

 트리 ㅎㅏ... 이해 안 돼서 멘탈 나갔던 것들. 일단 중위/전위/후위 순회가 뭔지부터 알아보자

 

 

 부모가 없는 최상위 노드를 root노드라고 한다. 여기서는 1이 root 노드! root의 위치에 따라 전위, 중위, 후위를 가른다고 생각하면 편하다. 

 

- 전위 순회 : root-> 왼쪽 서브트리-> 오른쪽 서브트리

 출력>> (root)1->(왼쪽 서브트리)2->4->5->(오른쪽 서브트리)3

 

-중위 순회 : 왼쪽 서브트리-> root-> 오른쪽 서브트리 

 출력>> (왼쪽 서브트리)4->2->5->(root)1->(오른쪽 서브트리)3

 

-후위 순회 : 왼쪽 서브트리-> 오른쪽 서브트리-> root

 출력>> (왼쪽 서브트리)4->5->2->(오른쪽 서브트리)3->(root)1

 

 

#전위 순회

 

 순환(재귀) 함수를 통해서 트리 구조의 순회를 해보자. 순환 함수는 함수를 호출하고 실행하는 과정에서는 지연 시간이 존재한다. 또, 메모리에 함수 호출을 하면 스택에 쌓이는데 이게 또 프로그램의 성능 저하의 원인이 되기도 한다. 그래서 순환함수가 아닌 반복문을 통해서도 순회가 가능한데, 일단은 순환 함수를 통해서 순회를 해보겠다. 

 

 

 

 일단 저 빨간 네모가 출력될 데이터다. 현재 preorder(root) 함수가 호출되었고 실행 중이다. 그리고 다음 코드에 따라 preorder(root->left) 호출되고 실행된다. 

 

그리고 n2를 인자로 보내 preorder의 *root의 매개변수로 받았으므로 현 함수에서 root는 n2가 된다. 4를 출력하고 또 root->left를 호출하면

 

 요래요래. 지금 root-> left NULL이니까 if문 실행이 안 되고 preorder(n1) 함수는 종료된다. 그럼 n2에서 아래와 같은 함수가 종료된 거다. 

 

 

 

 다음 코드인 preorder(root->right)를 실행하려는데 null이니까 preorder(n2) 함수도 종료된다. 자, 이제 preorder(n6)에서 마찬가지로 위와 같은 코드가 종료되었다. 그리고 root->right인 preorder(n5)를 실행한다. 

 

 

ps. 이제 알았는데 root 숫자는 안 바꾸고 계속 포인터만 바꾸고 있엇다.... 그냥 화살표만 보길 바란다. 

 

이 다음부터는 간단하게 슉슉해서 출력하면은...!!!

 

 

 

 

 요러케 나온다. 나머지 중위랑 후위도, print의 위치만 다를 뿐 다 같은 코드이다. 한 번 손으로.. 해보면 매우 쉬운.. 코드라는 걸 알 수 잇다....ㅜ