이진 탐색 트리(Binary Search Tree)

이진 탐색 트리(Binary Search Tree)

• 각 노드에는 값이 존재

• 각 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값을 지닌 노드들로 이루어 짐.

• 각 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값을 지닌 노드들로 이루어 짐.

노드 클래스

class Node {
public:
    int data;
    Node* left;
    Node* right;
​
    Node(int data) {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};

BST 클래스

​class BinarySearchTree {
public:
    Node* root;
​
    BinarySearchTree(int data) {
        root = new Node(data);
    }
​
    void Insert(int data);
    
    void Preorder(Node* root);
    void Inorder(Node* root);
    void Postorder(Node* root);
};

• 삽입과 순회만 구현 함.

BST 삽입

void Insert(int data) {
    Node* parent = NULL;
    Node* cur = root;
​
    while (cur != NULL) {
        if (data == cur->data) {
            return;
        }
​
        parent = cur;
​
        if (cur->data > data) {
            cur = cur->left;
        }
        else {
            cur = cur->right;
        }
    }
​
    cur = new Node(data);
​
    if (parent != NULL) {
        if (data < parent->data) {
            parent->left = cur;
        }
        else {
            parent->right = cur;
        }
    }
}

• 루트의 노드부터 값을 비교해서 작으면 왼쪽, 크면 오른쪽 서브트리를 탐색한다.

• NULL값이 나올 때까지 반복하며, 그 위치에 새로운 노드를 생성하고 값을 넣음.

• 이전의 노드(parent 노드)와 연결한다.

BST 순회

void Preorder(Node* root) {
    cout << root->data << endl;
    if (root->left != NULL) Preorder(root->left);
    if (root->right != NULL) Preorder(root->right);
}
​
void Inorder(Node* root) {
    if (root->left != NULL) Inorder(root->left);
    cout << root->data << endl;
    if (root->right != NULL) Inorder(root->right);
}
​
void Postorder(Node* root) {
    if (root->left != NULL) Postorder(root->left);
    if (root->right != NULL) Postorder(root->right);
    cout << root->data << endl;
}

• 쉬워서 설명 생략

메인 함수

int main() {
    BinarySearchTree* tree = new BinarySearchTree(5);
    tree->Insert(8);
    tree->Insert(1);
    tree->Insert(6);
    tree->Insert(4);
    tree->Insert(9);
    tree->Insert(3);
    tree->Insert(2);
    tree->Insert(7);
​
    tree->Preorder(tree->root);
    //tree->Inorder(tree->root);
    //tree->Postorder(tree->root);
​
    return 0;
}