Chương trình C++ tìm phần tử nhỏ nhất của mảng bằng Tìm kiếm nhị phân

Đây là chương trình C++ tìm phần tử nhỏ nhất của một mảng bằng cách xây dựng cây tìm kiếm nhị phân (BST) từ mảng chưa sắp xếp. Độ phức tạp thời gian của chương trình là O(log n) trong trường hợp trung bình.

Thuật toán

Bắt đầu
  Xây dựng cây tìm kiếm nhị phân cho mảng dữ liệu chưa sắp xếp đã cho.
  Để tìm phần tử nhỏ nhất, di chuyển con trỏ đến nút con bên trái nhất.
  In giá trị này là giá trị nhỏ nhất trong dữ liệu đã cho.
Kết thúc

Mã ví dụ

#include <iostream>
using namespace std;

struct node {
    int d;
    node *left;
    node *right;
};

node* CreateNode(int d) {
    node *newnode = new node;
    newnode->d = d;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}

node* InsertIntoTree(node* root, int d) {
    node *temp = CreateNode(d);
    node *t = root;
    if (root == NULL)
        root = temp;
    else {
        while (t != NULL) {
            if (t->d < d) {
                if (t->right == NULL) {
                    t->right = temp;
                    break;
                }
                t = t->right;
            } else if (t->d > d) {
                if (t->left == NULL) {
                    t->left = temp;
                    break;
                }
                t = t->left;
            }
        }
    }
    return root;
}

int main() {
    int n, i, a[10] = {86, 63, 95, 6, 7, 67, 52, 26, 45, 98};
    node *root = NULL;
    cout << "\nTập dữ liệu:\n";
    for (i = 0; i < 10; i++) {
        cout << a[i] << " ";
        root = InsertIntoTree(root, a[i]);
    }
    cout << "\n\nPhần tử nhỏ nhất của tập dữ liệu đã cho là ";
    i = 0;
    while (root->left != NULL) {
        i++;
        root = root->left;
    }
    cout << root->d << " được tìm thấy ở độ sâu " << i << " từ gốc.";
    return 0;
}

Kết quả

Tập dữ liệu: 86 63 95 6 7 67 52 26 45 98
Phần tử nhỏ nhất của tập dữ liệu đã cho là 6 được tìm thấy ở độ sâu 2 từ gốc.