마늘 계산기 난제 라이브러리

68회
 7.35% 
 1000ms 
 65536K
층수가 10보다 작은 두 갈래 트리를 지정하여 앞의 노드 이름 서열을 출력합니다.
입력은 한 줄을 포함하고 빈칸으로 구분된 각 노드는 두 갈래 나무의 층별 역행 순서에 따라 주어진다. 각 노드의 형식은 X(Y,num), X는 이 노드, Y는 부모 노드, num은 0, 1, 2 중의 하나, 0은 루트 노드, 1은 아버지 노드의 왼쪽 자절점, 2는 아버지 노드의 오른쪽 자절점을 나타낸다.출력은 한 줄로 되어 있고, 앞의 순서를 두루 훑어보는 결과입니다.

예제 1

입력:

A(0,0) B(A,1) C(A,2) D(B,1) E(B,2) F(C,1) G(D,1) H(D,2)

출력:

A B D G H E C F

#include<iostream>
#include<map>
#include<stack>
using namespace std;

struct btNode{
    char c;
    btNode *left, *right;
    btNode(char ch) : c(ch), left(NULL), right(NULL){}
};


bool firstFlag;
/*
void preOrder(btNode *root){
	if(root == NULL){
		return;
	}
    if(firstFlag){
        firstFlag = 0;
    }else{
        putchar(' ');
    }
    printf("%c", root->c);
    preOrder(root->left);
    preOrder(root->right);
}
*/

void preOrder(btNode *root){
    stack<btNode*> sk;
    sk.push(root);
    while(!sk.empty()){
        root = sk.top();
        sk.pop();
        while(root != NULL){
            if(firstFlag){
                firstFlag = 0;
            }else{
                putchar(' ');
            }
            printf("%c", root->c);
            if(root->right != NULL){
                sk.push(root->right);
            }
            root = root->left;
        }
    }
}

int main(){
//	freopen("test.txt", "r", stdin);
    char ch, fa, lr;
    map<char, btNode*> mp;
    btNode *root, *p, *q;
    while(scanf("%c(%c,%c) ", &ch, &fa, &lr) == 3){
        if(fa == '0'){
            root = new btNode(ch);
            mp[ch] = root;
        }else{
            p = mp[fa];
            q = new btNode(ch);
			 mp[ch] = q;
            if(lr == '1'){
                p->left = q;
            }else{
                p->right = q;
            }
        }
    }
    firstFlag = 1;
	preOrder(root);
    cout << endl;
}