글 읽기 - 어... 전통적 트리 구현으로는 안되는 문제인가요?

herdson 4년 전 0

트리분야 문제를 대비하는 마음으로

이진트리 그 자체를 짜는 식으로 했는데

5
A B C
D E .
B D .
C . .
E . .

상상도 못한 입력 ㄴㅇㄱ 가 있을 수 있는 상황이었네요. 대부분의 정답코드들에서 왜 배열이 나오는지 이해가 되어버렸습니다.

아래 소스처럼 통짜 트리를 짜서 해결하신 분이 있을까요?

#include <iostream>

using namespace std;

class Node
{
    private:
        char data;
        Node *left, *right;
    public:
        Node(char in)
        {
            this->data = in;
            this->left = this->right = nullptr;
        }
        void setleft(char in)
        {
            this->left = new Node(in);
        }
        void setright(char in)
        {
            this->right = new Node(in);
        }
        Node* getleft()
        {
            return this->left;
        }
        Node* getright()
        {
            return this->right;
        }
        char show()
        {
            char ret = data != '.' ? data : '\0';
            return ret;
        }
};

class Tree
{
    private:
        Node *root;
        void search(Node *parent, char data, char l, char r)
        {
            if (parent == nullptr)
                return;
            
            if (parent->show() == data)
            {
                parent->setleft(l);
                parent->setright(r);
                return;
            }
            else
            {
                search(parent->getleft(), data, l, r);
                search(parent->getright(), data, l, r);
            }
        }
    public:
        Tree()
        {
            root = nullptr;
        }
        Node* getroot() { return root; }
        void add(char in, char ld, char rd)
        {
            if (root == nullptr)
            {
                if (in == '.')
                    return;
                
                root = new Node(in);
                
                if (ld != '.')
                    root->setleft(ld);
                if (rd != '.')
                    root->setright(rd);
            }
            else
                search(root, in, ld, rd);
        }
        void preorder(Node *parent)
        {
            if (parent == nullptr)
                return;
            
            cout << parent->show();
            preorder(parent->getleft());
            preorder(parent->getright());
        }
        void inorder(Node *parent)
        {
            if (parent == nullptr)
                return;
            
            inorder(parent->getleft());
            cout << parent->show();
            inorder(parent->getright());
        }
        void postorder(Node *parent)
        {
            if (parent == nullptr)
                return;
            
            postorder(parent->getleft());
            postorder(parent->getright());
            cout << parent->show();
        }
    
};

int main()
{
    Tree *res = new Tree();
    int n; cin >> n;
    char prt, lft, rgt;
    while (n--)
    {
        cin >> prt >> lft >> rgt;
        res->add(prt, lft, rgt);
    }
    
    res->preorder(res->getroot());
    cout << "\n";
    res->inorder(res->getroot());
    cout << "\n";
    res->postorder(res->getroot());
    
    delete res;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어... 전통적 트리 구현으로는 안되는 문제인가요?

herdson 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말