CÂY NHỊ PHÂN
CÂY ĐỎ ĐEN
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
MỚI CẬP NHẬT

Tìm kiếm Node trên cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm một Node trên cây nhị phân tìm kiếm. Đây là thao tác đặc biệt nhất trong cây nhị phân tìm kiếm, vì nó được thực hiện một cách dễ dàng và nhanh chóng.

test php

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

Chúng ta sẽ tìm hiều về cách hoạt động của hàm tìm kiếm trong cây như thế nào, sau đó thực hiện một ví dụ tìm kiếm cụ thể để các bạn hiểu rõ hơn.

1. Tìm kiếm Node trong cây nhị phân tìm kiếm

Như các bạn đã biết thì thao tác tìm kiếm là một thao tác rất phổ biến trong các cấu trúc dữ liệu. Mỗi cấu trúc có mỗi cách tìm kiếm khác nhau, trong phần này các bạn hãy cùng mình tìm hiểu xem cách tìm kiếm trong cây nhị phân tìm kiếm như thế nào nhé.

Để thực hiện tìm kiếm đầu tiên các bạn phải nắm được cấu trúc lưu trữ của cây nhị phân tìm kiếm như thế nào, khi đó các bạn mới dựa vào đó để tìm kiếm. Khi lưu trữ các phần tử nhỏ hơn Node gốc (root) được lưu trữ ở cây con trái và các phần tử lớn hơn root được lưu ở cây con phải. Vì vậy khi tìm kiếm ta cũng thực hiện so sánh với root để tìm.

Bài viết này được đăng tại [free tuts .net]

tim kiem cay 1 PNG

Việc tìm kiếm một Node trong cây đơn giản chỉ là kiểm tra xem phần tử đó còn tồn tại trong cây hay không, nếu có thì trả về Node đó, ngược lại nếu không thì trả về NULL.

Ta có một hàm TimKiem() với tham số truyền vào là một cây t và một số nguyên x (ta sẽ tìm một số nguyên x trong cây số nguyên).

Việc đầu tiền là ta sẽ kiểm tra xem cây rỗng hay không, nếu cây rỗng thì trả về NULL, nếu cây có phần tử thì khi đó ta bắt đầu thực hiện tìm kiếm. Ta sẽ có 3 trường hợp khi thực hiện tìm kiếm trong cây:

Trường hợp 1: Phần tử x cần tìm kiếm nhỏ hơn t -> data.

Khi đó ta sẽ thực hiện gọi đệ quy hàm TimKiem() để duyệt sang bên cây con trái đề tìm phần tử x.

Trường hợp 2: Phần tử x cần tìm kiếm lớn hơn t -> data.

Khi đó ta sẽ thực hiện gọi đệ quy hàm TimKiem() để duyệt sang bên cây con phải để tìm phần tử x.

Trường hợp 3: Phần tử x cần tìm kiếm bằng t -> data.

Trong trường hợp này đơn giản ta chỉ cần trả về t -> data, vì đây chính là giá trị cần tìm.

// nếu node có tồn tại trong cây thì trả về cái node đó - còn không tồn tại thì trả về NULL
NODE* TimKiem(TREE t, int x)
{ 
	// nếu cây rỗng
	if (t == NULL)
	{
		return NULL;
	}
	else
	{
		// nếu phần tử cần tìm kiếm mà nhỏ hơn node gốc thì duyệt(đệ quy) sang bên trái để tìm
		if (x < t->data)
		{
			TimKiem(t->pLeft, x);
		}
		else if (x > t->data) // duyệt sang bên phải
		{
			TimKiem(t->pRight, x);
		}
		else // <=> t->data == x
		{
			return t; // trả về node cần tìm kiếm
		}
	}

}

2. Ví dụ: Tìm kiếm phần tử x trong cây nhị phân tìm kiếm

Trong ví dụ về tìm kiếm phần tử x trong cây nhị phân, mình sẽ thực hiện tìm kiếm một số nguyên x trong cây số nguyên bao gồm các số sau: 3, 5, -2, 0, 9, 6, 8.

