Cây nhị phân trong C: Hướng dẫn hoàn chỉnh cho người mới bắt đầu

Informatec Digital » Thuật toán » Cây nhị phân trong C: Hướng dẫn đầy đủ dành cho người mới bắt đầu

Cấu trúc phân cấp với các nút có tối đa hai nút con; bao gồm nút gốc, nút lá và các cấp độ.
Ưu điểm: tìm kiếm và chèn hiệu quả, biểu diễn phân cấp và tính linh hoạt động so với mảng.
Các thao tác chính: duyệt (vào, trước, sau), tìm kiếm, chèn và xóa để sắp xếp và quản lý dữ liệu.

Chào mừng bạn đến với hướng dẫn toàn diện này về cây nhị phân trong C. Trong bài viết này, chúng ta sẽ khám phá những điều cơ bản về cây nhị phân và cách triển khai chúng trong ngôn ngữ lập trình C. Nếu bạn là người mới bắt đầu lập trình hoặc chỉ muốn cải thiện kỹ năng C của mình, hướng dẫn này dành cho bạn.

Cây nhị phân là cấu trúc dữ liệu cơ bản trong khoa học máy tính và được sử dụng trong rất nhiều ứng dụng. Hiểu cách chúng hoạt động và cách triển khai chúng sẽ giúp bạn giải quyết các vấn đề phức tạp một cách hiệu quả và tinh tế hơn.

Trong bài viết này, chúng ta sẽ tìm hiểu những kiến thức cơ bản về cây nhị phân, bao gồm cấu trúc, chèn và xóa nút, duyệt cây và tìm kiếm phần tử. Chúng ta cũng sẽ cung cấp các ví dụ thực tế bằng ngôn ngữ lập trình C để bạn có thể thấy cách các khái niệm này được áp dụng trong thực tế.

Vậy hãy bắt đầu!

Cây nhị phân là gì?

Cây nhị phân là cấu trúc dữ liệu phân cấp bao gồm các nút được kết nối với nhau. Mỗi nút có thể có tối đa hai nút con: một ở bên trái và một ở bên phải. Cấu trúc hai nhánh này là điểm phân biệt cây nhị phân với các cấu trúc dữ liệu khác.

Trong cây nhị phân, nút đầu tiên được gọi là nút gốc. Các nút con được gọi là nút con, và các nút không có nút con được gọi là nút lá. Các nút ở cùng cấp được gọi là nút anh em.

Lợi ích của cây nhị phân

Cây nhị phân mang lại một số lợi thế về mặt lưu trữ dữ liệu và tìm kiếm hiệu quả. Một số lợi ích chính bao gồm:

Tìm kiếm hiệu quảCây nhị phân cho phép tìm kiếm các phần tử khi chạy nhanh hơn các cấu trúc dữ liệu khác, chẳng hạn như danh sách liên kết. Điều này là do cấu trúc phân cấp của cây và khả năng phân vùng tập dữ liệu nhanh chóng của nó.
Chèn và tháo linh hoạtCây nhị phân có khả năng thích ứng cao với các hoạt động chèn và xóa nút. Không giống như các cấu trúc dữ liệu tĩnh như mảng, cây nhị phân có thể phát triển và thay đổi cấu trúc của chúng một cách linh hoạt.
Biểu diễn các mối quan hệ phân cấpCây nhị phân đặc biệt hữu ích trong việc thể hiện mối quan hệ phân cấp giữa các phần tử. Ví dụ, trong cấu trúc thư mục tệp, mỗi thư mục có thể được biểu diễn như một nút trong cây, với các thư mục con và tệp là các nút con của nó.

Cấu trúc của cây nhị phân

Trước khi đi sâu vào việc triển khai cây nhị phân trong C, điều quan trọng là phải hiểu cấu trúc cơ bản của chúng. Mỗi nút trong cây nhị phân chứa một giá trị và tham chiếu đến các nút con bên trái và bên phải của nó, nếu có.

Bảng sau đây hiển thị cấu trúc của một nút trong cây nhị phân:

Nút nhị phân
lòng can đảm
Nút trái
Nút phải

Mỗi nút có thể lưu trữ bất kỳ loại dữ liệu nào, chẳng hạn như số nguyên, ký tự hoặc các cấu trúc phức tạp hơn. Nút gốc là điểm bắt đầu của cây và từ đó chúng ta có thể truy cập tất cả các nút khác.

Triển khai cây nhị phân trong C

