[ 트리 - 1991 ] 트리 순회(C++)

문제

---

접근법

 

가장 기본적인 트리 구조이다.

 

처음에는 1차원 배열을 이용하여 해당 트리를 구현하고자 하였다.

부모 Index *2가 왼쪽 자식, 부모 Index *2+1이 오른쪽 자식임을 이용한다면 할 수 있을 것이라 생각했다. 하지만 Input이 들어올 때 배열 내에서 해당 부모의 위치를 탐색한 후 왼쪽, 오른쪽 자식을 찾아야 하기 때문에 불필요한 탐색과정이 요구되고 구현하기도 쉽진 않다.

 

따라서 가장 많이 이용하는 Class를 이용하여 전위, 후위, 중위 순회를 구현하였다.

기본적인 Class 구조는 다음과 같다.

 

typedef class NODE {
public:
    char c_Alphabet;
    NODE* pst_Left;
    NODE* pst_Right;

    NODE(char val)
        : c_Alphabet(val), pst_Left(nullptr), pst_Right(nullptr) {}
} NODE_t;

 

왼쪽, 오른쪽 자식 역시 다른 노드이기 때문에 동적 할당을 위한 NODE Pointer로 구현하였으며, 해당 노드의 내용은 문자이기에 char 형으로 설정하였다. 노드 초기화는 인자로 해당 노드의 문자를 받고, 자식들은 모두 nullpointer로 구현하였다.

 

전위,중위,후위 순회는 다음과 같다.

 

void InOrder(NODE_t* root)
{
    if (root == nullptr) return;
    InOrder(root->pst_Left);
    cout << root->c_Alphabet;
    InOrder(root->pst_Right);
}

void PreOrder(NODE_t* root)
{
    if (root == nullptr) return;
    cout << root->c_Alphabet;
    PreOrder(root->pst_Left);
    PreOrder(root->pst_Right);
}


void PostOrder(NODE_t* root)
{
    if (root == nullptr) return;
    PostOrder(root->pst_Left);
    PostOrder(root->pst_Right);
    cout << root->c_Alphabet;
}

 

가장 기본이 되면서 중요한 순회 방식이니 알아두도록 하자. 

 

이 문제에서 시간을 많이 쓴 부분은 오히려 입력받은 부모, 자식 노드를 생성하고 연결하는 과정이 힘들었다.

하지만 컴파일러가 char형 문자를 디버깅 할 때 이에 해당하는 ASCII Code를 기반으로 디버깅 하는 것을 이용하여 구현할 수 있었다.

 

    for (int i = 0; i < s32_N; ++i) {
        char c_Parent, c_Left, c_Right;
        cin >> c_Parent >> c_Left >> c_Right;

        if (arst_Tree[c_Parent - 'A'] == nullptr) {
            arst_Tree[c_Parent - 'A'] = new NODE_t(c_Parent);
        }

        if (c_Left != '.') {
            arst_Tree[c_Left - 'A'] = new NODE_t(c_Left);
            arst_Tree[c_Parent - 'A']->pst_Left = arst_Tree[c_Left - 'A'];
        }

        if (c_Right != '.') {
            arst_Tree[c_Right - 'A'] = new NODE_t(c_Right);
            arst_Tree[c_Parent - 'A']->pst_Right = arst_Tree[c_Right - 'A'];
        }
    }

---

정답

#include <iostream>
#include <vector>
#include <string>

using namespace std;

typedef class NODE {
public:
    char c_Alphabet;
    NODE* pst_Left;
    NODE* pst_Right;

    NODE(char val)
        : c_Alphabet(val), pst_Left(nullptr), pst_Right(nullptr) {}
} NODE_t;

void InOrder(NODE_t* root);
void PreOrder(NODE_t* root);
void PostOrder(NODE_t* root);

NODE_t* arst_Tree[26] = { nullptr };

int main() {
    int32_t s32_N;
    cin >> s32_N;

    for (int i = 0; i < s32_N; ++i) {
        char c_Parent, c_Left, c_Right;
        cin >> c_Parent >> c_Left >> c_Right;

        if (arst_Tree[c_Parent - 'A'] == nullptr) {
            arst_Tree[c_Parent - 'A'] = new NODE_t(c_Parent);
        }

        if (c_Left != '.') {
            arst_Tree[c_Left - 'A'] = new NODE_t(c_Left);
            arst_Tree[c_Parent - 'A']->pst_Left = arst_Tree[c_Left - 'A'];
        }

        if (c_Right != '.') {
            arst_Tree[c_Right - 'A'] = new NODE_t(c_Right);
            arst_Tree[c_Parent - 'A']->pst_Right = arst_Tree[c_Right - 'A'];
        }
    }

    PreOrder(arst_Tree[0]);
    cout << endl;

    InOrder(arst_Tree[0]);
    cout << endl;

    PostOrder(arst_Tree[0]);
    cout << endl;

    return 0;
}

void InOrder(NODE_t* root)
{
    if (root == nullptr) return;
    InOrder(root->pst_Left);
    cout << root->c_Alphabet;
    InOrder(root->pst_Right);
}

void PreOrder(NODE_t* root)
{
    if (root == nullptr) return;
    cout << root->c_Alphabet;
    PreOrder(root->pst_Left);
    PreOrder(root->pst_Right);
}


void PostOrder(NODE_t* root)
{
    if (root == nullptr) return;
    PostOrder(root->pst_Left);
    PostOrder(root->pst_Right);
    cout << root->c_Alphabet;
}

 

 

결론은 트리는 Class를 쓰자. 1차원 배열로 하는건 효과적이지 않다.