Cây đa phân là một cấu trúc dữ liệu rất phổ biến và được sử dụng nhiều trong lập trình. Trong bài viết này, chúng ta sẽ cùng tìm hiểu về cấu trúc dữ liệu cây đa phân trong ngôn ngữ 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ấu trúc dữ liệu cây đa phân
Cây đa phân là một cấu trúc dữ liệu phổ biến trong lập trình, được sử dụng để lưu trữ và quản lý các dữ liệu phân cấp. Trong bài viết này, mình sẽ hướng dẫn bạn cách cài đặt cây đa phân trong lập trình C.
Trước khi bắt đầu, hãy xác định các thành phần cơ bản của cây đa phân:
- Node: đại diện cho một phần tử trong cây đa phân.
- Edge: đại diện cho một liên kết giữa các node trong cây.
- Root: đại diện cho node gốc của cây.
- Parent: đại diện cho node cha của một node.
- Child: đại diện cho các node con của một node.
XEM THÊM: Khóa học lập trình C/C++ từ A-Z cho người mới – Giảm giá 40% hôm nay
Triển khai cấu trúc cây đa phân lập trình C/C++
- Khai báo cấu trúc Node:
typedef struct Node {
int data; // dữ liệu của node
struct Node* parent; // con trỏ tới node cha
struct Node** children; // mảng con trỏ tới các node con
int numChildren; // số lượng node con
} Node;
2. Tạo ra một node mới bằng cách sử dụng hàm malloc:
Node* newNode(int data) {
Node* node = (Node*) malloc(sizeof(Node));
node->data = data;
node->parent = NULL;
node->children = NULL;
node->numChildren = 0;
return node;
}
3. Thêm một node con vào cây bằng cách sử dụng hàm addChild:
void addChild(Node* parent, Node* child) {
if (parent->children == NULL) {
parent->children = (Node**) malloc(sizeof(Node*));
parent->children[0] = child;
} else {
parent->children = (Node**) realloc(parent->children, (parent->numChildren + 1) * sizeof(Node*));
parent->children[parent->numChildren] = child;
}
child->parent = parent;
parent->numChildren++;
}
- Khóa học lập trình C/C++ từ A-Z cho người mới – Giảm giá 40% hôm nay
- Khóa học C# từ cơ bản tới nâng cao – Đăng ký hôm nay giảm 40%
- Khóa học Java cơ bản dành cho người mới bắt đầu- Giảm 40% hôm nay
- Khóa học lập trình Android từ cơ bản đến thành thạo – Giảm ngay 40%
4. Xóa một node con khỏi cây bằng cách sử dụng hàm removeChild:
void removeChild(Node* parent, Node* child) {
int i, j;
for (i = 0; i < parent->numChildren; i++) {
if (parent->children[i] == child) {
for (j = i; j < parent->numChildren - 1; j++) {
parent->children[j] = parent->children[j+1];
}
parent->children = (Node**) realloc(parent->children, (parent->numChildren - 1) * sizeof(Node*));
parent->numChildren--;
child->parent = NULL;
break;
}
}
}
5. Duyệt cây đa phân bằng cách sử dụng đệ quy:
void traverseTree(Node* node) {
printf("%d\n", node->data);
int
int i;
for (i = 0; i < node->numChildren; i++) {
traverseTree(node->children[i]);
}
6. Giải phóng bộ nhớ sau khi hoàn thành việc sử dụng cây:
void freeTree(Node* node) {
int i;
for (i = 0; i < node->numChildren; i++) {
freeTree(node->children[i]);
}
free(node->children);
free(node);
}
Với những bước trên, bạn đã có thể cài đặt và sử dụng cây đa phân trong lập trình C. Để thêm tính năng và tối ưu hóa cây đa phân, bạn có thể tham khảo thêm các tài liệu và ví dụ về cách sử dụng cây đa phân.
XEM THÊM: Khóa học C# từ cơ bản tới nâng cao – Đăng ký hôm nay giảm 40%
7. Chương trình minh họa cấu trúc dữ liệu cây đa phân
Để minh họa cách sử dụng cây đa phân, chúng ta hãy tạo ra một cây đa phân và duyệt cây đó bằng cách sử dụng các hàm đã xây dựng bên trên.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data; // d? li?u c?a node
struct Node* parent; // con tr? t?i node cha
struct Node** children; // m?ng con tr? t?i các node con
int numChildren; // s? lu?ng node con
} Node;
Node* newNode(int data) {
Node* node = (Node*) malloc(sizeof(Node));
node->data = data;
node->parent = NULL;
node->children = NULL;
node->numChildren = 0;
return node;
}
void addChild(Node* parent, Node* child) {
if (parent->children == NULL) {
parent->children = (Node**) malloc(sizeof(Node*));
parent->children[0] = child;
} else {
parent->children = (Node**) realloc(parent->children, (parent->numChildren + 1) * sizeof(Node*));
parent->children[parent->numChildren] = child;
}
child->parent = parent;
parent->numChildren++;
}
void removeChild(Node* parent, Node* child) {
int i, j;
for (i = 0; i < parent->numChildren; i++) {
if (parent->children[i] == child) {
for (j = i; j < parent->numChildren - 1; j++) {
parent->children[j] = parent->children[j+1];
}
parent->children = (Node**) realloc(parent->children, (parent->numChildren - 1) * sizeof(Node*));
parent->numChildren--;
child->parent = NULL;
break;
}
}
}
void traverseTree(Node* node) {
printf("%d\n", node->data);
int i;
for (i = 0; i < node->numChildren; i++) {
traverseTree(node->children[i]);
}
}
void freeTree(Node* node) {
int i;
for (i = 0; i < node->numChildren; i++) {
freeTree(node->children[i]);
}
free(node->children);
free(node);
}
int main() {
Node* root = newNode(1);
Node* node2 = newNode(2);
Node* node3 = newNode(3);
Node* node4 = newNode(4);
Node* node5 = newNode(5);
addChild(root, node2);
addChild(root, node3);
addChild(node2, node4);
addChild(node2, node5);
traverseTree(root);
freeTree(root);
return 0;
}
Kết quả đầu ra của chương trình sẽ là:
1
2
4
5
3
Trong đó, node 1 là node gốc, node 2 và node 3 là các node con của node 1, node 4 và node 5 là các node con của node 2.
Trong hàm main, chúng ta đã tạo ra một cây đa phân với 5 node và duyệt cây đó bằng cách sử dụng hàm traverseTree. Sau đó, chúng ta giải phóng bộ nhớ bằng cách sử dụng hàm freeTree.
Nếu bạn muốn thêm tính năng cho cây đa phân trên, bạn có thể tạo ra các hàm khác để thêm, xóa, sửa các node trong cây đa phân hoặc tính toán độ sâu của cây, đếm số lượng node trong cây, tìm kiếm các node trong cây, và nhiều tính năng khác.
Tóm lại, cây đa phân là một cấu trúc dữ liệu phổ biến trong lập trình và cài đặt cây đa phân trong lập trình C không quá phức tạp. Bạn có thể tham khảo bài viết này để tạo ra một cây đa phân đơn giản và sử dụng nó cho các mục đích của riêng mình.
[Xem tất cả bài viết chủ đề C/C++ tại đây]
XÊM THÊM Hiểu về cấu trúc dữ liệu cây 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 ngăn xếp 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++ Tìm hiểu các toán tử thao tác bit 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++ 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++