Giả sử mình cần tìm số 8 trong dãy các số trên, khi đó việc tìm kiếm sẽ thực hiện theo các bước sau: Biểu diễn bằng mũi tên màu đỏ.

tim kiem cay 2 PNG

Đầu tiên nó sẽ so sánh số 8 (số cần tìm) với root là số 3, vì 8 > 3 nên nó sẽ gọi đệ quy và duyệt sang cây con phải. Tiếp tục so sánh với số 5, 8 > 5 vì vậy gọi đệ quy và duyệt sang cây con phải.

Đến đây tiếp tục so sánh với số 9, khi này 8 < 9 nên sẽ gọi đệ quy và duyệt sang trái. Khi duyệt sang trái tiếp tục só sánh với số 6 , vì 8 > 6 nên sẽ gọi đệ quy và duyệt qua bên phải. Đến đây khi so sánh thì số cần tìm là số 8 lại bằng chính với t -> data, khi đó đã tìm thấy số 8.

#include<iostream>
using namespace std;
// nhập vào cây nhị phân tìm kiếm các số nguyên
// khai báo cấu trúc 1 cái node trong cây nhị phân tìm kiếm
struct node
{
	int data; // dữ liệu chứa trong 1 cái node
	struct node *pLeft; // con trỏ liên kết với cái node bên trái <=> cây con trái
	struct node *pRight; // con trỏ liên kết với cái node bên phải <=> cây con phải
};
typedef struct node NODE;
typedef NODE* TREE;

// hàm khởi tạo cây nhị phân tìm kiếm
void KhoiTaoCay(TREE &t)
{
	t = NULL;
}

// hàm thêm 1 cái phần tử vào cây
void ThemNodeVaoCay(TREE &t, int x)
{
	// nếu cây rỗng
	if (t == NULL)
	{
		NODE *p = new NODE;
		p->data = x;
		p->pLeft = NULL;
		p->pRight = NULL;
		t = p;
	}
	else
	{
		// nếu phần tử thêm vào mà nhỏ hơn nút gốc thì sẽ duyệt qua bên trái
		if (x < t->data)
		{
			ThemNodeVaoCay(t->pLeft, x);
		}
		else if (x > t->data)
		{
			ThemNodeVaoCay(t->pRight, x);
		}
	}
}

// hàm xuất phần tử trong cây nhị phân tìm kiếm
void NLR(TREE t)
{
	if (t != NULL)
	{
		// xử lí
		cout << t->data << "  ";
		NLR(t->pLeft);
		NLR(t->pRight);
	}
}

// nếu node có tồn tại trong cây thì trả về cái node đó - còn không tồn tại thì trả về NULL
NODE* TimKiem(TREE t, int x)
{ 
	// nếu cây rỗng
	if (t == NULL)
	{
		return NULL;
	}
	else
	{
		// nếu phần tử cần tìm kiếm mà nhỏ hơn node gốc thì duyệt(đệ quy) sang bên trái để tìm
		if (x < t->data)
		{
			TimKiem(t->pLeft, x);
		}
		else if (x > t->data) // duyệt sang bên phải
		{
			TimKiem(t->pRight, x);
		}
		else // <=> t->data == x
		{
			return t; // trả về node cần tìm kiếm
		}
	}
}

// hàm nhập cây nhị phân tìm kiếm
void Menu(TREE &t)
{
	int luachon;
	while(true)
	{
		cout << "\n\n\t\t ============ MENU ============";
		cout << "\n1. Nhập phần tử trong cây";
		cout << "\n2. Duyệt cây";
		cout << "\n3. Tìm kiếm phần tử trong cây";
		cout << "\n0. Thoát";
		cout << "\n\n\t\t =============  END  =============";

		cout << "\nNhập lựa chọn của bạn: ";
		cin >> luachon;

    if(luachon < 0 || luachon > 3){
      cout<<"\nLựa chọn của bạn không hợp lệ";
    }
		else if (luachon == 1)
		{
			int x;
			cout << "\nNhập giá trị: ";
			cin >> x;
			ThemNodeVaoCay(t, x);
		}
		else if (luachon == 2)
		{
			cout << "\n\t Cây nhị phân tìm kiếm\n";
			NLR(t);
		}
		else if (luachon == 3)
		{
			int x;
			cout << "\nNhập phần tử cần tìm kiếm: ";
			cin >> x;
			NODE *p = TimKiem(t, x);
			if (p == NULL)
			{
				cout << "\nPhần tử " << x << " không tồn tại trong cây";
			}
			else
			{
				cout << "\nPhần tử " << x << " có tồn tại trong c";
			}
		}
		else
		{
			break;
		}
	}
}