Giờ đây, khi đã có hiểu biết cơ bản về cây nhị phân, đã đến lúc triển khai chúng trong ngôn ngữ lập trình C. Tiếp theo, chúng ta sẽ xem cách khai báo và sử dụng cấu trúc cây nhị phân trong C.

Khai báo cấu trúc cây nhị phân

Trong C, chúng ta có thể khai báo cấu trúc của cây nhị phân bằng cách sử dụng cấu trúc và con trỏ. Sau đây là khai báo cơ bản của cấu trúc:

struct NodoArbol {
    int valor;
    struct NodoArbol* izquierdo;
    struct NodoArbol* derecho;
};

Trong cấu trúc này, valor biểu thị giá trị được lưu trữ trong nút và izquierdo y derecho lần lượt là các con trỏ tới các nút con bên trái và bên phải.

Trí thông minh sống: nó là gì, nó hoạt động như thế nào và tại sao nó lại quan trọng

Tạo một nút mới

Để tạo một nút mới trong cây nhị phân, chúng ta cần phân bổ bộ nhớ cho nút và đặt giá trị cho nút đó. Sau đây là hàm C tạo một nút mới:

struct NodoArbol* crearNodo(int valor) {
    struct NodoArbol* nodo = (struct NodoArbol*)malloc(sizeof(struct NodoArbol));
    nodo->valor = valor;
    nodo->izquierdo = NULL;
    nodo->derecho = NULL;
    return nodo;
}

Chức năng malloc Nó được sử dụng để phân bổ bộ nhớ động cho nút. Sau đó chúng ta thiết lập các giá trị cho nút và trả về nút đã tạo.

Chèn các nút

Chèn nút là một quá trình cơ bản trong cây nhị phân. Cho phép bạn thêm các phần tử mới vào cây ở đúng vị trí dựa trên giá trị nút. Dưới đây là hàm C để chèn một nút vào cây nhị phân:

struct NodoArbol* insertarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return crearNodo(valor);
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = insertarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = insertarNodo(raiz->derecho, valor);
    }

    return raiz;
}

Hàm này nhận một con trỏ tới gốc của cây và giá trị của nút cần chèn. Nếu root là null, điều đó có nghĩa là cây trống và chúng ta tạo một nút mới ở gốc. Nếu không, chúng ta sẽ so sánh giá trị của nút với giá trị của gốc và quyết định xem có nên chèn nút vào bên trái hay bên phải không.

Xóa các nút

Việc xóa các nút trong cây nhị phân có thể phức tạp hơn một chút. Điều này phụ thuộc vào một số trường hợp, chẳng hạn như nút cần xóa có nút con hay không. Dưới đây là hàm C để xóa một nút trong cây nhị phân:

struct NodoArbol* eliminarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return raiz;
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = eliminarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = eliminarNodo(raiz->derecho, valor);
    } else {
        if (raiz->izquierdo == NULL) {
            struct NodoArbol* temp = raiz->derecho;
            free(raiz);
            return temp;
        } else if (raiz->derecho == NULL) {
            struct NodoArbol* temp = raiz->izquierdo;
            free(raiz);
            return temp;
        }

        struct NodoArbol* sucesor = encontrarSucesor(raiz->derecho);
        raiz->valor = sucesor->valor;
        raiz->derecho = eliminarNodo(raiz->derecho, sucesor->valor);
    }

    return raiz;
}

Trong hàm này, chúng ta kiểm tra xem giá trị của nút có nhỏ hơn, lớn hơn hay bằng giá trị của gốc hiện tại không. Tùy từng trường hợp, chúng tôi thực hiện các hành động sau:

Nếu giá trị nhỏ hơn, chúng ta sẽ di chuyển về bên trái của cây.
Nếu giá trị lớn hơn, chúng ta sẽ đi về bên phải của cây.
Nếu giá trị bằng nhau, chúng ta sẽ tìm nút kế nhiệm gần nhất của nút đó (nút nhỏ nhất trong cây con bên phải) và thay thế nó bằng nút hiện tại. Sau đó chúng ta loại bỏ nút kế thừa khỏi cây con bên phải.

Duyệt trong cây nhị phân

Duyệt là các hoạt động cho phép chúng ta truy cập tất cả các nút của cây nhị phân theo một thứ tự nhất định. Có ba loại tour du lịch phổ biến:

