Cây tìm kiếm nhị phân (Binary Search Tree - BST) trong cấu trúc dữ liệu

Cây tìm kiếm nhị phân (BST) là cây nhị phân có các tính chất:

• Mọi BST đều là cây nhị phân
• Mọi con trái giữ giá trị nhỏ hơn gốc
• Mọi con phải giữ giá trị lớn hơn gốc
• BST lý tưởng không giữ giá trị trùng lặp

Ví dụ cây BST:

Cây này tuân thủ tất cả tính chất. Duyệt inorder (trái-gốc-phải) cho: 5, 8, 10, 15, 16, 20, 23.

Ví dụ C++ triển khai BST

#include <iostream>
using namespace std;

class node {
public:
    int h_left, h_right, bf, value;
    node *left, *right;
};

class tree {
private:
    node* get_node(int key);
public:
    node *root;
    tree() { root = NULL; }
    void inorder_traversal(node *r);
    node* insert_node(node *root, int key);
};

node* tree::get_node(int key) {
    node *new_node = new node;
    new_node->h_left = 0; new_node->h_right = 0;
    new_node->bf = 0;
    new_node->value = key;
    new_node->left = NULL; new_node->right = NULL;
    return new_node;
}

void tree::inorder_traversal(node *r) {
    if(r != NULL) {
        inorder_traversal(r->left);
        cout << r->value << " ";
        inorder_traversal(r->right);
    }
}

node* tree::insert_node(node *root, int key) {
    if(root == NULL) return get_node(key);
    if(key < root->value) root->left = insert_node(root->left, key);
    else if(key > root->value) root->right = insert_node(root->right, key);
    return root; // trùng khóa thì không chèn
}

int main() {
    node *root;
    tree my_tree;
    my_tree.root = my_tree.insert_node(my_tree.root, 10);
    my_tree.root = my_tree.insert_node(my_tree.root, 5);
    my_tree.root = my_tree.insert_node(my_tree.root, 16);
    my_tree.root = my_tree.insert_node(my_tree.root, 20);
    my_tree.root = my_tree.insert_node(my_tree.root, 15);
    my_tree.root = my_tree.insert_node(my_tree.root, 8);
    my_tree.root = my_tree.insert_node(my_tree.root, 23);
    cout << "In-Order Traversal: ";
    my_tree.inorder_traversal(my_tree.root);
}

Kết quả

In-Order Traversal: 5 8 10 15 16 20 23