[c++] 백준 - 1991: 트리 순회

1991번: 트리 순회 (acmicpc.net)

1991번: 트리 순회

 

C++로 쉽게 풀어쓰는 자료구조' 란 책에 나오는 트리 코드를 참고하여 작성하였습니다. 

#include <iostream>
using namespace std;

class BinaryNode {
protected:
	char data;
	BinaryNode* left;
	BinaryNode* right;
public:
	BinaryNode(char val) : data(val), left(NULL), right(NULL) { }

	void setData(char val) { data = val; }
	void setLeft(BinaryNode* l) { left = l; }
	void setRight(BinaryNode* r) { right = r; }

	char getData() { return data; }
	BinaryNode* getLeft() { return left; }
	BinaryNode* getRight() { return right; }

	void inorder() {
		if (left != NULL) left->inorder();
		if (data != '.') printf("%c", data);
		if (right != NULL) right->inorder();
	}
	void preorder() {
		if (data != '.') printf("%c", data);
		if (left != NULL) left->preorder();
		if (right != NULL) right->preorder();
	}
	void postorder() {
		if (left != NULL) left->postorder();
		if (right != NULL) right->postorder();
		if (data != '.') printf("%c", data);
	}

	BinaryNode* search(char key) {
            if (key == data) return this;
            if (left != nullptr) {
                BinaryNode* result = left->search(key);
                if (result != nullptr) return result;
            }
            if (right != nullptr) {
                BinaryNode* result = right->search(key);
                if (result != nullptr) return result;
            }
            return nullptr;
    }

};

int main() {
	int N; cin >> N; char prn, tmp1, tmp2;
	
	BinaryNode* root = new BinaryNode('A');
	for (int i = 0; i < N; i++) {
		cin >> prn >> tmp1 >> tmp2;
		BinaryNode* tmp = root->search(prn);
		tmp->setLeft(new BinaryNode(tmp1));
		tmp->setRight(new BinaryNode(tmp2));
	}

	root->preorder(); cout << endl;
	root->inorder(); cout << endl;
	root->postorder();


	return 0;
}