Thứ Sáu, 12 Tháng Tư 2024
Trang chủLập trìnhLậ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ấ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ấu trúc dữ liệu cây nhị phân trong lập trình C/C++
Hình ảnh minh họa 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++
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