Chương trình C++ đếm số lần xuất hiện bằng cây BST

Sử dụng cây tìm kiếm nhị phân (BST) với trường đếm (count) tại mỗi nút để lưu trữ và truy vấn số lần xuất hiện của một giá trị.

Thuật toán

Hàm Insert(root, d):
  Tạo nút mới với data=d, count=1.
  Nếu cây rỗng: nút mới làm gốc.
  Duyệt cây:
    Nếu d == nút hiện tại: tăng count.
    Nếu d < nút: đi trái.
    Nếu d > nút: đi phải.
  Trả về gốc.

Hàm SearchNode(root, d):
  Duyệt cây theo BST.
  Nếu tìm thấy: in data và count.
  Nếu hết cây: in "Khong tim thay".

Ví dụ mã nguồn

#include <iostream>
using namespace std;

struct Node {
    int data, cnt;
    Node *left, *right;
};

Node* createNode(int d) {
    Node* n = new Node;
    n->data = d; n->cnt = 1; n->left = n->right = nullptr;
    return n;
}

Node* insert(Node* root, int d) {
    Node* tmp = createNode(d);
    if (!root) return tmp;
    Node* t = root;
    while (t) {
        if (t->data == d) { t->cnt++; break; }
        else if (d < t->data) {
            if (!t->left) { t->left = tmp; break; }
            t = t->left;
        } else {
            if (!t->right) { t->right = tmp; break; }
            t = t->right;
        }
    }
    return root;
}

void search(Node* root, int d) {
    while (root) {
        if (root->data == d) {
            cout << "Gia tri " << d << " xuat hien " << root->cnt << " lan.\n";
            return;
        }
        root = (d < root->data) ? root->left : root->right;
    }
    cout << "Khong tim thay.\n";
}

int main() {
    int a[20] = {8,1,3,6,4,7,10,14,13,7,6,1,26,4,26,20,21,12,10,1};
    Node* root = nullptr;
    for (int x : a) root = insert(root, x);
    char c;
    do {
        int n; cout << "Tim gia tri: "; cin >> n;
        search(root, n);
        cout << "Tiep tuc? (y/n): "; cin >> c;
    } while (c == 'y' || c == 'Y');
    return 0;
}

Đầu ra mẫu

Tim gia tri: 7
Gia tri 7 xuat hien 2 lan.
Tiep tuc? (y/n): y
Tim gia tri: 15
Khong tim thay.
Tiep tuc? (y/n): n