Chương trình C++ tìm phần tử lớn nhất trong mảng bằng Cây tìm kiếm nhị phân

Đây là chương trình C++ tìm phần tử lớn nhất của một mảng bằng cách sử dụng Cây tìm kiếm nhị phân (BST). Độ 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 sử dụng các phần tử dữ liệu đã cho.
  Tiếp theo duyệt con trỏ gốc đến nút con bên phải nhất có sẵn.
  In phần dữ liệu của nút đó như là phần tử dữ liệu lớn nhất của tập dữ liệu đã cho.
  In độ sâu của phần tử dữ liệu lớn nhất.
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ử lớn nhất của tập dữ liệu đã cho là\n ";
    i = 0;
    while (root->right != NULL) {
        i++;
        root = root->right;
    }
    cout << root->d << "\n" << "dữ liệu tìm thấy ở " << i << " độ sâu 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ử lớn nhất của tập dữ liệu đã cho là 98
dữ liệu tìm thấy ở 2 độ sâu từ gốc.