Cây nhị phân tìm kiếm – Tìm hiểu cây nhị phân tìm kiếm trong C/C++

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

Node* createNode(int data) {
    Node* newNode = new Node;
    newNode->data = data;
    newNode->left = nullptr;
    newNode->right = nullptr;
    return newNode;
}

Node* insert(Node* root, int data) {
    if (root == nullptr) {
        return createNode(data);
    }
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }
    return root;
}

struct Node* search(struct Node* root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    }
    if (data < root->data) {
        return search(root->left, data);
    }
    return search(root->right, data);
}

void traverse(struct Node* root) {
    if (root == NULL) {
        return;
    }
    traverse(root->left);
    printf("%d ", root->data);
    traverse(root->right);
}

// Khai báo các thư viện
#include <stdio.h>

#include <stdlib.h>

// Khai báo cấu trúc dữ liệu Node
struct Node {
  int data;
  struct Node * left;
  struct Node * right;
};

// Hàm tạo mới một node với giá trị được truyền vào
struct Node * createNode(int data) {
  struct Node * newNode = (struct Node * ) malloc(sizeof(struct Node)); // Cấp phát bộ nhớ động cho node mới
  newNode -> data = data; // Gán giá trị vào node mới
  newNode -> left = NULL; // Khởi tạo con trỏ left trỏ đến NULL
  newNode -> right = NULL; // Khởi tạo con trỏ right trỏ đến NULL
  return newNode; // Trả về node mới được tạo
}

// Hàm thêm một node mới vào cây
struct Node * insert(struct Node * root, int data) {
  if (root == NULL) { // Nếu cây rỗng thì tạo mới một node và trả về
    return createNode(data);
  }
  if (data < root -> data) { // Nếu giá trị cần thêm nhỏ hơn giá trị của nút hiện tại thì thêm vào nhánh trái của nút hiện tại
    root -> left = insert(root -> left, data);
  } else if (data > root -> data) { // Ngược lại, thêm vào nhánh phải của nút hiện tại
    root -> right = insert(root -> right, data);
  }
  return root; // Trả về cây đã được thêm node mới
}

// Hàm tìm kiếm một node trong cây
struct Node * search(struct Node * root, int data) {
  if (root == NULL || root -> data == data) { // Nếu cây rỗng hoặc nút hiện tại chính là nút cần tìm kiếm thì trả về nút đó
    return root;
  }
  if (data < root -> data) { // Nếu giá trị cần tìm kiếm nhỏ hơn giá trị của nút hiện tại thì tiếp tục tìm kiếm ở nhánh trái của nút hiện tại
    return search(root -> left, data);
  }
  return search(root -> right, data); // Ngược lại, tìm kiếm ở nhánh phải của nút hiện tại
}

// Hàm duyệt cây theo thứ tự trung tố (in-order traversal)
void traverse(struct Node * root) {
  if (root == NULL) { // Nếu cây rỗng thì kết thúc
    return;
  }
  traverse(root -> left); // Duyệt nhánh trái của nút hiện tại
  printf("%d ", root -> data); // In giá trị của nút hiện tại ra màn hình
  traverse(root -> right); // Duyệt nhánh phải của nút hiện tại
}

// Hàm main

int main() {
  struct Node * root = NULL; //Khai báo nút root(nút gốc)

//Chèn các nút vào cây nhị phân tìm kiếm
  root = insert(root, 7);
  root = insert(root, 3);
  root = insert(root, 1);
  root = insert(root, 5);
  root = insert(root, 12);
  root = insert(root, 15);

  printf("Hiển thị cây: ");
  traverse(root);
  printf("\n");

  struct Node * foundNode = search(root, 5); //Tìm kiếm nút có gí trị là 5

  if (foundNode != NULL) {
    printf("Tim thay: %d\n", foundNode -> data); //Nếu tìm thấy in 5 ra màn hình
  } else {
    printf("Khhong tìm thấy\n"); // Ngược lại in ra màn hình không tìm thấy phần tử
  }

  return 0;
}