신입 개발자 기술면접 C++ 손코딩 : 트리 순회

 

 

참고 : https://m.blog.naver.com/PostView.naver?blogId=sedi1017&logNo=223144612932&proxyReferer=https:%2F%2Fm.search.naver.com%2Fsearch.naver%3Fwhere%3Dm%26sm%3Dmtb_jum%26query%3D%25EC%25A0%2584%25EC%259C%2584%2B%25EC%25A4%2591%25EC%259C%2584%2B%25ED%259B%2584%25EC%259C%2584

 

https://seongkyun.github.io/data_structure /2019/08/02/data_structure/

 

https://blog .naver.com/occidere/220899936160

 

이진 트리의 순회 알고리즘은 재귀적으로 각 노드를 방문합니다. 각 순회 방법(전위, 중위, 후위)는 방문 순서를 결정합니다. 전위, 중위, 후위의 차이는 루트 노드를 몇 번째로 탐색하느냐?? 차이입니다.

• 전위 순회(Pre-order Traversal): 루트를 먼저 방문한 다음, 왼쪽 서브트리와 오른쪽 서브트리를 방문합니다.
• 중위 순회(In-order Traversal): 왼쪽 서브트리를 먼저 방문한 다음, 루트를 방문하고, 마지막으로 오른쪽 서브트리를 방문합니다.
• 후위 순회(Post-order Traversal): 왼쪽 서브트리와 오른쪽 서브트리를 먼저 방문한 다음, 루트를 방문합니다.

다음은 C++로 작성된 이진 트리 순회 알고리즘입니다.

 

#include <iostream>

template<typename T>
class BinaryTree {
private:
    struct Node {
        T value;
        Node *left, *right;

        Node(T val) : value(val), left(nullptr), right(nullptr) {}

        ~Node() {
            delete left;
            delete right;
        }
    };

    Node *root;

    void preOrderTraversal(Node *node) {
        if (node == nullptr) return;
        std::cout << node->value << " ";
        preOrderTraversal(node->left);
        preOrderTraversal(node->right);
    }

    void inOrderTraversal(Node *node) {
        if (node == nullptr) return;
        inOrderTraversal(node->left);
        std::cout << node->value << " ";
        inOrderTraversal(node->right);
    }

    void postOrderTraversal(Node *node) {
        if (node == nullptr) return;
        postOrderTraversal(node->left);
        postOrderTraversal(node->right);
        std::cout << node->value << " ";
    }

public:
    BinaryTree() : root(nullptr) {}

    void insert(T value) {
        if (root == nullptr) {
            root = new Node(value);
        } else {
            // 더 복잡한 삽입 로직을 구현할 수 있습니다.
        }
    }

    void preOrder() {
        preOrderTraversal(root);
        std::cout << std::endl;
    }

    void inOrder() {
        inOrderTraversal(root);
        std::cout << std::endl;
    }

    void postOrder() {
        postOrderTraversal(root);
        std::cout << std::endl;
    }

    ~BinaryTree() {
        delete root;
    }
};