[실1] 1991 - 트리 순회

#include <iostream>
using namespace std;
 
int n;
 
struct node
{
    char left;
    char right;
};
 
struct node tree[100];
 
void preOrder(char root)
{
    if (root == '.')
        return;
 
    else 
    {
        cout << root;
        preOrder(tree[root].left);
        preOrder(tree[root].right);
    }
}
 
void inOrder(char root)
{
    if (root == '.')
        return;
 
    else 
    {
        inOrder(tree[root].left);
        cout << root;
        inOrder(tree[root].right);
    }
}
 
void postOrder(char root)
{
    if (root == '.')
        return;
 
    else 
    {
        postOrder(tree[root].left);
        postOrder(tree[root].right);
        cout << root;
    }
}
 
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    char t1, t2, t3;
 
    for (int i = 1; i <= n; i++)
    {
        cin >> t1 >> t2 >> t3;
        tree[t1].left = t2;
        tree[t1].right = t3;
    }
    preOrder('A');
    cout << "\n";
    inOrder('A');
    cout << "\n";
    postOrder('A');
    cout << "\n";
}

출처 : https://cocoon1787.tistory.com/472

 

 

개인 코드) 이론적으론 문제가 없으난 오류가 나서 참고했습니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <utility>
#include <unordered_map>
 
using namespace std;
 
#define SAFE_DELETE(x) if(x!=nullptr) delete x
 
struct s_node
{
    s_node* left = nullptr, * right = nullptr;
    char data = '\0';
 
public:
    s_node() = default;
 
    s_node(char _data) : data(_data) { }
 
    ~s_node() = default;
};
 
unordered_map<char, s_node*> tree;
vector<char> key;
 
// 트리 구조    
//     A
//   B   C
// D    E  F
//           G
// 
// 전위 A B D C E F G 
// 중위 D B A E C F G 
// 후위 D B E G F C A 
 
// (루트, 왼쪽, 오른쪽)
void Pre_order(s_node* _node)
{
    if (!_node)
        return;
 
    cout << _node->data;
    Pre_order(_node->left);
    Pre_order(_node->right);
}
 
// (왼쪽, 루트, 오른쪽)
void In_order(s_node* _node)
{
    if (!_node)
        return;
 
    In_order(_node->left);
    cout << _node->data;
    In_order(_node->right);
}
 
// (왼쪽, 오른쪽, 루트)
void Post_order(s_node* _node)
{
    if (!_node)
        return;
 
    Post_order(_node->left);
    Post_order(_node->right);
    cout << _node->data;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n; cin >> n;
 
    // 루트 생성
    s_node* root = nullptr;
    char root_arr[3];
 
    for (int j = 0; j < 3; j++)
        cin >> root_arr[j];
 
    root = new s_node(root_arr[0]);
    root->left = new s_node(root_arr[1]);
    root->right = new s_node(root_arr[2]);
    tree.insert({ root->data, root });
    key.push_back(root->data);
 
    for (int i = 1; i < n; i++)
    {
        char arr_ch[3];
 
        for (int j = 0; j < 3; j++)
            cin >> arr_ch[j];
 
        for (auto item : tree)
        {
            if (auto node = item.second)
            {
                s_node* root = nullptr;
                s_node* left = node->left;
                s_node* right = node->right;
 
                if (left &&
                    left->data == arr_ch[0])
                    root = left;
 
                if (right &&
                    right->data == arr_ch[0])
                    root = right;
 
                if (root)
                {
                    if (arr_ch[1] != '.')
                        root->left = new s_node(arr_ch[1]);
 
                    if (arr_ch[2] != '.')
                        root->right = new s_node(arr_ch[2]);
 
                    tree.insert({ root->data, root });
                    key.push_back(root->data);
                }
            }
        }
    }
    Pre_order(tree[key[0]]);
    cout << endl;
    In_order(tree[key[0]]);
    cout << endl;
    Post_order(tree[key[0]]);
    cout << endl;
 
    // 제거
    for (int i = tree.size()-1; i >= 0; i--)
        SAFE_DELETE(tree[key[i]]);
 
    tree.clear();
    return 0;
}