글 읽기 - 구조체로 트리를 구현했습니다

upsk1 6년 전 0

출력 결과가

ABDCEFG
DBEGFCA
DGFECBA

으로 뜹니다. 제가 구현한 함수대로라면 A가 마지막으로 출력 될수 없는데

무엇이 문제인지 감이 안잡힙니다.

#include <iostream>
using namespace std;
typedef struct Node {
	char data;
	Node* left;
	Node* right;
}node;

void add(node* a, node* b) {
	if (a->left == NULL) {//왼쪽 자식이 없으면 
		a->left = b;
	}
	else {
		node* temp = a->left; //있으면 오른쪽 끝을 찾아가서
		while (temp->right != NULL) {
			temp = temp->right; //자식을 추가
		}
		temp->right = b;
	}
}
void preorder(node* a) { //전위순회 
	cout << a->data;//루트 출력
	if (a->left != NULL)preorder(a->left); //왼쪽 

	if (a->right != NULL)preorder(a->right); //오른쪽
}
void inorder(node* a) {
	if (a->left != NULL)inorder(a->left); //왼쪽

	cout << a->data; //루트출력

	if (a->right != NULL)inorder(a->right);//오른쪽
}
void postorder(node* a) {
	if (a->left != NULL)postorder(a->left); //왼쪽

	if (a->right != NULL)postorder(a->right);//오른쪽

	cout << a->data;//루트출력
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	node a[127];
	char temp1, temp2, temp3;
	int n; cin >> n;
	for (int i = 'A'; i < 'A' + n; i++) {
		a[i].data = i;
		a[i].left = NULL;
		a[i].right = NULL;
	}
	for (int i = 0; i < n; i++) {
		cin >> temp1 >> temp2 >> temp3;
		if (temp2 != '.')add(&a[temp1], &a[temp2]);
		if (temp3 != '.')add(&a[temp1], &a[temp3]);
	}
	preorder(&a['A']);
	cout << '\n';
	inorder(&a['A']);
	cout << '\n';
	postorder(&a['A']);
}

dreamian 6년 전 1

add 함수가 잘못되었습니다.

주어진 예제의 입력에서

A B C를 입력하면

C는 A의 오른쪽 자식인데,

B의 오른쪽 자식으로 저장됩니다.

#include <iostream>
using namespace std;
typedef struct Node {
	char data;
	Node* left;
	Node* right;
}node;

void add(node* a, node* b, bool chk) {
	if (!chk) {//왼쪽 자식이 없으면 
		a->left = b;
	}
	else {
		a->right = b;
	}
}
void preorder(node* a) { //전위순회 
	cout << a->data;//루트 출력
	if (a->left != NULL)preorder(a->left); //왼쪽 

	if (a->right != NULL)preorder(a->right); //오른쪽
}
void inorder(node* a) {
	if (a->left != NULL)inorder(a->left); //왼쪽

	cout << a->data; //루트출력

	if (a->right != NULL)inorder(a->right);//오른쪽
}
void postorder(node* a) {
	if (a->left != NULL)postorder(a->left); //왼쪽

	if (a->right != NULL)postorder(a->right);//오른쪽

	cout << a->data;//루트출력
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	node a[127];
	char temp1, temp2, temp3;
	int n; cin >> n;
	for (int i = 'A'; i < 'A' + n; i++) {
		a[i].data = i;
		a[i].left = NULL;
		a[i].right = NULL;
	}
	for (int i = 0; i < n; i++) {
		cin >> temp1 >> temp2 >> temp3;
		if (temp2 != '.')add(&a[temp1], &a[temp2],false);
		if (temp3 != '.')add(&a[temp1], &a[temp3],true);
	}
	preorder(&a['A']);
	cout << '\n';
	inorder(&a['A']);
	cout << '\n';
	postorder(&a['A']);
}

upsk1 6년 전 0

아 감사합니다 n차 트리랑 헷갈렸었네요

byunghoonpark 5년 전 1

질문이 있습니다. node a[]의 크기가 127로 되어있는데 27로 줄이고 a[65]를 출력했을 때에도 A가 출력이 됩니다.

배열의 크기의 범위를 벗어나는데 어떻게 오류가 나지 않고 출력이 되는 것일까요?

upsk1 5년 전 0

byunghoonpark님 소스를 봤는데 입력받을때는 -65 해서 아스키코드 처리하셨고

출력할때는 a[0]과 포인터를 사용하셔서 문제없이 출력된 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

구조체로 트리를 구현했습니다

upsk1 6년 전 0

dreamian 6년 전 1

upsk1 6년 전 0

byunghoonpark 5년 전 1

upsk1 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말