Giới thiệu về cấu trúc cây nhị phân

Cây nhị phân là một cấu trúc dữ liệu quan trọng được sử dụng rộng rãi trong nhiều ứng dụng của lập trình. Bài viết này sẽ giới thiệu cách thực hiện và xử lý cây nhị phân trong ngôn ngữ C.

1. Định nghĩa cơ bản

Một cây nhị phân bao gồm các nút (node), mỗi nút có tối đa hai con, gọi là con trái (left child) và con phải (right child). Dưới đây là định nghĩa cơ bản của một nút trong cây nhị phân:

typedef struct Node {
    char data;
    struct Node* left;
    struct Node* right;
} Node;

2. Tạo cây nhị phân

Hàm dưới đây cho phép tạo cây nhị phân theo thứ tự duyệt trước (preorder traversal):

Node* createTree() {
    char ch;
    scanf(" %c", &ch);
    
    if (ch == '#') {
        return NULL; // Kết thúc khi gặp ký tự '#'
    } else {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = ch;
        newNode->left = createTree();  // Tạo con trái
        newNode->right = createTree(); // Tạo con phải
        return newNode;
    }
}

3. Duyệt cây theo thứ tự giữa (inorder traversal)

Dưới đây là hàm duyệt cây theo thứ tự giữa, tức là duyệt qua tất cả các nút từ trái sang phải:

void inorderTraversal(Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);  // Duyệt con trái
        printf("%c ", root->data);     // Xuất giá trị nút hiện tại
        inorderTraversal(root->right); // Duyệt con phải
    }
}

4. Đếm số nút trong cây

Số lượng nút trong cây có thể được tính bằng cách duyệt qua từng nút:

int countNodes(Node* root) {
    if (root == NULL) {
        return 0; // Trả về 0 nếu cây rỗng
    } else {
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
}

5. Tính độ sâu của cây

Độ sâu của cây là khoảng cách lớn nhất từ gốc đến lá. Hàm sau đây giúp tính toán độ sâu:

int treeDepth(Node* root) {
    if (root == NULL) {
        return 0; // Độ sâu của cây rỗng là 0
    } else {
        int leftDepth = treeDepth(root->left);   // Độ sâu của nhánh trái
        int rightDepth = treeDepth(root->right); // Độ sâu của nhánh phải
        return (leftDepth > rightDepth) ? (leftDepth + 1) : (rightDepth + 1);
    }
}

6. Sao chép cây

Hàm sao chép cây dưới đây tạo ra một bản sao hoàn chỉnh của cây ban đầu:

Node* copyTree(Node* original) {
    if (original == NULL) {
        return NULL; // Trả về NULL nếu gốc rỗng
    } else {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = original->data;
        newNode->left = copyTree(original->left);  // Sao chép con trái
        newNode->right = copyTree(original->right); // Sao chép con phải
        return newNode;
    }
}

7. Ví dụ chương trình đầy đủ

Dưới đây là một ví dụ hoàn chỉnh sử dụng các hàm trên:

#include 
#include 

typedef struct Node {
    char data;
    struct Node* left;
    struct Node* right;
} Node;

Node* createTree();
void inorderTraversal(Node* root);
int countNodes(Node* root);
int treeDepth(Node* root);
Node* copyTree(Node* original);

int main() {
    Node* tree = createTree();
    inorderTraversal(tree);
    printf("\nSố nút: %d\n", countNodes(tree));
    printf("Độ sâu: %d\n", treeDepth(tree));

    Node* copiedTree = copyTree(tree);
    printf("Duyệt cây đã sao chép: ");
    inorderTraversal(copiedTree);

    return 0;
}