CÂY NHỊ PHÂN
CÂY ĐỎ ĐEN
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
Dự án mới của mình là gamehow.net, mời anh em ghé thăm và góp ý ạ.

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ủa cây nhị phân tìm kiếm và cách thêm một Node vào cây nhị phân tìm kiếm.

Chúng ta sẽ tìm hiểu lần lượt về cấu trúc một Node trong cây và khởi tạo cho cây như thế nào. Sau đó sẽ thực hiện thêm Node vào cây.

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.

1. Cấu trúc dữ liệu của cây nhị phân tìm kiếm

Như các bạn đã học ở bài trước thì cây nhị phân tìm kiếm là một cấu trúc dữ liệu, vì vậy ta cần khởi tạo cấu trúc dữ liệu cho nó. Trong phần này ta có khởi tạo cấu trúc của một Node và khởi tạo cây.

Khởi tạo Node

Trong một Node ta có ba thành phần như sau:

  • Data là giá trị của Node
  • pLeft là con trỏ trỏ đến cây con bên trái Node
  • pRight là con trỏ trỏ đến cây con bên phải Node

cay cau truc node PNG

struct node
{
	int data; // dữ liệu của node ==> dữ liệu mà node sẽ lưu trữ
	struct node *pLeft; // node liên kết bên trái của cây <=> cây con trái
	struct node *pRight; // node liên kết bên phải của cây <=> cây con phải
};

Khởi tạo cây

Để làm việc được với cây ta cần khởi tạo cây và gán giá trị cho nó như danh sach liên kết đơn vậy.

Chúng ta sẽ tạo một cây t có tham số truyền vào cho hàm khởi tạo cây là một con trỏ *Node (đây là node vừa được khởi tạo ở trên). Trong hàm KhoiTaoCay() ta thực hiện cho khởi tạo cây bằng rỗng: t = null

/* khởi tạo cây */
void KhoiTaoCay(TREE &t)
{
	t = NULL; // cây rỗng
}

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

Sau khi chúng ta đã tạo cấu trúc dữ liệu cho cây, ta sẽ thực hiện thêm Node vào cây nhị phân tìm kiếm.

Trong hàm ThemNodeVaoCay() ta truyền hai tham số là cây t và Node x.

Để thêm Node mới vào cây ta cần xét hai trường hợp:

Trường hợp 1: Trong cây không có phần tử nào (cây rỗng).

Ta sử dụng struct dode tạo một Node mới để thêm vào cây, sau đó thêm dữ liệu x vào data (p->data = x).

Khởi tạo cho con trỏ pLeft và pRight bằng Null. Vì cây ban đầu không có phân tử nào, vì vậy phần tử đầu tiên khi thêm vào chính là phần tử gốc t = p

Trường hợp 2: Trong cây có tồn tại phần tử.

Khi này trong cây đã có phần tử, cũng như đã có phần tử gốc (root). Vì vậy khi ta thêm Node mới vào cần so sánh Node này với Node gốc để có thể thêm chính xác vị trí cần thêm.

Như ta đã học ở bài trước thì một phần tử khi được thêm vào nếu nhỏ hơn phần tử gốc thì nằm ở bên cây con trái và nếu lớn hơn phần tử gốc thì nằm ở bên cây con phải.

Trong trường hợp này ta sẽ sử dụng đệ quy để thực hiện gọi lại hàm ThemNodeVaoCay() duyệt qua trái để thêm phần tử x nếu x < root và duyệt qua phải nếu x > root

/* hàm thêm phần tử x vào cây nhị phân */
void ThemNodeVaoCay(TREE &t, int x)
{
	// nếu cây rỗng
	if (t == NULL)
	{
		NODE *p = new NODE; // khởi tạo 1 cái node để thêm vào cây
		p->data = x;// thêm dữ liệu x vào data
		p->pLeft = NULL;
		p->pRight = NULL;
		t = p;// node p chính là node gốc <=> x chính là node gốc
	}
	else // cây có tồn tại phần tử
 	{
		// nếu phần tử thêm vào mà nhỏ hơn node gốc ==> thêm nó vào bên trái
		if (t->data > x)
		{
			ThemNodeVaoCay(t->pLeft, x); // duyệt qua trái để thêm phần tử x
		}
		else if (t->data < x) // nếu phần tử thêm vào mà lớn hơn node gốc ==> thêm nó vào bên phải
		{
			ThemNodeVaoCay(t->pRight, x); // duyệt qua phải để thêm phần tử x
		}
	}
}

3. Kết luận

Như vậy là chúng ta đã tìm hiểu xong về cấu trúc dữ liệu của cây nhị phân tìm kiếm, cũng như cách thêm một Node vào cây. Đây là bước đầu tiên để tạo dữ liệu cho cây. Ở bài tiếp theo mình sẽ thực hiện duyệt cây để có thể kiếm tra được các thao tác của ta trên cây đúng hay sai. Các bạn 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…

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

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…

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:

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