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 ý ạ.

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 và Node lá trong cây nhị phân tìm kiếm. Đây là một bài toán thường gặp khi thực hiện thao tác với cây nhị phân tìm kiếm.

xuat node con 1 PNG

Chúng ta sẽ cùng nhau tìm hiểu về Node con và Node lá là gì? Sau đó thực hiện xuất số Node con và Node lá trong cây nhị phân tìm kiếm thông qua ví dụ.

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. Xuất các Node có hai con trong cây nhị phân tìm kiếm

Node có hai con là Node vừa có cây con trái vừa có cây con phải. Vì vậy ta dựa vào đây để viết hàm xuất ra Node có hai con.

xuat node con 2 PNG

Cụ thể trong hình trên Node số 1 là Node có hai con, vì cây con bên trái và cây con bên phải nó đều tồn tại.

Đầu tiên ta xét điều kiện cây nhị phân tìm kiếm không rỗng (có tồn tại phần tử), khi đó ta tiếp tục xét điều kiện nếu cây con trái khác NULL (t -> pLeft != NULL) và cây con phải khác NULL (t -> pRight != NULL).

Sau khi xét điều kiện của Node có hai con ta thực hiện gọi đệ quy để tiếp tục duyệt qua cây con trái và cây con phải

// xuất các node có 2 con
void Node_Co_2_Con(TREE t)
{
	if (t != NULL)
	{
		// xử lí
		if (t->pLeft != NULL && t->pRight != NULL) // con trái và con phải có tồn tại phần tử
		{
			cout << t->data << "  ";
		}
		Node_Co_2_Con(t->pLeft); // duyệt sang cây con trái của node hiện tại
		Node_Co_2_Con(t->pRight); // duyệt sang cây con phải của node hiện tại
	}
}

2. Xuất các Node có một con trong cây nhị phân tìm kiếm

Node có một con trong cây nhị phân tìm kiếm là Node chỉ tồn tại cây con trái hoặc chỉ tồn tại cây con phải. Một bên sẽ tồn tại giá trị và bên còn lại bằng NULL.

xuat node con 3 PNG

Cụ thể trong hình ta thấy Node số 7 chỉ tồn tại cây con trái là số 6, còn cây con phải bằng NULL. Một Node như vậy được xem là Node có một con.

Thuật toán cho trường hợp này khá đơn giản, ta chỉ cần thay đổi điều kiện một chút từ trường hợp xuất Node có hai con là xong.

Ta xét hai điều kiện: t->pLeft != NULL && t->pRight == NULLt->pLeft == NULL && t->pRight != NULL. Ta vẫn sẽ gọi đệ quy để tiếp tục duyệt sang cây con trái và cây con phải.

// xuất các node có 1 con
void Node_Co_1_Con(TREE t)
{
	if (t != NULL)
	{
		// xử lí
		if ((t->pLeft != NULL && t->pRight == NULL) || (t->pLeft == NULL && t->pRight != NULL))
		{
			cout << t->data << "  ";
		}
		Node_Co_1_Con(t->pLeft); // duyệt sang cây con trái của node hiện tại
		Node_Co_1_Con(t->pRight); // duyệt sang cây con phải của node hiện tại
	}
}

3. Xuất các Node lá trong cây nhị phân tìm kiếm

Node lá trong cây nhị phân tìm kiếm là Node không tồn tại cây con trái và cây con phải. Cả cây con trái và cây con phải của nó đều bằng giá trị NULL.

xuat node con 4 PNG

Thuật toán cho trường hợp này ngược lại với trường hợp Node có hai con, ta chỉ cần cho t -> pLeft == NULLt -> pRight == NULL. Rồi gọi đệ quy để duyệt qua cây con trái và cây con phải là xong.

// xuất các node lá
void Node_La(TREE t)
{
	if (t != NULL)
	{
		// xử lí
		if (t->pLeft == NULL && t->pRight == NULL)
		{
			cout << t->data << "  ";
		}
		Node_La(t->pLeft); // duyệt sang cây con trái của node hiện tại
		Node_La(t->pRight); // duyệt sang cây con phải của node hiện tại
	}
}

4. Ví dụ: Xuất các Node hai con, Node một con, Node lá trong cây nhị phân tìm kiếm

Trong ví dụ này mình sẽ thực hiện một Menu gồm các thao tác xuất Node hai con, Node một con và Node lá. Các bạn hãy tham khảo code dưới đây nhé.

#include<iostream>
using namespace std;
// 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);
	}
}

// xuất các node có 2 con
void Node_Co_2_Con(TREE t)
{
	if (t != NULL)
	{
		// xử lí
		if (t->pLeft != NULL && t->pRight != NULL) // con trái và con phải có tồn tại phần tử
		{
			cout << t->data << "  ";
		}
		Node_Co_2_Con(t->pLeft); // duyệt sang cây con trái của node hiện tại
		Node_Co_2_Con(t->pRight); // duyệt sang cây con phải của node hiện tại
	}
}
// xuất các node có 1 con
void Node_Co_1_Con(TREE t)
{
	if (t != NULL)
	{
		// xử lí
		if ((t->pLeft != NULL && t->pRight == NULL) || (t->pLeft == NULL && t->pRight != NULL))
		{
			cout << t->data << "  ";
		}
		Node_Co_1_Con(t->pLeft); // duyệt sang cây con trái của node hiện tại
		Node_Co_1_Con(t->pRight); // duyệt sang cây con phải của node hiện tại
	}
}

// xuất các node lá
void Node_La(TREE t)
{
	if (t != NULL)
	{
		// xử lí
		if (t->pLeft == NULL && t->pRight == NULL)
		{
			cout << t->data << "  ";
		}
		Node_La(t->pLeft); // duyệt sang cây con trái của node hiện tại
		Node_La(t->pRight); // duyệt sang cây con phải của node hiện tại
	}
}

// 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ử cho cây";
		cout << "\n2. Duyệt cây";
		cout << "\n3. Node có hai con";
		cout << "\n4. Node có một con";
		cout << "\n5. Node lá";
		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 == 1)
		{
			int x;
			cout << "\nNhập giá trị: ";
			cin >> x;
			ThemNodeVaoCay(t, x);
		}
		else if (luachon == 2)
		{
			cout << "\nCây nhị phân tìm kiếm\n";
			NLR(t);
		}
		
		else if (luachon == 3)
		{
			cout << "\nNode có hai con: ";
			Node_Co_2_Con(t);
		}
		else if (luachon == 4)
		{
			cout << "\nNode có một con: ";
			Node_Co_1_Con(t);
		}
		else if (luachon == 5)
		{
			cout << "\nNode lá: ";
			Node_La(t);
		}
		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ả: Mình sẽ sử dụng dữ liệu như hình ở đầu bài viết, bao gồm các số: 5, 1, -2, 0, 8, 7, 9, 3, 6.

xuat node con 6 PNG

5. Kết luận

Như vậy là chúng ta đã tìm hiểu xong Node hai con, Node một con, Node lá là gì? và cách xuất các Node lá trong cây nhị phân tìm kiếm. Các bạn hãy luyện tập thật nhiều để có thể nhớ được lâu nhé. Ở bài tiếp theo mình sẽ thực hiện tìm giá trị MIN và giá trị MAX trong cây nhị phân tìm kiếm, các bạn hãy 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…

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:

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