[Algorithm] Baekjoon 1991번 : 트리 순회

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

1991번: 트리 순회

struct Node
{
    char name;
    Node* left = nullptr;
    Node* right = nullptr;
};
 
Node* nodes[27];
 
void preOrder(Node* node) // 중 왼 오
{
    if (node == nullptr) return;
 
    cout << node->name;
    preOrder(node->left);
    preOrder(node->right);
}
 
void inOrder(Node* node) // 왼 중 오
{
    if (node == nullptr) return;
 
    inOrder(node->left);
    cout << node->name;
    inOrder(node->right);
}
 
void postOrder(Node* node) // 왼 오 중
{
    if (node == nullptr) return;
 
    postOrder(node->left);
    postOrder(node->right);
    cout << node->name;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    Node* root = new Node({'A'});
    nodes[root->name - 65] = root;
    char parent, left, right;
    
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        cin >> parent >> left >> right;
        
        Node* p = nodes[parent - 65];
 
        if (left != '.')
        {
            nodes[left - 65] = new Node({ left });
            p->left = nodes[left - 65];
        }
 
        if (right != '.')
        {
            nodes[right - 65] = new Node({ right });
            p->right = nodes[right - 65];
        }
    }
 
    preOrder(root);
    cout << endl;
    inOrder(root);
    cout << endl;
    postOrder(root);
}

 

한번쯤은 풀어봤을 트리순회.

무난하게 풀긴했는데, 배열로도 충분히 되는 문제라 코드를 한번 더 짰다.

힙메모리를 안쓰고 해결하면 더 좋으니까..

 

 

int nodes[27][2];
 
void preOrder(char c) // 문자로
{
    if (c == '.') return;
 
    cout << c;
    preOrder(nodes[c - 65][0]);
    preOrder(nodes[c - 65][1]);
}
 
void inOrder(char c)
{
    if (c == '.') return;
 
    inOrder(nodes[c - 65][0]);
    cout << c;
    inOrder(nodes[c - 65][1]);
}
 
void postOrder(char c)
{
    if (c == '.') return;
 
    postOrder(nodes[c - 65][0]);
    postOrder(nodes[c - 65][1]);
    cout << c;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
 
    char parent, left, right;
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        cin >> parent >> left >> right;
 
        nodes[parent - 65][0] = (int)left;
        nodes[parent - 65][1] = (int)right;
    }
 
    preOrder('A'); cout << endl;
    inOrder('A'); cout << endl;
    postOrder('A');
}