[c++] 이진트리 정렬

12 Dec 2023

이진 트리 정렬(Binary Tree Sort)은 이진 트리를 사용하여 데이터를 정렬하는 알고리즘입니다.

이진 트리(Binary Tree)

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조를 말합니다. 일반적으로 이진 트리에는 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드의 연결이 존재합니다.

class Node {
  public:
    int value;
    Node* left;
    Node* right;
};

이진 트리 정렬 알고리즘

먼저 주어진 데이터를 바탕으로 이진 트리를 구성합니다.
다음으로 트리를 중위 순회(Inorder Traversal)하여 정렬된 결과를 얻습니다.
중위 순회를 통해 얻은 정렬된 데이터를 반환합니다.

예시 코드

다음은 C++에서 이진 트리 정렬을 구현한 간단한 예시 코드입니다.

#include <iostream>
using namespace std;

class Node {
  public:
    int value;
    Node* left;
    Node* right;
};

class BinaryTreeSort {
  public:
    Node* root;

    void insert(Node*& node, int value) {
        if (node == nullptr) {
            node = new Node;
            node->value = value;
            node->left = nullptr;
            node->right = nullptr;
        } else {
            if (value < node->value) {
                insert(node->left, value);
            } else {
                insert(node->right, value);
            }
        }
    }

    void inorderTraversal(Node* node) {
        if (node != nullptr) {
            inorderTraversal(node->left);
            cout << node->value << " ";
            inorderTraversal(node->right);
        }
    }
};

int main() {
    int values[] = {5, 3, 8, 1, 4, 7, 9};
    BinaryTreeSort treeSort;
    for (int value : values) {
        treeSort.insert(treeSort.root, value);
    }
    treeSort.inorderTraversal(treeSort.root);
    return 0;
}

위 예시 코드는 이진 트리를 사용하여 주어진 데이터를 정렬한 후, 중위 순회를 통해 정렬된 결과를 출력합니다.

참고 자료

이진 트리: https://en.wikipedia.org/wiki/Binary_tree
중위 순회: https://en.wikipedia.org/wiki/Tree_traversal#In-order_(LNR)