[백준 5639] 이진 검색 트리

문제 

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

5639번: 이진 검색 트리

 

 

문제 분석 

수를 입력 받아 트리 안에 넣어주고, 그 트리를 후위순회한 결과값을 출력하는 문제이다. 

 

 

알고리즘 설계

Node라는 구조체를 만들어 그 데이터 값, 왼쪽 노드, 오른쪽 노드를 만들어준다. 

 

가장 기본이 되는 rootNode변수를 만든다. 

 

이후 입력을 받으며 처음엔 rootNode에 넣어주고, 처음이 아니라면 Insert함수에 입력 받은 data값과 루트 노드를 넣어준다. 

 

노드의 값과 입력 받은 값을 비교하여 왼쪽에 갈지 오른쪽으로 갈지 정해준다. 만약 각 노드들이 비어있다면 데이터를 넣어주면 되고, 아니면 왼쪽 혹은 오른쪽 노드를 매개변수로 Insert함수에 넣어준다. 

 

이후 후위 순회를 하여 출력해준다. 

 

 

유의점

입력 받는 방법이 백준에서 쓰이는 while(cin >> value)형식이기에 디버깅시 조심하여야한다. 

 

struct를 사용하였는데 값 넣어주거나 노드 연결 시켜줄떄 조심하여 넣어야 한다. 

 

 

코드 

#include <iostream>

using namespace std;

struct Node
{
	int value = NULL;
	Node* left = NULL;
	Node* right = NULL;
};

void Insert(int index, Node* Parent);
void PostorderTraversal(Node& findNode);

int main()
{
	Node rootNode;
	rootNode.value = NULL;
	int input;
	
	while (cin >> input)
	{
		if (rootNode.value == NULL)
			rootNode.value = input;
		else
			Insert(input, &rootNode);
	}
	PostorderTraversal(rootNode);
}

void Insert(int index, Node* parent)
{
	if (parent->value < index)
	{
		if (parent->right == NULL)
		{
			parent->right = new Node;
			parent->right->value = index;
		}
		else
			Insert(index, parent->right);
	}
	else
	{
		if (parent->left == NULL)
		{
			parent->left = new Node;
			parent->left->value = index;
		}
		else
			Insert(index, parent->left);
	}
}

void PostorderTraversal(Node& findNode)
{
	if (findNode.left != NULL)
		PostorderTraversal(*findNode.left);
	if (findNode.right != NULL)
		PostorderTraversal(*findNode.right);
	cout << findNode.value << '\n';
}