글 읽기 - [c++] 트리 순회 틀린이유가 뭐가있을까요?

gi5005 3년 전 0

일단 기본적으로 예제는 정상적으로 동작하는거같은데 틀렸다고 나옵니다. 반례가 뭐가있는걸까요

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <vector>
#define MAX 10001
using namespace std;

bool vst[MAX];
char parent[MAX];
vector<pair<char, char>> tree[MAX]; // <left,right>
int N;
void preOrder(char curNode, string preStr) //현제 노드 , 출력
{
    if (preStr.size() == N)
    {
        cout << preStr << "\n";
        return;
    }
    vst[curNode] = true;
    char left = tree[curNode][0].first;
    char right = tree[curNode][0].second;
    if (!vst[left] && left != '.')
    {
        preOrder(left, preStr + left);
    }
    else if (!vst[right] && right != '.')
    {
        preOrder(right, preStr + right);
    }
    else
    {
        char pre = parent[curNode];
        preOrder(pre, preStr);
    }
    return;
}
void inOrder(char curNode, string preStr)
{
    if (preStr.size() == N)
    {
        cout << preStr << "\n";
        return;
    }
    vst[curNode] = true;
    char left = tree[curNode][0].first;
    char right = tree[curNode][0].second;
    if (!vst[left] && left != '.')
    {
        inOrder(left, preStr);
    }
    else
    {
        if (!vst[right] && right != '.')
        {
            inOrder(right, preStr + curNode);
        }
        else
        {
            char pre = parent[curNode];
            inOrder(pre, preStr + curNode);
        }
    }
    return;
}
void postOrder(char curNode, string preStr)
{
    if (preStr.size() == N)
    {
        cout << preStr << "\n";
        return;
    }
    vst[curNode] = true;
    char left = tree[curNode][0].first;
    char right = tree[curNode][0].second;
    if (!vst[left] && left != '.')
    {
        postOrder(left, preStr);
    }
    else if (!vst[right] && right != '.')
    {
        postOrder(right, preStr);
    }
    else
    {
        char pre = parent[curNode];
        postOrder(pre, preStr + curNode);
    }
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        char curNode, right, left;
        cin >> curNode >> right >> left;
        tree[curNode].push_back({right, left});
        parent[right] = curNode;
        parent[left] = curNode;
    }
    memset(vst, false, sizeof(vst));
    preOrder('A', "A");
    memset(vst, false, sizeof(vst));
    inOrder('A', "");
    memset(vst, false, sizeof(vst));
    postOrder('A', "");
}

ckdgus2482 3년 전 1

입력 받을때 tree에 right, left 순으로 pair 만들어서 넣으셨는데 읽을땐 left, right로 취급하고 있는 것 같습니다

아마 그부분이 틀린 이유일 것 같습니다

그 외에 몇 가지 조언을 드리고 싶네요

1. 지금 재귀호출하면서 string을 계속 값 복사해서 넘기고 있어서 복사오버헤드가 큽니다

출력을 한 문자 단위로 노드 방문할때마다 하면 string을 전달해줄 필요가 없어 복사를 피할 수 있습니다

2. 트리도 이진 트리의 특성상 일차원 배열로 표현할 수 있는데 코드도 훨씬 짧고 깔끔해질 것 같습니다

3.방문여부를 저장하는 vst배열은 필요가 없습니다

루트부터 탑다운으로 탐색하는 것이므로 부모나 조상으로 올라가는 역방향 간선을 타지 않습니다(트리가 방향성이 없긴하지만 루트가 있는 트리이므로 개념적으로 표현하자면)

따라서 탐색중 같은 노드에 중복 방문하는 경우가 없습니다

gi5005 3년 전 0

아하....그렇군요 재귀로 하나하나 출력하면서 내려가면 역방향으로 올라갈필요가 없다는걸 알았습니다 답변 감사합니다.

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