[Data Structure] 자료구조(4강) - 이진 트리와 순회

• 수식이 제대로 보이지 않는다면, 새로고침(F5)을 해주시기 바랍니다.

자료구조 포스팅은 여러 자료 구조의 개념 및 c++로의 프로그래밍을 다룰 예정입니다. 자료 구조는 비교적 널리 알려져있고, 다른 곳에서도 잘 설명된 곳이 많기 때문에 자료구조에 한해서는 간단한 개념 및 구현만을 다루겠습니다. 간단히 정리된 것을 볼 수 있는 용도로 적합할 것 같습니다.
경쟁적 프로그래밍 문제 풀이에 유용한 c++의 STL의 헤더파일도 함께 다루겠습니다.

Binary Tree

아래에 구현한 코드는 이진 트리입니다. 부모 노드가 있고, 그 아래 자식 노드는 최대 2개까지 존재할 수 있는 트리입니다. 최고 높은 부모가 root 노드입니다.
트리의 순회에는 전위 순회, 중위 순회, 후위 순회가 있습니다. 부모 노드와 자식 노드 2개가 있을 때, 부모 노드를 언제 방문하는지에 따라 순회의 종류가 갈립니다. 세 노드 중 부모 노드를 먼저 방문하면 전위 순회, 2번 째로 방문하면 중위 순회, 마지막으로 방문하면 후위 순회입니다.

#include <iostream>
using namespace std;

class TreeNode {
public:
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) {
        data = val;
        left = nullptr;
        right = nullptr;
    };
};

class BinaryTree {
private:
    TreeNode* root;

public:
    BinaryTree() {
        root = nullptr;
    }

    ~BinaryTree() {
        clear(root);
    }

    void clear(TreeNode* node) {
        if (node != nullptr) {
            clear(node->left);
            clear(node->right);
            delete node;
        }
    }

    void insert_root(int val) {
        if (root != nullptr) clear(root);
        root = new TreeNode(val);
    }

    void insert_left(TreeNode* parent, int val) {
        if (parent != nullptr && parent->left == nullptr) {
            parent->left = new TreeNode(val);
        }
    }

    void insert_right(TreeNode* parent, int val) {
        if (parent != nullptr && parent->right == nullptr) {
            parent->right = new TreeNode(val);
        }
    }

    void preorder(TreeNode* node) {
        if (node != nullptr) {
            cout << node->data << endl;
            preorder(node->left);
            preorder(node->right);
        }
    }

    void inorder(TreeNode* node) {
        if (node != nullptr) {
            inorder(node->left);
            cout << node->data << endl;
            inorder(node->right);
        }
    }

    void postorder(TreeNode* node) {
        if (node != nullptr) {
            postorder(node->left);
            postorder(node->right);
            cout << node->data << endl;
        }
    }

    TreeNode* get_root() {
        return root;
    }
};