Cấu trúc dữ liệu cây nhị phân trong lập trình C/C++
Cây nhị phân là một cấu trúc dữ liệu rất phổ biến 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 nhị 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++
Khái niệm về cây nhị phân
Cây nhị phân là một cấu trúc dữ liệu cây đặc biệt, trong đó mỗi nút có tối đa hai nút con, được gọi là nút trái và nút phải. Trong một cây nhị phân, nút gốc(root) là nút đầu tiên của cây, và nút lá là nút không có con. Cây nhị phân được sử dụng rộng rãi để lưu trữ và tìm kiếm dữ liệu.
Triển khai cấu trúc cây nhị phân lập trình C/C++
Trong lập trình C/C++, chúng ta có thể triển khai cây nhị phân bằng cách sử dụng con trỏ.
Để triển khai cây nhị phân, chúng ta sẽ cần một cấu trúc dữ liệu để biểu diễn một nút trong cây nhị phân. Mỗi nút trong cây nhị phân bao gồm một giá trị và hai con trỏ, một con trỏ trỏ đến nút con trái và một con trỏ trỏ đến nút con phải của nút đó. Đây là cấu trúc dữ liệu cho một nút trong cây nhị phân:
//Định nghĩa dữ liệu 1 nút
struct Node {
int value; //Giá trị của nút(giá trị có thể là 1 số, 1 chuỗi, hay 1 struct)
struct Node *left; //Con trỏ trỏ tới nút con trái
struct Node *right; //Con trỏ trỏ tới nút con phải
};
>>XEM THÊM: Tìm hiểu các toán tử thao tác bit trong lập trình C/C++
Cây nhị phân là một cấu trúc nút liên kết xuất phát từ nút root, vậy ta khai báo nút gốc của cây như sau.
Node *root;
Sau khi định nghĩa các cấu trúc dữ liệu cho cây nhị phân, chúng ta sẽ bắt đầu triển khai các hàm thao tác với cây nhị phân. Các hàm bao gồm hàm tạo nút, chèn nút vào cây, duyệt cây....
Để chèn được nút nào cây, chúng ta nên có một hàm riêng để tạo nút mới. Đây là hàm tạo một nút.
//Hàm tạo một nút mới
tNode *newNode(int data){
tNode *node = new tNode; //Khai báo 1 nút
node->data = data; //Gắn data của nút
//Vì nút mới nên sẽ không chưa có nút con trái và phải, vậy ta cho trỏ tới rỗng
node->pLeft = NULL;
node->pRight = NULL;
return node; //Trả về nút cho hàm
}
Để chèn giá trị vào cây nhị phân, chúng ta sử dụng một hàm chèn. Hàm này sẽ chèn giá trị vào cây bằng cách nếu nút con bên trái của nút root là rỗng thì chèn vào con bên trái, con bên phải nút root rỗng thì chèn vào con bên phải. Và nếu không có con nào của nút gốc rỗng, vậy ta sẽ chèn nút này vào con bên trái, và con trước đó sẽ được đẩy thành con trái của nút này.
//Hàm chèn nút vào cây nhị phân
void insertNode(tNode *p, int value){
tNode *node = newNode(value); //Tạo một nút mới
if (p->pLeft == NULL){
p->pLeft = node;
}else if (p->pRight == NULL) {
p->pRight = node;
}else{
node->pLeft = p->pLeft;
p->pLeft = 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
Đã có hàm chèn nút, hàm xuất cây nhị phân theo NLR (Node -> Left -> Right) sử dụng đệ quy sẽ viết như sau:
void NLR(tNode *root){
if(root!=NULL){
if(root!=NULL){
cout<<root->data<<" ";
}
NLR(root->pLeft);
NLR(root->pRight);
}
}
Vậy đã có các hàm ta có thể viết chương trình chèn phần tử và xuất ra cây nhị phân đơn giản.
#include <iostream>
using namespace std;
//Định nghĩa 1 nút
struct tNode{
int data;
tNode *pLeft, *pRight;
};
tNode *root; //Khai báo nút gốc - root
//Hàm tạo ra một nút
tNode *newNode(int data){
tNode *node = new tNode;
node->data = data;
node->pLeft = NULL;
node->pRight = NULL;
return node;
}
//Hàm chèn phần tử vào 1 nút
void insertNode(tNode *p, int value){
tNode *node = newNode(value);
if (p->pLeft == NULL){
p->pLeft = node;
}else if (p->pRight == NULL) {
p->pRight = node;
}else{
node->pLeft = p->pLeft;
p->pLeft = node;
}
}
//Hàm duyệt cây nhị phân theo NLR
void NLR(tNode *root){
if(root!=NULL){
if(root!=NULL){
cout<<root->data<<" ";
}
NLR(root->pLeft);
NLR(root->pRight);
}
}
int main()
{
//Tạo nút gốc
root = newNode(4);
//Chèn các phần tử nút vào cây
insertNode(root, 5);
insertNode(root, 76);
insertNode(root, 65);
insertNode(root, 74);
insertNode(root, 95);
insertNode(root, 57);
insertNode(root, 54);
cout<<"Hiển thị cây theo NLR:";
NLR(root);
}
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á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++