2017_11_28<백준>1991번 트리 순회

출처:https://www.acmicpc.net/problem/1991

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

문제 해결 과정:

-이진 트리를 만든다

-insert search함수를 만들어 트리를 만든다.

-visit함수를 만들고

-Inorder preorder postorder를 만든다.

#include<iostream>
using namespace std;
struct Node {
    char val;
    Node* leftChild = NULL;
    Node* rightChild = NULL;
};
 
class BinaryTree{
private:
    Node* root;
public:
    BinaryTree() {
        root = NULL;
    }
    BinaryTree(Node* a) {
        root = a;
    }
 
    void insertNode(char parent,char leftChild,char rightChild) {
        Node* Nparent = new Node;
        Node* Nleft = new Node;
        Node* Nright = new Node;
        if (leftChild == '.') {
            Nleft =NULL;
        }
        else {
            Nleft->val = leftChild;
        }
        if (rightChild == '.') {
            Nright = NULL;
        }
        else {
            Nright->val = rightChild;
        }
 
        if (root == NULL) {
            Nparent->val = parent;
            Nparent->rightChild = Nright;
            Nparent->leftChild = Nleft;
            root = Nparent;
        }
        else {
            Node* p = new Node;
            p=searchNodeVal(root, parent);
            p->leftChild = Nleft;
            p->rightChild = Nright;
        }
    }
    
    Node* searchNodeVal(Node* current,char val) {
        if (current == NULL)return NULL;
        if (val == current->val) {
            return current;
        }
        else {
            
            if (searchNodeVal(current->leftChild, val)== NULL) {
                searchNodeVal(current->rightChild, val);
            }
 
        }
 
    }
    void visit(Node* node) {
        cout << node->val;
    }
 
    void InOrder(Node* current) {
        if (current == NULL) {
            return;
        }
 
        InOrder(current->leftChild);
        visit(current);
        InOrder(current->rightChild);
    }
 
    void preOrder(Node* current) {
        if (current == NULL) {
            return;
        }
        visit(current);
        InOrder(current->leftChild);
        InOrder(current->rightChild);
    }
 
    void postOrder(Node* current) {
        if (current == NULL) {
            return;
        }
 
        InOrder(current->leftChild);
        InOrder(current->rightChild);
        visit(current);
    }
    Node* getRoot() {
        return root;
    }
};
 
int main() {
    BinaryTree Tree;
    int n;
    char a, b, c;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a >> b >> c;
        Tree.insertNode(a, b, c);
    }
    Tree.preOrder(Tree.getRoot());
    cout << endl;
    Tree.InOrder(Tree.getRoot());
    cout << endl;
    Tree.postOrder(Tree.getRoot());
    cout << endl;
    
    return 0;
}