[c++] 배열과 포인터를 사용한 트리 구현

14 Dec 2023

배열과 포인터를 사용하여 간단한 이진 트리를 구현하는 방법을 살펴보겠습니다.

이진 트리 구현

이진 트리는 각 노드가 최대 두 개의 자식을 가지는 트리 구조입니다. 각 노드는 데이터와 두 개의 포인터(왼쪽 자식, 오른쪽 자식)를 갖습니다.

#include <iostream>
using namespace std;

// 이진 트리 노드
struct Node {
    int data;
    Node* left;
    Node* right;
};

// 이진 트리 클래스
class BinaryTree {
public:
    Node* root;
    BinaryTree(int data) {
        root = createNode(data);
    }

    Node* createNode(int data) {
        Node* newNode = new Node;
        newNode->data = data;
        newNode->left = nullptr;
        newNode->right = nullptr;
        return newNode;
    }

    void insert(int data) {
        Node* newNode = createNode(data);
        insertNode(root, newNode);
    }

    void insertNode(Node* root, Node* newNode) {
        if (root->data > newNode->data) {
            if (root->left == nullptr) {
                root->left = newNode;
            } else {
                insertNode(root->left, newNode);
            }
        } else {
            if (root->right == nullptr) {
                root->right = newNode;
            } else {
                insertNode(root->right, newNode);
            }
        }
    }
};

int main() {
    BinaryTree tree(5);
    tree.insert(3);
    tree.insert(8);
    return 0;
}

위 코드에서는 배열이 아닌 포인터를 사용하여 이진 트리를 구현했습니다. Node 구조체는 데이터와 두 개의 포인터를 포함하고 있습니다. BinaryTree 클래스는 이러한 노드들을 생성하고 삽입하는 역할을 합니다.

이제 배열과 포인터를 사용하여 간단한 이진 트리를 구현하는 방법을 살펴보았습니다. 이러한 방식으로 트리를 구현할 때는 메모리 관리에 신경써야 하며, 재귀를 이용한 순회 등의 작업도 고려해야 합니다.