hêm Node vào cây nhị phân tìm kiếm - Cấu trúc cây

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.

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

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é!!