백준 1991번: 트리 순회

[문제 링크]

1991번: 트리 순회

---

이진트리의 전위순회, 중위순회, 후위순회를 구현하는 문제였다.

이진트리에서 노드는 자식노드를 가지고 있지 않더라도 공집합 노드를 가지고있는 하나의 이진트리라고 볼 수 있기 때문에 별도의 노드 구조체를 정의하지 않고, BTree 클래스를 정의하여 구현하였다.

---

#include <iostream>
using namespace std;

class BTree {
	char data;
	BTree* left;
	BTree* right;
public:
	BTree(char c) : data(c), left(NULL), right(NULL) { }
	
	void makeLeftSubTree(BTree* sub) {
		this->left = sub;
	}

	void makeRightSubTree(BTree* sub) {
		this->right = sub;
	}

	void printData() {
		cout << data;
	}

	BTree* findNode(char c) {
		BTree* node = NULL;

		if (this->data == c)
			node = this;
		if (left != NULL && node == NULL) node = left->findNode(c);
		if (right != NULL && node == NULL) node = right->findNode(c);

		return node;
	}

	void preorder() {
		printData();
		if(left != NULL)  left->preorder();
		if(right != NULL) right->preorder();
	}

	void inorder() {
		if (left != NULL)  left->inorder();
		printData();
		if (right != NULL) right->inorder();
	}

	void postorder() {
		if (left != NULL)  left->postorder();
		if (right != NULL) right->postorder();
		printData();
	}

	void deleteTree() {
		if (left != NULL)
			left->deleteTree();
		if (right != NULL)
			right->deleteTree();

		delete this;
	}
};

int main(void) {
	int N;
	cin >> N;

	BTree* tree = new BTree('A');
	for (int i = 0; i < N; i++) {
		char parent, left, right;
		cin >> parent >> left >> right;

		if (left != '.') {
			BTree* lNode = new BTree(left);
			tree->findNode(parent)->makeLeftSubTree(lNode);
		}
		if (right != '.') {
			BTree* rNode = new BTree(right);
			tree->findNode(parent)->makeRightSubTree(rNode);
		}
	}

	tree->preorder();
	cout << '\n';
	tree->inorder();
	cout << '\n';
	tree->postorder();

	tree->deleteTree();

	return 0;
}