3주차 - 트리 (백준 1991번)

백준 1991번 문제: 트리 순회

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

1991번: 트리 순회

3주차 트리 자료구조 교육에서 배운 것처럼,
구조체를 통해 이진 트리를 구현하고 각 정의에 맞게 코드를 구성하면 된다.

• 전위 순위
  : 루트 노드 방문 -> 왼쪽 서브트리 방문 -> 오른쪽 서브트리 방문
• 중위 순위
  : 왼쪽 서브트리 방문 -> 루트 노드 방문 -> 오른쪽 서브트리 방문
• 후위 순위
  : 왼쪽 서브트리 방문 -> 오른쪽 서브트리 방문 -> 루트 노드 방문

재귀를 사용한 방법, 반복을 사용한 방법으로 구현할 수 있다.

재귀를 사용한 방법은 반복문보다 성능은 떨어지지만 가독성이 높다는 장점이 있다.
따라서 나는 재귀를 사용하여 코드를 구현했다.

처음에 아래와 같이 구조체와 포인트를 활용한 방법(일반적으로 배운 방법)을 통해 구현하려고 했는데,

//하나의 노드 정보를 선언
typedef struct node* TreeNode;
typedef struct node {
    char data;
    TreeNode left, right;
}  node;

//전위 순회 구현
void preorder(TreeNode ptr) {
    if (ptr != NULL) {
        cout << ptr->data; // (1) 자기 자신을 처리 
        preorder(ptr->left); // (2) 왼쪽 방문 
        preorder(ptr->right); // (3) 오른쪽 방문
    }
}

//중위 순회 구현
void inorder(TreeNode ptr) {
    if (ptr != NULL) {
        inorder(ptr->left); // (1) 왼쪽 방문 
        cout << ptr->data; // (2) 자기 자신을 처리 
        inorder(ptr->right);// (3) 오른쪽 방문
    }
}

//후위 순회 구현
void postorder(TreeNode ptr) {
    if (ptr != NULL) {
        postorder(ptr->left); // (1) 왼쪽 방문 
        postorder(ptr->right);// (2) 오른쪽 방문 
        cout << ptr->data; // (3) 자기 자신을 처리
    }
}

main 부분에서 노드를 입력 받는 부분에서 오류를 해결하지 못해서,
구글링을 통해 참고하여 조금 다른 방법으로 구현했다.

---

최종 제출 코드

#include <iostream>
using namespace std;

struct node {
	char left;
	char right;
};

struct node arr[100];

void preorder(char root) {
	if (root == '.') // root가 .이면 상관 없으므로
		return;
	else {
		cout << root;
		preorder(arr[root].left);
		preorder(arr[root].right);
	}
}

void inorder(char root) {
	if (root == '.') // root가 .이면 상관 없으므로
		return;
	else {
		inorder(arr[root].left);
		cout << root;
		inorder(arr[root].right);
	}
}

void postorder(char root) {
	if (root == '.') // root가 .이면 상관 없으므로
		return;
	else {
		postorder(arr[root].left);
		postorder(arr[root].right);
		cout << root;
	}
}

int main() {
	int n;
	cin >> n; // 노드의 개수

	char node, lNode, rNode; // 차례로 입력 받음

	for (int i = 1; i <= n; i++) {
		cin >> node >> lNode >> rNode;
		arr[node].left = lNode;
		arr[node].right = rNode;
	}

	preorder('A');
	cout << endl;
	inorder('A');
	cout << endl;
	postorder('A');
	cout << endl;

	return 0;
}

node 구조체 구현
 => 포인터로 노드를 받지 않고, 구조체에 char타입인 left와 right만 존재한다.

탐색 부분 함수 구현
 => . (즉 단일 노드 일 때)는 구분하여 return만 하고, 그 외의 경우는 위와 같이 각 탐색별 정의에 맞게 탐색한다.

main 함수 구현
노드의 개수는 n으로 입력받고 n만큼 반복해서 순차적으로 3개씩 입력 받는다.
이때 노드, 왼쪽 노드, 오른쪽 노드 순으로 입력 받는 것 이므로 이에 맞게 코드를 구성한다. 

제출 결과