int main()
{
	TREE t;
	KhoiTaoCay(t);
	Menu(t);

	cout<<"\n-------------------------------------\n";
        cout<<"Chương trình này được đăng tại Freetuts.net";
}

Kết quả: Thực hiện kiểm tra hai số x = 0 và x = 10 trong dãy số: 3, 5, -2, 0, 9, 6, 8.

tim kiem cay 3 PNG

3. Kết luận

Như vậy là chúng ta đã tìm hiểu xong về cách tìm kiếm phần tử trong cây nhị phân tìm kiếm. Ở ví dụ trên mình thực hiện tìm kiếm số nguyên x trong cây số nguyên, các bạn có thể tự thực hành bằng cách tìm số nguyên tố trong cây số nguyên để có thể luyện tập. Ở bài tiếp theo mình sẽ tiếp tục thực hiện các thao tác thường gặp trong cây nhị phân, các bạn hay chú ý theo dõi nhé !!

Cùng chuyên mục:

Tìm các số chẵn lẻ bằng Queue và Stack

Tìm các số chẵn lẻ bằng Queue và Stack

Để làm được bài này các bạn cần có kiến thức về cấu trúc Queue…

Cài đặt hàng đợi Queue bằng mảng một chiều

Cài đặt hàng đợi Queue bằng mảng một chiều

Chúng ta sẽ cùng nhau tìm hiểu về cách cài đặt hàng đợi Queue bằng…

Cài đặt hàng đợi Queue bằng danh sách liên kết

Cài đặt hàng đợi Queue bằng danh sách liên kết

Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu…

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Bài tập kiểm tra số nguyên tố bằng Stack

Bài tập kiểm tra số nguyên tố bằng Stack

Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết…

Bài tập chuyển đổi cơ số bằng Stack

Bài tập chuyển đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài toán chuyển đổi cơ…

Cài đặt Stack bằng mảng một chiều

Cài đặt Stack bằng mảng một chiều

Chúng ta sẽ lần lượt thực hiện tạo các hàm cơ bản cho Stack như:…

Cài đặt Stack bằng danh sách liên kết

Cài đặt Stack bằng danh sách liên kết

Chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh…

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Xóa Node khỏi cây đỏ đen

Xóa Node khỏi cây đỏ đen

Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ…

Thêm Node mới vào cây đỏ đen

Thêm Node mới vào cây đỏ đen

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc dữ liệu…

Xóa Node khỏi cây nhị phân tìm kiếm

Xóa Node khỏi cây nhị phân tìm kiếm

Chúng ta sẽ cùng nhau thực hiện xóa Node có 1 con, Node có 2…

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Chúng ta sẽ thực hiện một vài cách tìm ra giá trị MAX và MIN…

Xuất Node con và lá trong cây nhị phân tìm kiếm

Xuất Node con và lá trong cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xuất các Node con…

Duyệt cây nhị phân tìm kiếm

Duyệt cây nhị phân tìm kiếm

Chúng ta sẽ tìm hiểu lần lượt 6 cách duyệt cây nhị phân tìm kiếm:

Thêm Node vào cây nhị phân tìm kiếm

Thêm Node vào cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu…

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Trong bài này mình sẽ giới thiệu các bạn một trong các cấu trúc dữ…

Gộp hai danh sách liên kết đôi

Gộp hai danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu về cách nối hai danh sách liên kết…

Tìm kiếm phần tử k trong danh sách liên kết đôi

Tìm kiếm phần tử k trong danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu cách tìm kiếm một phần tử k trong…

Top