백준 1991 트리 순회 [C++]

문제 링크 : https://www.acmicpc.net/problem/1991

소스코드

#include <iostream>

#include <string>

using namespace std;

class Tree {

    string data;

    Tree *left, *right;

public:

    Tree() { data = ""; left = NULL; right = NULL; }

    void setData(char data) { this->data = data; }

    void setLeft(Tree *left) { this->left = left; }

    void setRight(Tree *right) { this->right = right; }

    void static preorder(Tree *root) { // 전위

        if (root) {

            cout << root->data;

            preorder(root->left);

            preorder(root->right);

        }

    }

    void static inorder(Tree *root) { // 중위

        if (root) {

            inorder(root->left);

            cout << root->data;

            inorder(root->right);

        }

    }

    void static postorder(Tree *root) { // 후위

        if (root) {

            postorder(root->left);

            postorder(root->right);

            cout << root->data;

        }

    }

};

int main() {

    int n;

    cin >> n;

    Tree *tree = new Tree[n];

    for (int i = 0; i < n; ++i) {

        char data,left,right;

        cin >> data>>left>>right;

        if(data!='.')

            tree[(int)(data-'A')].setData(data);

        if (left != '.')

            tree[(int)(data - 'A')].setLeft(&tree[(int)(left - 'A')]);

        else

            tree[(int)(data - 'A')].setLeft(NULL);

        if (right != '.')

            tree[(int)(data - 'A')].setRight(&tree[(int)(right - 'A')]);

        else

            tree[(int)(data - 'A')].setRight(NULL);

    }

    Tree *root = &tree[0];

    //cout << "전위 순회 : ";

    Tree::preorder(root);

    cout << endl;

    //cout << "중위 순회 : ";

    Tree::inorder(root);

    cout << endl;

    //cout << "후위 순회 : ";

    Tree::postorder(root);

    cout << endl;

}

이 문제의 트리는 이진트리입니다.

이진 트리는 한 노드에 왼쪽 자식과 오른쪽 자식이 있는 트리입니다.

전위 순회는 루트노드- 왼쪽 자식- 오른쪽 자식 순서로 방문합니다.

중위 순회는 왼쪽 자식 - 루트 노드 - 오른쪽 자식 순서로 방문합니다.

후위 순회는 왼쪽 자식 - 오른쪽 자식 - 루트 노드 순서로 방문합니다.

예를 들어 전위 순회에서는 루트 노드를 방문 후, 왼쪽 자식이 없을 때 까지 내려갔다가 왼쪽 자식의 끝을 방문하면 다시 올라와 오른쪽 자식을 방문합니다.

Tree 클래스를 만들어 각 알파벳에 해당하는 인덱스에 노드를 만들었습니다.