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

Trong bài viết này, codehow sẽ hướng dẫn các bạn cách thêm node vào cây nhị phân tìm kiếm. Đây là một thao tác rất quan trọng khi sử dụng cây nhị phân tìm kiếm, bởi nó là bước căn bản để các bạn có thể thực hiện các thao tác khác.

Chúng ta sẽ tìm hiểu về cấu trúc của cây nhị phân, khởi tạo cây nhị phân và node. Sau đó sẽ tìm hiểu về cách thêm node vào cây nhị phân tìm kiếm.

Cây nhị phân tìm kiếm là gì? Cấu trúc dữ liệu của nó

Để có thể sử dụng được, ta cần khai báo và khởi tạo cấu trúc dữ liệu của cây nhị phân tìm kiếm. Sau đó là khởi tạo cấu trúc node trong cây, hãy bắt đầu tìm hiểu cùng mình thôi nhé.

Khởi tạo cây nhị phân tìm kiếm:

Tương tự như DSLK đơn hay DSLK đôi, ta cần khai báo cây sau đó khởi tạo giá trị NULL cho cây.

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

Trong hàm khởi tạo, ta truyền tham số là một cây nhị phân tìm kiếm t, cấu trúc cây này mình sẽ hướng dẫn ngay bên dưới đây. Bên trong hàm ta khởi tạo cho cây nhị phân tìm kiếm t = NULL.

Khởi tạo node:

Đối với việc tạo node cho cây, ta cần quan tâm đến ba thông số đó là:

• Giá trị của node (data).
• Con trỏ trỏ đến cây con bên trái (pLeft).
• Con trỏ trỏ đến cây con bên phải (pRight).

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
};

Khi khai báo cấu trúc node, ta tạo một biến data, biến này lưu trữ dữ liệu cho node. Sau đó là khai báo hai con trỏ pLeft và pRight của node.

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

Sau khi đã có cấu trúc cây nhị phân tìm kiếm và cấu trúc của node, bây giờ chúng ta đã có thể thêm node vào cây nhị phân được rồi.

Đối với hàm thêm node vào cây nhị phân tìm kiếm, ta cần truyền vào hai tham số đó là:

• Cây nhị phân tìm kiếm t.
• Node x là node cần thêm 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, ta có hai trường hợp xảy ra, vì vậy cần tạo điều kiện cho hai trường hợp này.

Trường hợp 1: Cây nhị phân tìm kiếm rỗng, nghĩa là node mới thêm vào chính là node Root.

// 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
}

Đầu tiên ta khởi tạo node *p là node cần thêm vào cây nhị phân tìm kiếm. Sau đó truyền dữ liệu x vào data của node, khi đó data của *p chính là x.

Vì cây rỗng nên p chính là node đầu tiên và cũng là node gốc. Vậy nên con trỏ pLeft và pRight của nó sẽ được trỏ về NULL và p chính là node gốc t = p.

Trường hợp 2: Cây nhị phân đã tồn tại phần tử.

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
	}
}

Vì cây đã tồn tại phần tử, nghĩa là đã có node gốc rồi. Vậy nên chúng ta cần so sánh với node gốc để xác định vị trí cần thêm node vào cây nhị phân tìm kiếm.

Nếu x nhỏ hơn data của node t thì ta gọi đệ quy hàm ThemNodeVaoCay() để duyệt qua bên trái để thêm phần tử x.

Nếu x lớn hơn data của node t thì ta gọi đệ quy hàm ThemNodeVaoCay() để duyệt qua bên phải để thêm phần tử x.

Full code hàm thêm node vào cây nhị phân tìm kiếm:

/* 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
		}
	}
}

Lời kết

Như vậy là chúng ta đã cùng nhau tìm hiểu về cách thêm node vào cây nhị phân tìm kiếm, cũng như cấu trúc dữ liệu của nó. Qua bài này, mình càn các bạn lưu ý một số kiến thức sau đây:

• Cây nhị phân tìm kiếm là một cấu trúc dữ liệu lưu trữ dưới dạng cây.
• Để thêm node vào cây nhị phân trước tiên ta cần khai báo vào khởi tạo cấu trúc cây và cấu trúc node.
• Khi thêm node vào cây nhị phân ta cần xét hai trường hợp đó là:
  • Cây rỗng.
  • Cây đã tồn tại phần tử.

Ở bài viết tiếp theo mình sẽ hướng dẫn các bạn cách duyệt cây nhị phân tìm kiếm, các bạn chú ý theo dõi nhé !!!