Chương trình C++ tìm kiếm phần tử trong Cây tìm kiếm nhị phân

Trong chương trình này, chúng ta cần triển khai tìm kiếm nhị phân để tìm sự tồn tại của một chuỗi tìm kiếm trong một cây tìm kiếm nhị phân (BST). Độ phức tạp thời gian schlimm nhất của tìm kiếm nhị phân là O(n) nhưng trung bình là O(log n).

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 bằng cách chèn dữ liệu vào cây lần lượt.
  Nhập dữ liệu cần tìm trong BST.
  Bắt đầu từ nút gốc, so sánh dữ liệu với phần dữ liệu của nút.
  nếu dữ liệu < temp->d, di chuyển con trỏ temp đến nút con trái.
  nếu dữ liệu > temp->d di chuyển con trỏ temp đến nút con phải.
  nếu dữ liệu = temp->d in độ sâu cây nơi tìm thấy và trả về main.
  Ngược lại in mục không tìm thấy.
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;
}

void Search(node *root, int d) {
    int depth = 0;
    node *temp = root;
    while (temp != NULL) {
        depth++;
        if (temp->d == d) {
            cout << "\nmục tìm thấy ở độ sâu: " << depth;
            return;
        } else if (temp->d > d)
            temp = temp->left;
        else
            temp = temp->right;
    }
    cout << "\n mục không tìm thấy";
    return;
}

int main() {
    char ch;
    int n, i, a[10] = {93, 53, 45, 2, 7, 67, 32, 26, 71, 76};
    node *root = NULL;
    for (i = 0; i < 10; i++)
        root = InsertIntoTree(root, a[i]);
    up:
    cout << "\nNhập phần tử cần tìm: ";
    cin >> n;
    Search(root, n);
    cout << "\n\n\tBạn có muốn tìm kiếm thêm...nhập lựa chọn(y/n)?";
    cin >> ch;
    if (ch == 'y' || ch == 'Y')
        goto up;
    return 0;
}

Kết quả

Nhập phần tử cần tìm: 26
mục tìm thấy ở độ sâu: 7
Bạn có muốn tìm kiếm thêm...nhập lựa chọn(y/n)?
Nhập phần tử cần tìm: 1
mục không tìm thấy
Bạn có muốn tìm kiếm thêm...nhập lựa chọn(y/n)?