Thứ Ba, 20 Tháng Hai 2024
Trang chủLập trìnhLập trình C/C++Cây nhị phân tìm kiếm - Tìm hiểu cây nhị phân tìm...

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++

Cây nhị phân tìm kiếm là một cấu trúc dữ liệu rất quan trọng và được sử dụng rộng rãi trong các ứng dụng tìm kiếm, xử lý chuỗi, xử lý ảnh, và nhiều lĩnh vực khác.

Trong bài viết trước chúng ta đã cùng nhau tìm hiểu về Cấu trúc dữ liệu cây nhị phân trong lập trình C/C++. Tiếp tục với chủ đề cây nhị phân, trong bài viết này, chúng ta sẽ cùng thực hiện cài đặt và sử dụng cây nhị phân tìm kiếm trong lập trình C/C++.

DANH SÁCH BÀI VIẾT
Tìm hiểu Cấu trúc dữ liệu Hash table trong lập trình C/C++
Cây đa phân trong lập trình C/C++ – Cấu trúc dữ liệu cây đa phân
Hiểu về cấu trúc dữ liệu cây trong lập trình C/C++
Chinh phục cấu trúc dữ liệu hàng đợi lập trình C/C++ trong 5 phút
Cấu trúc dữ liệu ngăn xếp trong lập trình C/C++
Cấu trúc dữ liệu Danh sách liên kết (Linked list) trong lập trình C/C++
Cấu trúc dữ liệu cây nhị phân trong lập trình C/C++
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++
Duyệt tiền tố, trung tố, hậu tố trong cây nhị phân – Lập trình C/C++

Cây nhị phân tìm kiếm

Cây nhị phân tìm kiếm là một cấu trúc dữ liệu trong đó mỗi nút của cây đều chứa một giá trị, và các giá trị được sắp xếp sao cho giá trị của một nút bên trái nhỏ hơn giá trị của nút cha, và giá trị của một nút bên phải lớn hơn giá trị của nút cha.

Ví dụ, cây nhị phân tìm kiếm dưới đây có các giá trị được sắp xếp tăng dần:

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++
Hình ảnh minh họa cây nhị phân tìm kiếm

Cài đặt cây nhị phân tìm kiếm trong C/C++

Trước tiên, chúng ta cần định nghĩa một cấu trúc dữ liệu để đại diện cho một nút của cây nhị phân tìm kiếm:

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

Sau đó, chúng ta có thể viết các hàm để thao tác với cây nhị phân tìm kiếm:

Hàm tạo nút mới

Hàm này sẽ tạo một nút mới chứa giá trị data và trả về con trỏ trỏ đến nút đó:

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

Hàm chèn giá trị vào cây

Hàm này sẽ chèn một giá trị mới vào cây nhị phân tìm kiếm:

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;
}

Hàm tìm kiếm giá trị trong cây

Hàm này sẽ tìm kiếm một giá trị trong cây nhị phân tìm kiếm:

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);
}

Hàm duyệt cây

Hàm này sẽ duyệt cây nhị phân tìm kiếm và thực hiện một hành động trên từng nút của cây:

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

Chương trình ví dụ

Chương trình ví cây nhị phân tìm kiếm trong lập trình C/C++.

// 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;
}

Cảm ơn bạn đã đọc hết bài viết! Chúc bạn học tốt!

[XEM TẤT CẢ BÀI VIẾT CHỦ ĐỀ C/C++ TẠI ĐÂY]

XÊM THÊM
Cấu trúc dữ liệu cây nhị phân trong lập trình C/C++
Cách tìm UCLN và BCNN
Thuật toán đếm số lượng chữ số của số nguyên dương n
Thuật toán tính dãy số Fibonacci
Bài toán chuẩn hóa xâu ký tự
Kiểm tra số chẵn lẻ trong lập trình C/C++
0 0 Phiếu bình chọn
Xếp hạng bài viết
BÀI VIẾT LIÊN QUAN
Đăng ký nhận thông báo
Thông báo email khi
guest
0 Bình luận
Không thể gửi email
Phản hồi nội tuyến

NÊN ĐỌC THÊM

Bạn muốn tìm kiếm gì?

Dịch vụ code thuê

TUICOCACH.COM NHẬN ĐẶT TEXTLINK, BANNER, GP
0
Giáo sư! có thể ném gạch bên dưới nhé!x