[Jungol] 정올 1716 이진트리 탐색

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=989&sca=50&page=7

 Input 
5 3 11 7 -1 -1 2 -1 -1 -1 8 13 -1 -1 4 -1 1 -1 -1　 

 Output 

7 2 11 3 13 1 4 8 5

 

preorder로 입력된 데이터를 postorder로 출력하는 문제입니다.

단말 노드에는 -1이 입력되며, 노드 번호의 최대값 = 20

 

- 전위(preorder) 순회: Root → 왼쪽 자식 → 오른쪽 자식

- 후위(postorder) 순회: 왼쪽 자식 → 오른쪽 자식 → Root

 

※ 재귀 호출로도 이 문제를 구현할 수 있습니다.

#include <stdio.h>
 
int main() {
    int num;
    scanf("%d", &num);
    if (num < 0)
        return 0;
 
    main();
    main();
 
    printf("%d ", num);
    return 0;
}

 

---

동적 할당

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
struct Node {
    int data;
    Node* lch, *rch;
    Node(){}
    Node(int nd) {
        data = nd;
        lch = rch = NULL;
    }
};
struct Tree {
    Node* head;
    void build(){
        head = input();
    }
 
    Node* input(){
        int data;
        scanf("%d", &data);
        if(data < 0) return NULL;
        Node* obj = new Node(data);
        obj->lch = input();
        obj->rch = input();
        return obj;
    }
};
 
void postOrder(Node* now){
        if(now == NULL) return;
        postOrder(now->lch);
        postOrder(now->rch);
        printf("%d ", now->data);
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    Tree* tree = new Tree;
    tree->build();
    postOrder(tree->head);
    
}

 

 

정적 할당

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
struct Node {
    int data;
    Node* lch, *rch;
    Node* alloc(int nd) {
        data = nd;
        lch = rch = NULL;
        return this;
    }
}buf[30];
int bcnt;;
struct Tree {
    Node* head;
    void build(){
        head = input();
    }
 
    Node* input(){
        int data;
        scanf("%d", &data);
        if(data < 0) return NULL;
        Node* obj = buf[bcnt++].alloc(data);
        obj->lch = input();
        obj->rch = input();
        return obj;
    }
};
 
void postOrder(Node* now){
        if(now == NULL) return;
        postOrder(now->lch);
        postOrder(now->rch);
        printf("%d ", now->data);
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    Tree* tree = new Tree;
    tree->build();
    postOrder(tree->head);
    
}