init 3주차 과제 - 트리

1. 과제

백준 트리 1991번 문제

• 문제
• 내가 푼 코드

2. 참고한 사항 / 중요 사항

malloc 메모리 동적 할당으로 배열 만들기

int *arr = (int *)malloc(sizeof(int) *size);

• 입력받은 크기만큼 int 배열을 형성함(실은 입력받은 만큼의 메모리 공간을 할당)
• arr 포인터변수는 배열을 사용하는 것처럼 같은 방법으로 값을 입력하거나 값을 가져올 수 있음.
• malloc은 void 형이므로 형변환 필수!

출처 : https://vitalholic.tistory.com/79

현재 입력받는 노드의 인덱스 변수 만들기

int num;        // 현재 입력받는 노드의 인덱스

for (int i = 0; i < N; i++) {
		getchar();
		char x, y, z;
		scanf("%c %c %c", &x, &y, &z);
		
		num = (int) x - 'A';
		nodes[num].data = x;

		if (y == '.') {
			nodes[num].left = NULL;
		}
		else {
			nodes[num].left = &nodes[y - 'A'];
		}
		
		if (z == '.') {
			nodes[num].right = NULL;
		}
		else {
			nodes[num].right = &nodes[z - 'A'];
		}
}

• 현재 입력받고 있는 노드의 인덱스 값을 따로 변수(num)를 만들어서 저장해두고, 그 값을 활용해 편하게 해당 노드에 접근 가능하게 할 수 있다.

  • 이 인덱스 값은 { (입력받은 노드 문자) - 'A' }값을 통해 몇번째 인덱스인지 쉽게 구할 수 있다!

• left, right 쪽 자식노드가 없을 경우 NULL로 설정한다

• 자식노드가 있을 경우에는 { (해당 자식노드 문자) - 'A' }값을 통해 쉽게 구할 수 있다!

코드 전체적으로 참고한 글 : https://lily-lee.postype.com/post/3147856

3. 전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

typedef struct node* TreeNode;
typedef struct node {
	char data;
	TreeNode left, right;
} node;

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

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

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

int main() {
	int N;
	scanf("%d", &N);

	node *nodes = (node*)malloc(sizeof(node) * N);
	int num;        // 현재 입력받는 노드의 인덱스

	for (int i = 0; i < N; i++) {
		getchar();
		char x, y, z;
		scanf("%c %c %c", &x, &y, &z);
		
		num = (int) x - 'A';
		nodes[num].data = x;

		if (y == '.') {
			nodes[num].left = NULL;
		}
		else {
			nodes[num].left = &nodes[y - 'A'];
		}
		
		if (z == '.') {
			nodes[num].right = NULL;
		}
		else {
			nodes[num].right = &nodes[z - 'A'];
		}
	}

	preorder(&nodes[0]);
	cout << "\n";
	inorder(&nodes[0]);
	cout << "\n";
	postorder(&nodes[0]);
	
	return 0;
}

4. 제출 화면