Duyệt theo thứ tự giữa (In-order traversal ): Duyệt cây con bên trái trước, sau đó đến nút hiện tại, và cuối cùng là cây con bên phải. Dưới đây là một hàm C thực hiện duyệt theo thứ tự giữa của cây nhị phân:

void inOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        inOrden(raiz->izquierdo);
        printf("%d ", raiz->valor);
        inOrden(raiz->derecho);
    }
}

Duyệt cây theo thứ tự trước (Pre-order traversal ): Duyệt nút hiện tại trước, sau đó là cây con bên trái, và cuối cùng là cây con bên phải. Dưới đây là một hàm C thực hiện duyệt cây nhị phân theo thứ tự trước:

void preOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        printf("%d ", raiz->valor);
        preOrden(raiz->izquierdo);
        preOrden(raiz->derecho);
    }
}

Duyệt theo thứ tự hậu tố : Duyệt cây con bên trái trước, sau đó là cây con bên phải, và cuối cùng là nút hiện tại. Dưới đây là một hàm C thực hiện duyệt cây nhị phân theo thứ tự hậu tố:

void postOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        postOrden(raiz->izquierdo);
        postOrden(raiz->derecho);
        printf("%d ", raiz->valor);
    }
}

Tìm kiếm các yếu tố

Việc tìm kiếm các phần tử trong cây nhị phân cho phép chúng ta nhanh chóng tìm thấy một giá trị cụ thể trong cấu trúc dữ liệu. Sau đây là hàm C để tìm kiếm một phần tử trong cây nhị phân:

struct NodoArbol* buscarElemento(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL || raiz->valor == valor) {
        return raiz;
    }

    if (valor < raiz->valor) {
        return buscarElemento(raiz->izquierdo, valor);
    } else {
        return buscarElemento(raiz->derecho, valor);
    }
}

Hàm này thực hiện tìm kiếm đệ quy trong cây nhị phân. Nếu giá trị của nút hiện tại bằng với giá trị được tìm kiếm thì nút đó sẽ được trả về. Nếu không, cây con bên trái hoặc bên phải sẽ được tìm kiếm dựa trên giá trị và quá trình được lặp lại cho đến khi tìm thấy giá trị hoặc đạt đến một nút null.

Thuật toán brute-force trong lập trình: chúng là gì, ví dụ và sự khác biệt với thuật toán quay lui.

Ví dụ về việc triển khai cây nhị phân trong C

Bây giờ chúng ta đã tìm hiểu những kiến thức cơ bản về cây nhị phân và cách triển khai chúng trong C, hãy cùng xem một số ví dụ thực tế.

Ví dụ 1: Tạo cây nhị phân

Giả sử chúng ta muốn tạo một cây nhị phân với các giá trị sau: 10, 5, 15, 3, 7, 13, 18. Sau đây là cách chúng ta có thể thực hiện trong C:

int main() {
    struct NodoArbol* raiz = NULL;

    raiz = insertarNodo(raiz, 10);
    raiz = insertarNodo(raiz, 5);
    raiz = insertarNodo(raiz, 15);
    raiz = insertarNodo(raiz, 3);
    raiz = insertarNodo(raiz, 7);
    raiz = insertarNodo(raiz, 13);
    raiz = insertarNodo(raiz, 18);

    return 0;
}

Trong ví dụ này, chúng ta tạo một con trỏ tới gốc của cây và sau đó sử dụng hàm insertarNodo để thêm các giá trị vào cây.

Ví dụ 2: Duyệt theo thứ tự của cây nhị phân

Để in các giá trị của cây nhị phân theo thứ tự, chúng ta có thể gọi hàm inOrden như sau:

int main() {
    // Crear el árbol binario

    printf("Recorrido en orden: ");
    inOrden(raiz);
    printf("\n");

    return 0;
}

Ví dụ này sẽ in các giá trị trong cây theo thứ tự tăng dần.

Câu hỏi thường gặp

1. Sự khác biệt giữa cây nhị phân và cây tìm kiếm nhị phân là gì?

Cây tìm kiếm nhị phân (BST) là một loại cây nhị phân đặc biệt trong đó các phần tử được sắp xếp sao cho các giá trị nhỏ hơn ở bên trái và các giá trị lớn hơn ở bên phải. Điều này cho phép tìm kiếm các phần tử hiệu quả hơn so với cây nhị phân thông thường.

2. Tôi có thể có các nút có giá trị trùng lặp trong cây nhị phân không?

