Cây Nhị Phân

Cây nhị phân - Binary Tree

Cây nhị phân là tập hợp các nút (node) chứa giá trị liên kết với nhau theo quan hệ cha - con (lần lượt theo chiều mũi tên như hình vẽ) sao cho mỗi nút không quá 2 nút con.

Nút gốc

Nút gốc là nút không là con của bất kỳ của nút nào, là nút bắt đầu của cây nhị phân, từ đó cây nhị phân mở rộng ra.

Nút trong

Nút trong là nút có con, bất kể 1 hoặc 2 nút con.

Nút lá

Nút lá là nút không có nút con nào.

Cây con

Mỗi nút trong cây cùng với những nút phía dưới nó tạo thành một cây con.

Code cây nhị phân

Định nghĩa cấu trúc nút

Giả sử giá trị của nút là kiểu int, cần 2 biến con trỏ trỏ đến địa chỉ của hai nút con của mỗi nút.

// ...
struct Node
{
	int info;
	Node *pLeft;
	Node *pRight;
}

Định nghĩa cây nhị phân

• Quản lý cây nhị phân từ một nút gốc ban đầu (nút không là con của nút nào khác) rồi dần duyệt xuống.
• Các nút sẽ được thể hiện dưới dạng con trỏ được cấp phát động để có thể trình bày các dòng code dễ dàng hơn cũng như thuận tiện tạo nút mới.

Khởi tạo cây nhị phân rỗng

Khi cây chưa có nút nào, hay còn gọi là cây rỗng, nút gốc ban đầu cần được trỏ đến một địa chỉ xác định nào đó có thể có thể kiểm soát được. Như vậy mới có thể xác định được cây nhị phân hiện tại có rỗng hay chưa?

// ...
void init(Node * & tree)
{
	tree = nullptr;
}

Khởi tạo một nút với giá trị cho trước

Cấp phát động một nút và gán địa chỉ 2 nút con của nút đó có giá trị nullptr mặc định nút đó là nút lá.

Node* getNode(int value)
{
	Node *p = new Node;

	// truong hop cap phat cho p that bai, tra ve gia tri nullptr
	if (p == nullptr)
		return nullptr;

	// gan gia tri chua trong nut
	p->info = value;

	// gan dia chi hai nut con cua nut p tam thoi la nullptr
	p->pLeft = nullptr;
	p->pRight = nullptr;

	return p;
}

Thêm nút vào cây nhị phân

Tuỳ vào mục đích xây dựng và sắp xếp các nút trên cây nhị phân sẽ có những cách thêm nút phù hợp tương ứng, xác định rõ tính chất của kiểu cây nhị phân và yêu cầu của bài toán để có cách phù hợp.

Duyệt cây nhị phân theo thứ tự

Tuỳ vào mục đích sử dụng có các phương pháp duyệt cây với thứ tự khác nhau:

• Phương pháp LNR (Left Node Right).
• Phương pháp LRN (Left Right Node).
• Phương pháp NLR (Node Left Right).
• Phương pháp NRL (Node Right Left).
• Phương pháp RNL (Right Node Left).
• Phương pháp RLN (Right Left Node).

Tuỳ vào các mục đích duyệt cây để thực hiện công việc gì sẽ có hàm duyệt cây tương ứng. Dưới đây là hàm duyệt cây để lần lượt in ra các giá trị của mỗi nút theo đệ quy bằng C++.

Duyệt theo NLR (Node Left Right)

// ...
void show(Node *tree)
{
    // kiem tra cay nhi phan co rong khong
    // hoac khi de quy den nut la ket thuc de quy
    if (tree == nullptr)
        return;

    cout << tree->info;
    show(tree->pLeft);
    show(tree->pRight);
}

Duyệt theo LNR (Left Node Right)

// ...
void show(Node *tree)
{
    // kiem tra cay nhi phan co rong khong
    // hoac khi de quy den nut la ket thuc de quy
    if (tree == nullptr)
        return;

    show(tree->pLeft);
    cout << tree->info;
    show(tree->pRight);
}

Tương tự thay đổi thứ tự cho những cách duyệt còn lại.

Ngoài ra còn có thể nâng cấp nhiều tính năng hơn cho cây nhị phân để có thể sử dụng giải quyết các nhu cầu thực tế như từ điển.