C 백준 1991 트리 순회 (트리)

 

 

https://www.acmicpc.net/problem/1991

 

---

문제

1. 첫째 줄에 이진 트리 노드 개수 N 입력 (1 <= N <= 26)
2. N개의 줄에 각 노드(루트)와 왼쪽 자식 노드, 오른쪽 자식 노드가 주어짐.
3. 노드의 이름은 알파벳 대문자로 차례대로 매겨짐.
4. A가 항상 루트 노드.
5. 자식 노드가 없는 경우는 . 입력.
6. 전위 순회, 중위 순회, 후위 순회한 각 결과를 알파벳을 공백 없이 출력.
7. 줄 바꿈으로 구분.

---

 

초기 코드

저번에 만들었던 트리 코드를 긁어와 문제에 맞게 수정함
제대로 출력이 되진 않음

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

typedef char elementType;

typedef struct Node {	//노드 구조체 선언
	char data;
	struct Node* leftChild;
	struct Node* rightChild;
}Node;

Node* new_Node(char key) {		//노드 생성하는 함수
	Node* newNode = (Node*)malloc(sizeof(Node)); // 새로운 노드를 동적할당.
	newNode->data = key;
	newNode->leftChild = NULL;
	newNode->rightChild = NULL;

	return newNode; //노드를 가리키는 포인터 반환. 포인터를 반환해야 노드 안의 원소로 접근이 가능.
}


Node* searchNode(Node* root, char key) {	//루트랑 비교하여 값을 찾는 부분
	if (root == NULL) {
		return NULL;
	}
	if (root == key) {
		return root;
	}
	else {
		searchNode(root->leftChild, key);
		searchNode(root->rightChild, key);
	}
}

void preorder(Node* root) { //전위순회
	if (root) {
		printf("%c", root->data);
		preorder(root->leftChild);
		preorder(root->rightChild);
	}
	return;
}

void inorder(Node* root) { //중위순회
	if (root) {
		inorder(root->leftChild);
		printf("%c", root->data);
		inorder(root->rightChild);
	}
	return;
}

void postorder(Node* root) { //후위순회
	if (root) {
		postorder(root->leftChild);
		postorder(root->rightChild);
		printf("%c", root->data);
	}
	return;
}


int main(void) {
	Node* root = NULL;
	int N;
	char R, l, r;

	scanf_s("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf("%c %c %c", &R, &l, &r);
		
		if (R == 'A') {
			root = new_Node(R);
		}
		else {
			searchNode(root, R);
		}

		if (l != '.') {
			root->leftChild = new_Node(l);
		}
		if (r != '.') {
			root->leftChild = new_Node(r);
		}
	}

	preorder(root);
	printf("\n");
	inorder(root);
	printf("\n");
	postorder(root);

	return 0;
}

이전에 썼던 코드에는 insert하는 부분이 있지만 이번 문제에는 크기를 따질 이유가 없기 때문에 해당 부분을 삭제.

대신에

		if (R == 'A') {
			root = new_Node(R);
		}
		else {
			searchNode(root, R);
		}

		if (l != '.') {
			root->leftChild = new_Node(l);
		}
		if (r != '.') {
			root->leftChild = new_Node(r);
		}

메인 코드의 이 부분으로 루트 노드와 왼쪽 자식 노드, 오른쪽 자식 노드 생성.
항상 처음은 루트 노드인 A이므로 처음에는 아무것도 없으므로 그냥 생성하도록 함. 좌 우 자식 노드도 만들어서 추가.

 

마법의 함수 getchar...

이 이후로 제대로 출력해보려고... 이거 저거 해봤음

아!!!!!!!!!!!!!!!!!!! 왜 아무도 나보고 잘못썻다고 말안해줫지... 나 진짜 이거만 2시간 고쳤는데 진짜로... ㅠㅠ... 하... 진짜 뭐가 문젠지 진짜 심각햇는데 그냥...

 

		if (r != '.') {
			root->leftChild = new_Node(r);
		}

 

이거 하나를 못 찾아서... 하... 진짜로 진심으로...? ㅠㅠ... ㅠㅠ...

 

최종 코드

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

typedef char elementType;

typedef struct Node {	//노드 구조체 선언
	char data;
	struct Node* leftChild;
	struct Node* rightChild;
}Node;

Node* new_Node(char key) {		//노드 생성하는 함수
	Node* newNode = (Node*)malloc(sizeof(Node)); // 새로운 노드를 동적할당.
	newNode->data = key;
	newNode->leftChild = NULL;
	newNode->rightChild = NULL;

	return newNode; //노드를 가리키는 포인터 반환. 포인터를 반환해야 노드 안의 원소로 접근이 가능.
}


Node* searchNode(Node* root, char key) {	//루트랑 비교하여 값을 찾는 부분
	if (root== NULL) {
		return NULL;
	}
	if (root -> data == key) {
		return root;
	}
	else {
		Node* temp = searchNode(root->leftChild, key);
		if (temp != NULL) {
			return temp;
		}
		else {
			return searchNode(root->rightChild, key);
		}
	}
}

void preorder(Node* root) { //전위순회
	if (root) {
		printf("%c", root->data);
		preorder(root->leftChild);
		preorder(root->rightChild);
	}
	return;
}

void inorder(Node* root) { //중위순회
	if (root) {
		inorder(root->leftChild);
		printf("%c", root->data);
		inorder(root->rightChild);
	}
	return;
}

void postorder(Node* root) { //후위순회
	if (root) {
		postorder(root->leftChild);
		postorder(root->rightChild);
		printf("%c", root->data);
	}
	return;
}



int main(void) {
	Node* root = NULL;
    Node* start = NULL;

	int N;
	char R, l, r;

	scanf_s("%d", &N);
	getchar();

	for (int i = 0; i < N; i++) {
		scanf("%c %c %c", &R, &l, &r);
		getchar();
		
		if (R == 'A') { // A가 루트로 들어올 때
			root = new_Node(R);
			start = root; // 만들어진 A 노드를 고정할 포인터? 변수? 뭐라고 그러지 아무튼 이거
		}
		else {
			root = searchNode(start, R); // 루트 노드부터 비교하여 찾음(재귀)
		}

		if (l != '.') {
			root->leftChild = new_Node(l);
		}
		if (r != '.') {
			root->rightChild = new_Node(r);
		}
	}

	preorder(start);
	printf("\n");
	inorder(start);
	printf("\n");
	postorder(start);


	return 0;
}

 

[참고] https://velog.io/@wnwjdqkr/%EB%B0%B1%EC%A4%80-1991%EB%B2%88-%ED%8A%B8%EB%A6%AC-%EC%88%9C%ED%9A%8C

 

내 코드 searchNode의 else 부분을 조금 참고함.

 

 

c언어 포인터 구조체는... 아직 적응이 덜 된 것 같음... 좀 더 해봐야 되겠어...