[트리/구현] BAEKJOON '1991'번 '트리 순회' 문제 (C++/python)

문제 : www.acmicpc.net/problem/1991

1991번: 트리 순회

 

 

 

• 문제 해결 아이디어

    1.  class나 구조체를 사용하여 node를 생성 후, 값들을 저장하고 탐색한다.

   

 

 

• python

 

class Node:
    def __init__(self, data, left_node, right_node):
        self.data = data
        self.left_node = left_node
        self.right_node = right_node

def preorder(node):
    print(node.data, end='')
    if node.left_node != '.':
        preorder(tree[node.left_node])
    if node.right_node != '.':
        preorder(tree[node.right_node])

def inorder(node):
    if node.left_node != '.':
        inorder(tree[node.left_node])

    print(node.data, end='')

    if node.right_node != '.':
        inorder(tree[node.right_node])

def postorder(node):
    if node.left_node != '.':
        postorder(tree[node.left_node])
    if node.right_node != '.':
        postorder(tree[node.right_node])
    print(node.data, end='')

n = int(input())
tree={}    # dictionaray 선언
for i in range(n):
    data, left_node, right_node = input().split()
    tree[data] = Node(data, left_node, right_node)

preorder(tree['A'])
print()
inorder(tree['A'])
print()
postorder(tree['A'])
print()

 

 

• c++

초기에 구조체를 사용하지 않고, dfs를 이용하여 탐색을 시도하였다.

A의 ASCII code값이 65이므로, A를 int로 치환하였을 때, 0으로 바꾸기 위해서 65를 빼고 더해주었다.

dfs를 탐색할 때, 왼쪽이 비어있는 경우, 왼쪽이 비어있지 않은 경우, 오른쪽이 비어있는 경우, 오른쪽이 비어있지 않은 경우, 이렇게  4가지로 나누어 탐색을 진행하였다. 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> preorder;
vector<int> inorder; // 트리를 그렸을 때, x축 기준으로 왼쪽부터 쭉 읽으면 된다.
vector<int> postorder;



void dfs(int start, vector<char> graph[], bool check[]){
    check[start] = true;
    preorder.push_back(start+65);
    
    for(int i=0 ; i< graph[start].size() ; i++){
        
        char next = graph[start][i];
        
        if(next == 'x' && i ==0){
            inorder.push_back(start+65);
            continue;
        }
        
        else if(next == 'x' && i ==1){
            continue;
        }
        
        else if(next != 'x' && i ==0){
            if(check[next-65] == false){
                dfs(next-65, graph, check);
                inorder.push_back(start+65);
            }
        }
        
        else if(next != 'x' && i ==1){
            if(check[next-65] == false){
                dfs(next-65, graph, check);
            }
        }
    }
    postorder.push_back(start+65);
    
}



int main(){
    int nodes;
    string input;
    scanf("%d",&nodes);
    cin.ignore();
    
    vector<char> graph[nodes+1];
    bool check[nodes+1];
    fill(check, check + nodes + 1, false);
    
    for(int i=0 ; i< nodes ; i++){
        getline(cin, input);
        char tmp = input[0];
        
        if(input[2] == '.'){
            graph[tmp-65].push_back('x');
        }
        else{
            graph[tmp-65].push_back(input[2]);
        }
        
        if(input[4] == '.'){
            graph[tmp-65].push_back('x');
        }
       else{
            graph[tmp-65].push_back(input[4]);
        }
    }
    
    dfs(0, graph, check);
    
    
    for(int i=0 ; i< nodes ; i++){
        printf("%c",preorder[i]);
    }
    printf("\n");
    
    
    for(int i=0 ; i< nodes ; i++){
        printf("%c",inorder[i]);
    }
    printf("\n");
    
    
    for(int i=0 ; i< nodes ; i++){
        printf("%c",postorder[i]);
    }
    printf("\n");
    
    return 0;
}

 

 

위 방법도 정답이었지만, 코드를 더욱 단순화 하기 위하여 구조체를 사용하였다.

#include <iostream>
#include <string>

using namespace std;


struct Node{
    Node* left;
    Node* right;
    char data;
};
Node *nodes;


void preorder(Node *root){
    printf("%c",root->data);
    if(root->left)
        preorder(root->left);
    if(root->right)
        preorder(root->right);
}


void inorder(Node *root){
    if(root->left)
        inorder(root->left);
    printf("%c",root->data);
    if(root->right)
        inorder(root->right);
    
}

void postorder(Node *root){
    if(root->left)
        postorder(root->left);
    if(root->right)
        postorder(root->right);
    printf("%c",root->data);
    
}




int main(){
    string input;
    int n;
    scanf("%d",&n);
    cin.ignore();
    
    nodes = (Node*)malloc(sizeof(Node)*n);
    
    for(int i=0 ; i< n ; i++){
        getline(cin, input);
        int now_root = input[0] - 65;
        
        nodes[now_root].data = input[0];
        
        if(input[2] == '.'){
            nodes[now_root].left = NULL;
        }
        else{
            nodes[now_root].left = &nodes[input[2]-65];
        }
        
        if(input[4] == '.'){
            nodes[now_root].right = NULL;
        }
       else{
           nodes[now_root].right = &nodes[input[4]-65];
        }
    }
    
    
    preorder(&nodes[0]);
    printf("\n");
    inorder(&nodes[0]);
    printf("\n");
    postorder(&nodes[0]);
    printf("\n");
    
    free(nodes);
    
    return 0;
}