백준 1991. 트리 순회 [실패]

1.실패 원인

기억이 안났다.. 순회 방법은 알고 있었는데 데이터를 어떻게 넣고 조회하는지 기억이 안났다.

다른 블로그들을 보니 구현 방법은 두 가지이다. 2차원 배열을 이용할지 Node 구조체를 통해 함수를 제작할지.

트리를 작성할 때 이진트리가 아닌경우를 대비해서 포인터로 짜는게 좋다고는 알고있었지만 해당 문제는 이진트리로 주어졌기 때문에 배열로 작성하는게 좋아보인다. 더 풀어봐야 알겠지만 알고리즘 문제에서 이진트리를 이용하는 문제들 위주로 나온다면 앞으로 배열을 이용해서 트리구조를 작성할 생각이다.

 

2.작성 코드

#include <iostream>

char tree[26][2];


void preorder(int node) {
	if (node == -1) return;


	std::cout << (char)('A' + node);
	preorder(tree[node][0]);
	preorder(tree[node][1]);
}

void inorder(int node) {
	if (node == -1)return;

	inorder(tree[node][0]);
	std::cout << (char)('A' + node);
	inorder(tree[node][1]);
}

void postorder(int node) {
	if (node == -1)return;
	postorder(tree[node][0]);
	postorder(tree[node][1]);
	std::cout << (char)('A' + node);
}



int main() {

	int n;
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		char a, b, c;
		std::cin >> a >> b >> c;
		if (b != '.')tree[a - 'A'][0] = b-'A'; else tree[a - 'A'][0] = -1;
		if (c != '.')tree[a - 'A'][1] = c-'A'; else tree[a - 'A'][1] = -1;

	}
	preorder(0);
	std::cout << std::endl;
	inorder(0);
	std::cout << std::endl;
	postorder(0);
	std::cout << std::endl;


	return 0;
}

3. 작성 코드2(노드 구조체)

#include <iostream>

struct Node {
	char value;
	Node* left;
	Node* right;
};

// 노드 추가, 노드 조회, 노드 순회법 3가지 , 노드 생성

Node* NewNode(char value) {
	Node* newNode = new Node();
	newNode->value = value;
	newNode->left = nullptr;
	newNode->right = nullptr;
	return newNode;
}

Node* SearchNode(Node* next, char key) {
	if (next == nullptr) return nullptr;
	else {
		if (next->value == key)return next;

		Node* leftNode = SearchNode(next->left, key);
		if (leftNode != nullptr)return leftNode;

		return SearchNode(next->right, key);
	}
	
}

void CreateNode(Node* node ,char data , char left, char right) {

	node->value = data;
	if (left != '.') {
		node->left = NewNode(left);
	}
	if (right != '.') {
		node->right = NewNode(right);
	}
	
}

void PreOrder(Node* node) {
	if (node == nullptr)return;

	std::cout << node->value;
	PreOrder(node->left);
	PreOrder(node->right);
}

void InOrder(Node* node) {
	if (node == nullptr) return;
	
	InOrder(node->left);
	std::cout << node->value;
	InOrder(node->right);
}

void PostOrder(Node* node) {
	if (node == nullptr) return;
	PostOrder(node->left);
	PostOrder(node->right);
	std::cout << node->value;
}


int main() {

	int n;
	Node* Tree =NewNode(NULL);
	Node* tempNode = nullptr;
	std::cin >> n;

	for (int i = 0; i < n; i++) {
		char data, left, right;
		std::cin >> data >> left >> right;
		/*
        	Tree = SearchNode(Tree,data);
            CreateNode(Tree,data,left,right); // 오류!
        */
		tempNode = SearchNode(Tree,data);
		if (tempNode != nullptr) {
			
			CreateNode(tempNode,data, left, right);
		}
		else {
			CreateNode(Tree, data, left, right);
			
		}
		
	}
	PreOrder(Tree);
	std::cout << std::endl;
	InOrder(Tree);
	std::cout << std::endl;
	PostOrder(Tree);
	std::cout << std::endl;
	return 0;
}

 

작성 코드2에서 tempNode를 두는 이유는 딱 한 번 Tree가 nullptr인 경우가 있다. 가장 처음에 트리에 노드를 집어 넣는 경우에 대해서 그런데, tempNode를 사용하지 않는다면 SearchNode에 의해 Tree가 nullptr이 돼서 CreateNode의 매개변수로 nullptr을 넘겨줘서 프로그램이 터져버린다.

 

따라서, 단 한 번의 nullptr 처리를 위해서 tempNode를 두고 어차피 노드들은 포인터로 연결돼있으니 tempNode에 노드의 자식에 다른 노드들이 추가되면 자동으로 같은 포인터를 가리키고 있는 Tree 노드에 Tree가 구성이 되는 것이다.

 

 

4.참고 코드

https://wjdgus2951.tistory.com/51

[백준] 1991번 트리 순회