간단한 이진-tree 만들기(들어온 순서대로 만들기)

1. 목표

C++ 사용해 간단한 tree구조를 만들어보겠습니다.

입력한 순서대로 만들어지는 2진-tree를 만들것입니다.

예를들어 1, 2, 3, 4, 5, 6, 7, 8 이 들어온다면 다음과 같이 만드는 것이 목적입니다.

queue를 이용한 bfs 방법으로 만들었습니다.

2.  만들기

1) 우선 간단한 Tree와 요소를 담을 vector, 자료를 처리할 queue를 선언합니다.

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

class tree {

private:

    int num;

    tree* right;

    tree* left;

public:

    tree() {

        right = NULL;

        left = NULL;

        num = 0;

    }

    ~tree() {

        delete(right);

        delete(left);

    }

};

int main()

{

    vector<int> element = { 1, 2, 3, 4, 5, 6, 7, 8 };   //tree만들 요소

    queue<tree *> tree_element; //들어올 순서대로 작업하기 위한 queue

    queue<int> element_queue;   //tree요소를 담을 queue

    tree* t = new tree();

    for (auto n : element)

        element_queue.emplace(n);

    tree_element.emplace(t);

    return 0;

}

우선 백터에 있는 요소들을 element_queue에 넣고 tree의 클래스 구조를 만들었습니다.

그 후 마지막에 tree_element 에 new 생성자를 통해 만들어진 t를 넣고 있습니다.

여기까지 완료되면 다음과 같은 그림일 것입니다.

2) 요소값 입력

tree_queue에 있는 t를 꺼내 t의 왼쪽, 오른쪽에 element_queue에 있는 각 요소들을 순서대로 입력해줄 것입니다.

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

class tree {

private:

    int num;

    tree* right;

    tree* left;

public:

    tree() {

        right = NULL;

        left = NULL;

        num = 0;

    }

    ~tree() {

        delete(right);

        delete(left);

    }

    tree* getLeft() {

        return left;

    }

    tree* getRight() {

        return right;

    }

    void insert_right(int number) {

        right = new tree();

        right->setNum(number);

    }

    void insert_left(int number) {

        left = new tree();

        left->setNum(number);

    }

    void setNum(int number) {

        num = number;

    }

};

int main()

{

    vector<int> element = { 1, 2, 3, 4, 5, 6, 7, 8 };   //tree만들 요소

    queue<tree *> tree_element; //들어올 순서대로 작업하기 위한 queue

    queue<int> element_queue;   //tree요소를 담을 queue

    tree* t = new tree();

    for (auto n : element)

        element_queue.emplace(n);

    tree_element.emplace(t);

    while (!element_queue.empty()) {

        tree* temp = tree_element.front();

        tree_element.pop();

        int left, right;

        left = element_queue.front();

        element_queue.pop();

        temp->insert_left(left);

        tree_element.emplace(temp->getLeft());

        if (element_queue.empty()) break;

    

        right = element_queue.front();

        element_queue.pop();

        temp->insert_right(right);

        tree_element.emplace(temp->getRight());

    }

    return 0;

}

1. tree_element에 있는 tree * 값을 하나 뺀다.

2. 그 후 element_queue에 있는 요소를 하나 빼서 left 변수에 넣는다.

3. insert_left()함수를 이용해 int left를 전달하고 함수내부에서 new를 통해 tree * left 값이 새로운 tree를 가르키게 한다.

4. 오른쪽 도 위와 같은 방법으로 진행.

완료되고 난 후 그림으로 표현하자면 다음과 같이 될 것입니다.

그 후 while문을 통해 다시 위로 올라가서 위 작업을 반복하면 tree_queue에는 입력될 순서대로 들어가게 됩니다.

element_queue가 비어있을때 까지 while문을 돌리게 되면 순서대로 채워지게 됩니다.

마지막으로 출력 코드 보여드리고 마무리 하겠습니다.

3) 출력 코드

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

class tree {

private:

    int num;

    tree* right;

    tree* left;

public:

    tree() {

        right = NULL;

        left = NULL;

        num = 0;

    }

    ~tree() {

        delete(right);

        delete(left);

    }

    tree* getLeft() {

        return left;

    }

    tree* getRight() {

        return right;

    }

    void insert_right(int number) {

        right = new tree();

        right->setNum(number);

    }

    void insert_left(int number) {

        left = new tree();

        left->setNum(number);

    }

    void setNum(int number) {

        num = number;

    }

    bool left_Check() {

        if (left == NULL) return false;

        else return true;

    }

    bool right_Check() {

        if (right == NULL) return false;

        else return true;

    }

    int getNum() {

        return num;

    }

};

int main()

{

    vector<int> element = { 1, 2, 3, 4, 5, 6, 7, 8 };

    queue<tree *> tree_element;

    queue<int> element_queue;

    tree* t = new tree();

    for (auto n : element)

        element_queue.emplace(n);

    tree_element.emplace(t);

    while (!element_queue.empty()) {

        tree* temp = tree_element.front();

        tree_element.pop();

        int left, right;

        left = element_queue.front();

        element_queue.pop();

        temp->insert_left(left);

        tree_element.emplace(temp->getLeft());

        if (element_queue.empty()) break;

    

        right = element_queue.front();

        element_queue.pop();

        temp->insert_right(right);

        tree_element.emplace(temp->getRight());

    }

    queue<tree*>().swap(tree_element);

    tree_element.emplace(t);

    while (!tree_element.empty()) {

        tree* temp = tree_element.front();

        tree_element.pop();

        cout << temp->getLeft()->getNum() << " ";

        if(temp->getLeft()->left_Check())

            tree_element.emplace(temp->getLeft());

        cout << temp->getRight()->getNum() << " ";

        if (temp->getRight()->right_Check())

            tree_element.emplace(temp->getRight());

    }

    return 0;

}

끝