1991 트리 순회(백준)

생각 과정

struct를 하나 구현해주고 tree 의 left 하고 right을 표현해줘야 children(자식 노드들) 을 참조할수 있음

Preorder는 인풋 받고 left, right 차례대로 재귀로 순회

Inorder는 left로 먼저 D(맨 왼쪽 끝 자식노드) 참조하고 그리고 input 받고 right 순회

Postorder는 삼각형 모양을 먼저 뽑고 왼쪽 노드를 참조 못하니 오른쪽 끝 자식에서부터 순회 -> 따라서 left, right 둘다 순회해주고 인풋 받기

 

모든 함수 기저조건 - 만약 . 만나면 자식노드 없으니 아무것도 리턴하지 않음.

처음 left right 포인터 만약 문제가 달라지면 설정법이 달라질 수도있으니 주의.

 

코드

#include <iostream>
using namespace std;
int n;

//참조
// https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
// (struct 구현 및 입력 부분만) https://velog.io/@hyez_dev/%EB%B0%B1%EC%A4%80-1991-%ED%8A%B8%EB%A6%AC-%EC%88%9C%ED%9A%8C-C 
struct node{ //따로 노드 구현하는 법을 몰라 풀이 참고
    char left;
    char right;
};

node c[28];

void PreOrder(char node){

    if (node == '.'){
        return ;
    }

    cout << node;
    PreOrder(c[node].left); //node? node - 'A'?
    PreOrder(c[node].right);
}

void InOrder(char node){

    if (node == '.'){
        return;
    }

    InOrder(c[node].left);
    cout << node;
    InOrder(c[node].right);
}

void PostOrder(char node){

    if (node == '.'){
        return;
    }
    PostOrder(c[node].left);
    PostOrder(c[node].right);
    cout << node;
}

int main(){   

    cin >> n;
    char nod, lft, rht;
    for (int i = 0; i < n; i++){ //1 인덱싱 하면 에러... 질문...

        cin >> nod >> lft >> rht;
        c[nod].left = lft;
        c[nod].right = rht;
    }

    PreOrder('A'); //언제 single quote, 언제 double quote in C++?
    printf("\n");

    InOrder('A');
    printf("\n");

    PostOrder('A');
    printf("\n");
}