전위 중위 후위 순회방법

 

트리에서 전위 중위 후위 순회 하는 방법은 각 순회의 특징을 그대로 적용하는 것이다.

전위는 현재 노드를 먼저 읽는 방식으로 현재노드 -> 좌 -> 우

중위는 좌측 노드부터 먼저 읽는 방식으로 좌 -> 현재노드 -> 우

후위는 자식들을 전부 읽고 자신을 읽는 방식으로 좌 -> 우 -> 현재노드

 

이를 코드로 표현하면 다음과 같다

 

struct tree {
    int    w;
    tree* parent = NULL;
    tree* left = NULL;
    tree* right = NULL;
    bool visit = false;
};
 
void pre(tree* now) { // 전위
    if (now == NULL || now->visit) return;
 
    now->visit = true;
    cout << now->w << " ";
    pre(now->left);
    pre(now->right);
}
 
void in(tree* now) { // 중위
    if (now == NULL || now->visit) return;
    now->visit = true;
    in(now->left);
    cout << now->w << " ";
    in(now->right);
}
 
void post(tree* now) { // 후위
    if (now == NULL || now->visit) return;
    now->visit = true;
    post(now->left);
    post(now->right);
    cout << now->w << " ";
}
 
void solve() {
    
    cout << "pre : ";
    pre(root);
    for (int i = 0; i < tree_size; i++) node[i].visit = false;
    cout << "\n";
    cout << "in : ";
    in(root);
    for (int i = 0; i < tree_size; i++) node[i].visit = false;
    cout << "\n";
    cout << "post : ";
    post(root);
    for (int i = 0; i < tree_size; i++) node[i].visit = false;
}