Có, có thể có các nút có giá trị trùng lặp trong cây nhị phân. Tuy nhiên, tùy thuộc vào cách triển khai và các quy tắc cụ thể của cây nhị phân, có thể có nhiều cách khác nhau để xử lý các nút trùng lặp. Một số triển khai có thể cho phép các giá trị trùng lặp và lưu trữ chúng theo bất kỳ thứ tự nào, trong khi những triển khai khác có thể yêu cầu các giá trị trùng lặp phải được xử lý đặc biệt hoặc loại bỏ.

3. Làm thế nào để xóa một nút cụ thể khỏi cây nhị phân?

Để xóa một nút cụ thể khỏi cây nhị phân, bạn cần làm theo các bước sau:

Tìm nút bạn muốn xóa bằng cách sử dụng tìm kiếm cây.
Hãy xem xét các trường hợp loại trừ khác nhau:
- Nếu nút không có nút con, bạn chỉ cần xóa nút đó và giải phóng bộ nhớ cho nút đó.
- Nếu nút chỉ có một nút con, bạn có thể thay thế nút đó bằng nút con của nó.
- Nếu nút có hai nút con, bạn phải tìm nút kế nhiệm gần nhất (nút nhỏ nhất trong cây con bên phải) và thay thế giá trị của nút cần xóa bằng giá trị của nút kế nhiệm. Sau đó xóa người kế nhiệm khỏi cây.
Điều chỉnh các liên kết và con trỏ khi cần thiết để duy trì cấu trúc cây chính xác.

5 phần của thuật toán lập trình

4. Cây nhị phân đầy đủ là gì?

Cây nhị phân đầy đủ là một loại cây nhị phân đặc biệt trong đó tất cả các cấp, ngoại trừ cấp cuối cùng, đều được điền đầy đủ và các nút của cấp cuối cùng nằm càng xa về bên trái càng tốt. Điều này có nghĩa là tất cả các nút đều có hai nút con, ngoại trừ các nút ở cấp độ cuối cùng có thể có một hoặc không có nút con nào.

5. Chiều cao của cây nhị phân là bao nhiêu?

Chiều cao của cây nhị phân là độ dài của đường dẫn dài nhất từ gốc đến lá. Nói cách khác, đó là số cạnh tối đa giữa gốc và bất kỳ lá nào trong cây. Chiều cao được đo theo số lượng cấp, do đó một cây chỉ có một nút có chiều cao là 0 và một cây trống sẽ không có chiều cao.

6. Khi nào tôi nên sử dụng cây nhị phân trong chương trình của mình?

Cây nhị phân hữu ích trong nhiều tình huống khác nhau. Một số trường hợp phổ biến mà bạn có thể sử dụng cây nhị phân bao gồm:

Tra cứu phần tử hiệu quả: Nếu bạn cần tra cứu nhanh các phần tử trong cấu trúc dữ liệu, cây nhị phân có thể cung cấp khả năng truy cập dữ liệu hiệu quả.
Biểu diễn các mối quan hệ phân cấp: Cây nhị phân lý tưởng để biểu diễn các mối quan hệ phân cấp, chẳng hạn như cấu trúc thư mục trong hệ thống tập tin.
Sắp xếp dữ liệu: Bạn có thể sử dụng cây tìm kiếm nhị phân để sắp xếp dữ liệu hiệu quả và thực hiện tìm kiếm, chèn và xóa theo thời gian logarit.

Hãy nhớ đánh giá các yêu cầu của bạn và cân nhắc mức độ phức tạp của các phép toán trên cây nhị phân trước khi quyết định sử dụng chúng trong chương trình của bạn.

Kết luận

Trong hướng dẫn toàn diện này, chúng ta đã khám phá các khái niệm cơ bản về cây nhị phân trong C. Chúng ta đã tìm hiểu về cấu trúc của cây, cách chèn và xóa các nút, thực hiện duyệt và tìm kiếm các phần tử trong cây nhị phân.

Chúng tôi hy vọng hướng dẫn này đã cung cấp cho bạn sự hiểu biết vững chắc về cây nhị phân và cách triển khai chúng trong C. Cây nhị phân là cấu trúc dữ liệu linh hoạt và mạnh mẽ có thể giúp bạn giải quyết nhiều vấn đề trong lập trình.

Hãy nhớ thực hành và thử nghiệm với các ví dụ được cung cấp để củng cố hiểu biết của bạn về cây nhị phân trong C. Chúc bạn may mắn trên hành trình học tập và phát triển phần mềm!