[자료구조] Linked list를 활용한 이진 트리 구현 :: C++

트리에 대한 기본적인 배경지식은 아래의 포스팅을 참고하면 좋을 것 같다.

https://go2gym365.tistory.com/274

[자료구조] Tree & Binary Tree

1. Node 구조체

노드는 값과 자식 노드로 left, right노드를 가지고 있다.

struct Node {
    int data;
    Node* left;
    Node* right;

    Node() {
        left = nullptr;
        right = nullptr;
    }
};

2. Binary Tree Class

기본적으로 트리는 루트노드를 가지고 있기 때문에 Node ptr형 변수를 하나 선언해주고 nullptr로 생성자를 통해 초기화 해줬다.

class BinaryTree{
private:
    Node *root;

public:
    BinaryTree() {root = nullptr;}
    ~BinaryTree() {}

    void addNode(int value);
    void deleteNode(int idx);
    
    void preOrder();
    void inOrder();
    void postOrder();
    void levelOrder();

    void preOrderLogic(Node* node);
    void inOrderLogic(Node* node);
    void postOrderLogic(Node* node);
};

 

3. 노드 추가

만약 루트 노드가 비었다면, 즉 노드가 하나도 생성되지 않았다면 바로 루트노드에 값을 넣어주고, 다른 노드들이 존재한다면 레벨 순회를 통해 비어있는 노드부터 채워서 완전 이진트리 형태로 구성해줬다.

void BinaryTree::addNode(int value) {
    Node *newNode = new Node();
    newNode->data = value;

    if(root == nullptr) {
        root = newNode;
    }
    else {
        queue<Node*> q;
        Node *temp;

        q.push(root);
        
        while(!q.empty()) {
            temp = q.front();
            q.pop();

            if(temp->left == nullptr) {
                temp->left = newNode;
                break;
            }
            else {
                q.push(temp->left);
            }
            
            if(temp->right == nullptr) {
                temp->right = newNode;
                break;
            }
            else {
                q.push(temp->right);
            }
        }
    }
}

3. 노드 삭제

만약 루트노드조차 없다면 삭제할 메모리조차 없기 때문에 오류를 반환했다. 

삭제하고싶은 노드의 레벨 순서대로의 번호를 받아서 레벨 순회를 통해 인덱스 번호가 일치하면 삭제처리했다.

여기서도 자식노드가 있으면 오류를 반환했다.

void BinaryTree::deleteNode(int idx) {

    if(root == nullptr) {
        cout << "삭제할 노드가 없습니다." << '\n';
        exit(EXIT_FAILURE);
    }
    else {
        queue<Node*> q;
        int cnt = 0;
        Node *temp;

        q.push(root);
        
        while(!q.empty()) {
            temp = q.front();
            q.pop();
            cnt++;

            if(cnt == idx) {
                if(temp->left != nullptr || temp->right != nullptr) {
                    cout << "자식 노드가 있어 삭제가 불가능합니다." << '\n';
                    return;
                }
                else {
                    delete(temp);
                    cout << "삭제 성공" << '\n';
                    return;
                }
            }
            else {
                if(temp->left != nullptr) {
                    q.push(temp->left);
                }
                if(temp->right != nullptr) {
                    q.push(temp->right);
                }
            }
            cout << "인덱스에 원소가 없습니다." << '\n';
            return;
        }
    }
}

 

여기서부터는 트리의 노드를 순회하는 로직에 대해서 설명한다. 아래의 순회 방법에 대한 설명은 아래의 포스팅을 참고하자

https://go2gym365.tistory.com/276

[자료구조] 트리의 순회 방법 - 전위, 중위, 후위, 레벨

4. Preorder / 전위 순회

전위 순회는 재귀가 들어가는 순서대로 방문한다고 보면 된다.

순회 순서 : [ root node > 왼쪽 노드 > 오른쪽 노드 ] 순서로 순회한다.

void BinaryTree::preOrder() {
    if(root == nullptr) {
        cout << "순회할 노드가 없습니다." << '\n';
        return;
    }
    preOrderLogic(root);
}

void BinaryTree::preOrderLogic(Node* cur) {
    if(cur == nullptr) return;

    cout << cur->data << "  ";
    preOrderLogic(cur->left);
    preOrderLogic(cur->right);
}

5. InOrder / 중위 순회

순회 순서 : [ 왼쪽 자식 > root node > 오른쪽 자식 ]

void BinaryTree::inOrder() {
    if(root == nullptr) {
        cout << "순회할 노드가 없습니다." << '\n';
        return;
    }
    inOrderLogic(root);
}

void BinaryTree::inOrderLogic(Node* cur) {
    if(cur == nullptr) return;

    inOrderLogic(cur->left);
    cout << cur->data << "  ";
    inOrderLogic(cur->right);
}

6. PostOrder / 후위 순회

순회 순서 : [ 왼쪽 자식 > 오른쪽 자식 > root node ]

void BinaryTree::postOrder() {
    if(root == nullptr) {
        cout << "순회할 노드가 없습니다." << '\n';
        return;
    }
    postOrderLogic(root);
}

void BinaryTree::postOrderLogic(Node* cur) {
    if(cur == nullptr) return;

    postOrderLogic(cur->left);
    postOrderLogic(cur->right);
    cout << cur->data << " ";
}

7. Level Order / 레벨 순회

레벨 순회는 말그대로 트리의 레벨 순서대로, 번호에 맞춰서 순회하는 방법이다. 루트노드부터 차례대로 순회한다.

