Binary Tree [c++]

---

Binary Tree 개념

하나의 노드가 자식 노드를 2개까지만 가질 수 있는 트리.

---

Binary Tree 특징

노드의 최대 차수는 2.

다시 말해, 모든 이진 트리 노드의 자식 노드 수는 0, 1, 2 중 하나.

포화 이진 트리 : leaf를 제외한 모든 노드의 자식노드 수가 2이고, leaf노드가 동일한 level인 트리

완전 이진 트리 : 마지막 level을 제외한 모든 level이 완전히 채워져 있는 트리. 마지막 level은 차 있지 않아도 되지만 노드가 왼쪽부터 채워져 있어야 함.

---

c++로 구현한 Binary Tree

#include <iostream>
using namespace std;
template <typename T>
struct Node {
    T data;
    struct Node* left;
    struct Node* right;
};
template <typename T>
class SimpleBinaryTree {
private:

public:
    SimpleBinaryTree();
    ~SimpleBinaryTree();

    Node<T>* SBT_CreateNode(T newData);
    void SBT_DestroyNode(Node<T>* node);
    void SBT_DestroyTree(Node<T>* root);

    void SBT_PreOrderPrintTree(Node<T>* root);
    void SBT_InOrderPrintTree(Node<T>* root);
    void SBT_PostOrderPrintTree(Node<T>* root);
};

template <typename T>
SimpleBinaryTree<T>::SimpleBinaryTree() {}

template <typename T>
SimpleBinaryTree<T>::~SimpleBinaryTree() {
    
}

template <typename T>
Node<T>* SimpleBinaryTree<T>::SBT_CreateNode(T newData) {
    Node<T>* newNode = new Node<T>;

    newNode->data = newData;
    newNode->left = nullptr;
    newNode->right = nullptr;

    return newNode;
}

template <typename T>
void SimpleBinaryTree<T>::SBT_DestroyNode(Node<T>* node) {
    node->left = nullptr;
    node->right = nullptr;

    delete node;
}

template <typename T>
void SimpleBinaryTree<T>::SBT_DestroyTree(Node<T>* root) {
    if (root == nullptr) {
        return;
    }

    SBT_DestroyTree(root->left);
    SBT_DestroyTree(root->right);

    SBT_DestroyNode(root);
}

template <typename T>
void SimpleBinaryTree<T>::SBT_PreOrderPrintTree(Node<T>* root) {
    if (root == nullptr) {
        return;
    }

    cout << root->data << " ";
    SBT_PreOrderPrintTree(root->left);
    SBT_PreOrderPrintTree(root->right);
}

template <typename T>
void SimpleBinaryTree<T>::SBT_InOrderPrintTree(Node<T>* root) {
    if (root == nullptr) {
        return;
    }

    SBT_InOrderPrintTree(root->left);
    cout << root->data << " ";
    SBT_InOrderPrintTree(root->right);
}

template <typename T>
void SimpleBinaryTree<T>::SBT_PostOrderPrintTree(Node<T>* root) {
    if (root == nullptr) {
        return;
    }

    SBT_PostOrderPrintTree(root->left);
    SBT_PostOrderPrintTree(root->right);
    cout << root->data << " ";
}


int main() {
    SimpleBinaryTree<string>* simplebinarytree = new SimpleBinaryTree<string>;
    
    Node<string>* a = simplebinarytree->SBT_CreateNode("a");
    Node<string>* b = simplebinarytree->SBT_CreateNode("b");
    Node<string>* c = simplebinarytree->SBT_CreateNode("c");
    Node<string>* d = simplebinarytree->SBT_CreateNode("d");
    Node<string>* e = simplebinarytree->SBT_CreateNode("e");
    Node<string>* f = simplebinarytree->SBT_CreateNode("f");
    Node<string>* g = simplebinarytree->SBT_CreateNode("g");
    a->left = b;
    a->right = c;
    b->left = d;
    b->right = e;
    c->left = f;
    c->right = g;
    cout << "preorder : ";
    simplebinarytree->SBT_PreOrderPrintTree(a);
    cout << "\ninorder : ";
    simplebinarytree->SBT_InOrderPrintTree(a);
    cout << "\npostorder : ";
    simplebinarytree->SBT_PostOrderPrintTree(a);

    return 0;
}

출력 결과
preorder : a b d e c f g
inorder : d b e a f c g
postorder : d e b f g c a

---