BST - Tìm kiếm và chèn C++

Cây tìm kiếm nhị phân (BST): trái < gốc < phải. Tìm kiếm: so sánh với gốc, đi trái/phải. Chèn: tìm vị trí lá phù hợp, gán nút mới.

Tìm kiếm đệ quy

Nếu root==NULL hoặc root->key==key → trả về root. Nếu key > root->key → tìm cây phải, ngược lại tìm cây trái.

Chèn đệ quy

Nếu root==NULL → tạo nút mới. Nếu key < root->key → chèn trái, ngược lại chèn phải. Trả về root.

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int key;
    Node *left, *right;
};

Node* newNode(int k) {
    Node* n = new Node();
    n->key = k; n->left = n->right = nullptr;
    return n;
}

Node* search(Node* root, int key) {
    if (!root || root->key == key) return root;
    if (key > root->key) return search(root->right, key);
    return search(root->left, key);
}

Node* insert(Node* root, int key) {
    if (!root) return newNode(key);
    if (key < root->key) root->left = insert(root->left, key);
    else if (key > root->key) root->right = insert(root->right, key);
    return root;
}

void inorder(Node* root) {
    if (root) { inorder(root->left); cout << root->key << '\t'; inorder(root->right); }
}

int main() {
    Node* root = nullptr;
    root = insert(root, 23);
    insert(root, 15);
    insert(root, 12);
    insert(root, 17);
    insert(root, 32);
    insert(root, 29);
    
    cout << "Cay: "; inorder(root); cout << '\n';
    cout << "Tim 12: " << (search(root, 12) ? "Tim thay" : "Khong tim thay");
    return 0;
}

Kết quả

Cay: 12 15 17 23 29 32
Tim 12: Tim thay