void BinaryTree::levelOrder() {
    if(root == nullptr) {
        cout << "순회할 노드가 없습니다." << '\n';
        return;
    }

    queue<Node*> q;
    q.push(root);

    while(!q.empty()) {
        Node* cur = q.front();
        q.pop();
        cout << cur->data << ' ';

        if(cur->left != nullptr) {
            q.push(cur->left);
        }

        if(cur->right != nullptr) {
            q.push(cur->right);
        }
    }
}

8. 전체 코드

#include <iostream>
#include <cstdlib>
#include <queue>

using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;

    Node() {
        left = nullptr;
        right = nullptr;
    }
};

class BinaryTree{
private:
    Node *root;

public:
    BinaryTree() {root = nullptr;}
    ~BinaryTree() {}

    void addNode(int value);
    void deleteNode(int idx);
    
    void preOrder();
    void inOrder();
    void postOrder();
    void levelOrder();

    void preOrderLogic(Node* node);
    void inOrderLogic(Node* node);
    void postOrderLogic(Node* node);
};

void BinaryTree::addNode(int value) {
    Node *newNode = new Node();
    newNode->data = value;

    if(root == nullptr) {
        root = newNode;
    }
    else {
        queue<Node*> q;
        Node *temp;

        q.push(root);
        
        while(!q.empty()) {
            temp = q.front();
            q.pop();

            if(temp->left == nullptr) {
                temp->left = newNode;
                break;
            }
            else {
                q.push(temp->left);
            }
            
            if(temp->right == nullptr) {
                temp->right = newNode;
                break;
            }
            else {
                q.push(temp->right);
            }
        }
    }
}

void BinaryTree::deleteNode(int idx) {

    if(root == nullptr) {
        cout << "삭제할 노드가 없습니다." << '\n';
        exit(EXIT_FAILURE);
    }
    else {
        queue<Node*> q;
        int cnt = 0;
        Node *temp;

        q.push(root);
        
        while(!q.empty()) {
            temp = q.front();
            q.pop();
            cnt++;

            if(cnt == idx) {
                if(temp->left != nullptr || temp->right != nullptr) {
                    cout << "자식 노드가 있어 삭제가 불가능합니다." << '\n';
                    return;
                }
                else {
                    delete(temp);
                    cout << "삭제 성공" << '\n';
                    return;
                }
            }
            else {
                if(temp->left != nullptr) {
                    q.push(temp->left);
                }
                if(temp->right != nullptr) {
                    q.push(temp->right);
                }
            }
            cout << "인덱스에 원소가 없습니다." << '\n';
            return;
        }
    }
}

void BinaryTree::preOrder() {
    if(root == nullptr) {
        cout << "순회할 노드가 없습니다." << '\n';
        return;
    }
    preOrderLogic(root);
}

void BinaryTree::preOrderLogic(Node* cur) {
    if(cur == nullptr) return;

    cout << cur->data << "  ";
    preOrderLogic(cur->left);
    preOrderLogic(cur->right);
}

void BinaryTree::inOrder() {
    if(root == nullptr) {
        cout << "순회할 노드가 없습니다." << '\n';
        return;
    }
    inOrderLogic(root);
}

void BinaryTree::inOrderLogic(Node* cur) {
    if(cur == nullptr) return;

    inOrderLogic(cur->left);
    cout << cur->data << "  ";
    inOrderLogic(cur->right);
}

void BinaryTree::postOrder() {
    if(root == nullptr) {
        cout << "순회할 노드가 없습니다." << '\n';
        return;
    }
    postOrderLogic(root);
}

void BinaryTree::postOrderLogic(Node* cur) {
    if(cur == nullptr) return;

    postOrderLogic(cur->left);
    postOrderLogic(cur->right);
    cout << cur->data << " ";
}

void BinaryTree::levelOrder() {
    if(root == nullptr) {
        cout << "순회할 노드가 없습니다." << '\n';
        return;
    }

    queue<Node*> q;
    q.push(root);

    while(!q.empty()) {
        Node* cur = q.front();
        q.pop();
        cout << cur->data << ' ';

        if(cur->left != nullptr) {
            q.push(cur->left);
        }

        if(cur->right != nullptr) {
            q.push(cur->right);
        }
    }
}

void menuPrint() {
    cout << "==============Binary Tree==============" << "\n";
    cout << "[1] AddNode" << "\n";
    cout << "[2] DeleteNode" << "\n";
    cout << "[3] preOrder" << "\n";
    cout << "[4] inOrder" << "\n";
    cout << "[5] postOrder" << "\n";
    cout << "[6] levelOrder" << "\n";
    cout << "[Exit] Exit(1~6제외 아무키나 누르세요)" << "\n";
}

int main() {
    BinaryTree BT;

    while(true) {
        menuPrint();
        char cmd;
        cin >> cmd;
        if(cmd == '1') {
            int input;
            cout << "값을 입력하세요 : ";
            cin >> input;
            BT.addNode(input);
        }
        else if(cmd == '2') {
            int input;
            cout << "삭제할 노드의 레벨을 입력하세요 : ";
            cin >> input;
            BT.deleteNode(input);
        }
        else if(cmd == '3') {
            BT.preOrder();
            cout << '\n';
        }
        else if(cmd == '4') {
            BT.inOrder();
            cout << '\n';
        }
        else if(cmd == '5') {
            BT.postOrder();
            cout << '\n';
        }
        else if(cmd == '6') {
            BT.levelOrder();
            cout << '\n';
        }
        else {
            exit(0);
        }
    }
}

CS 지식을 공부하고 기록하는 개인 공부 블로그입니다.
내용 중 틀린 부분 피드백 혹은 궁금한 점이 있으면 댓글로 남겨주시면 참고 및 답변 달아드리겠습니다🧐