[백준 1991] 트리 순회

[문제풀이]

오랜만에 트리 문제를 풀어봤는데,,, 너무 쩔쩔매던 문제였습니다... (개념은 알고 있는데 구현을 못하니..)

주말에 다시 풀어봐야겠습니다.

 

여튼 문제에서는 트리를 구성하고 전위 순회, 중위 순회, 후위 순회를 그대로 출력하면 됩니다.

 

전위 순회는 parent, leftChild, rightChild

중위 순회는 leftChild, parent, rightChild

후위 순회는 leftChild, rightChild, parent

 

Tree의 구성은 node 들도 구성되어 있습니다.

node의 구성은 데이터를 저장할 char와 자식 노드를 가리킬 2개의 포인터를 구성하면 됩니다.

struct Node
{
	char data;
	Node* leftChild;
	Node* rightChild;
};

순회는 위에서부터 아래로 쭉 보기 때문에 반복되는 구문이 필요합니다.

이때 반복은 재귀 형식으로 구현하면 됩니다.

 

전위 순회

void preorder(Node* root)
{
	if (root)
	{
		cout << root->data;
		preorder(root->leftChild);
		preorder(root->rightChild);
	}
}

루트에서 출발해서 자신의 데이터를 출력하고 왼쪽, 오른쪽으로 줄기를 타고 내려갑니다.

만약에 루트가 nullptr이면 종료합니다.

 

중위 순회

void inorder(Node* root)
{
	if (root)
	{
		inorder(root->leftChild);
		cout << root->data;
		inorder(root->rightChild);
	}
}

후위 순회

void postorder(Node* root)
{
	if (root)
	{
		postorder(root->leftChild);
		postorder(root->rightChild);
		cout << root->data;
	}
}

 

입력을 받아서 노드를 구성할 때는 parent, left, right 순으로 데이터가 들어오며 parent는 root를 의미하면서 동시에 데이터이므로 데이터를 저장하고, 이어서 left와 right를 저장합니다.

주의할 점은 '.' 입력이면 자식이 없다는 뜻이므로 무시합니다. '.' 이외의 값이 들어오면 각각 자식 노드를 가리키게 설정해주면 됩니다.

 

출력은 'A' 노드가 항상 루트노드 이므로 root는 'A' 노드를 가리킬 수 있게 합니다.

그런 다음 위에서 구현한 전위, 중위, 후위 순회를 각각 호출하면 됩니다.

#include <iostream>
#include <vector>
using namespace std;

// 자료구조 Tree 구현

struct Node
{
	char data;
	Node* leftChild;
	Node* rightChild;
};

void preorder(Node* root)
{
	if (root)
	{
		cout << root->data;
		preorder(root->leftChild);
		preorder(root->rightChild);
	}
}

void inorder(Node* root)
{
	if (root)
	{
		inorder(root->leftChild);
		cout << root->data;
		inorder(root->rightChild);
	}
}

void postorder(Node* root)
{
	if (root)
	{
		postorder(root->leftChild);
		postorder(root->rightChild);
		cout << root->data;
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	vector<Node*> nodes(26);

	for (int i = 0; i < 26; i++)
	{
		nodes[i] = new Node();
	}
	
	for (int i = 0; i < n; i++)
	{
		char parent, left, right;
		cin >> parent >> left >> right;

		nodes[parent - 'A']->data = parent;

		if (left != '.')
		{
			nodes[parent - 'A']->leftChild = nodes[left - 'A'];
		}

		if (right != '.')
		{
			nodes[parent - 'A']->rightChild = nodes[right - 'A'];
		}
	}

	Node* root = nodes[0];
	preorder(root); cout << endl;
	inorder(root); cout << endl;
	postorder(root); cout << endl;

	return 0;
}