이진 검색 트리(BST, Binary Search Tree) 삽입(Insert) C++ 소스 코드

안녕하세요, 츄르 사려고 코딩하는 집사! 코집사입니다.

이번 글은 이진 검색 트리(BST, Binary Search Tree)의 삽입에 대한 글입니다.

 

 

#include<iostream>

#include<stdlib.h>

using namespace std;

int count=0; // treeInsert 함수의 호출 횟수를 기억하기 위한 변수

 

template <typename T>

class cBinarySearchTree;

 

template <typename T>

class cNode {

    friend class cBinarySearchTree <T>;

public:

    cNode();

    cNode(T t) { key = t; left = right = 0; }

private:

    cNode<T>* left;

    cNode<T>* right;

    T key;

};

 

template <typename T>

class cBinarySearchTree {

    friend class cNode<T>;

public:

    cBinarySearchTree();

    ~cBinarySearchTree();

    void treeInsert(T x);

private:

    cNode<T>* treeInsert(cNode<T>* t, T x);

    cNode<T>* root;

};

 

 

template <typename T>

cBinarySearchTree <T>::cBinarySearchTree() {

    root = NULL;

}

 

template <typename T>

cBinarySearchTree <T>::~cBinarySearchTree() {

}

 

 

 

template <typename T>

void cBinarySearchTree <T>::treeInsert(T x) {

    root = treeInsert(root, x);

    return;

}

 

 

 

template <typename T>

cNode<T>* cBinarySearchTree <T>::treeInsert(cNode <T>* t, T x) {

    if (t == NULL) {

        cNode<T> *r = new cNode<T>(x);

        return r;

    }

    if (x < t->key) {

        t->left = treeInsert(t->left, x);

        count++;

        return t;

    }

    else {

        t->right = treeInsert(t->right, x);

        count++;

        return t;

    }

}

 

int main() {

    int n;

    int x;

    cBinarySearchTree<int> tree;

 

    cin >> n;

    for (int i = 0; i<n; i++) {

        cin >> x;

        tree.treeInsert(x);

        count++;

    }

    cout << count;

    return 0;

}