Phần 1 - Cây Nhị Phân Tìm Kiếm

Cây nhị phân là một tập hợp hữu hạn các node, trong đó có một node đặc biệt gọi là gốc (Root). Giữa các node có một quan hệ phân cấp gọi là quan hệ cha con. Trong bài viết này tôi sẽ đề cập đến các thao tác trên cây nhị phân tìm kiếm.

Bài viết hướng dẫn các thao tác trên cây nhị phân, kết hợp với kiến thức về Pointer và Recursive trong C/C++ nhằm trả lời các câu hỏi sau:

• Cây nhị phân là gì?
• Tại sao phải dùng cây nhị phân để lưu trữ?
• Các thao tác cơ bản trên cây nhị phân?

Cây nhị phân

Là một dạng cấu trúc dữ liệu như: danh sách liên kết, danh sách liên kết đôi, mảng, ... nhằm tạo thuận lợi cho việc tìm kiếm dữ liệu. Mọi node trên cây nhị phân đều có quan hệ "cha - con".

Cấu tạo gồm 3 phần:

• Node gốc (root): là node bắt đầu hay còn gọi là "rễ".
• Node trong (internal): là node có ít nhất 1 con.
• Node lá (leaf): là node không có con.

Tại sao sử dụng cây nhị phân?

Cây nhị phân được sử dụng vào nhiều mục đích khác nhau. Tuy nhiên việc sử dụng cây nhị phân để lưu giữ và tìm kiếm thông tin vẫn là một trong những áp dụng quan trọng nhất của cây nhị phân. Trong bài viết này đề cập lớp cây nhị phân phục vụ cho việc tìm kiếm thông tin, đó là cây nhị phân tìm kiếm.

Các ứng dụng: Từ điển, tra cứu thông tin, ...

Đặc điểm của cây nhị phân tìm kiếm

Cây nhị phân tìm kiếm là cây nhị phân rỗng hoặc thoả mãn đồng thời các điều kiện sau:

• Khoá của các đỉnh thuộc cây con trái nhỏ hơn khoá node gốc.
• Khoá của node gốc nhỏ hơn khoá của các đỉnh thuộc cây con phải của của gốc.

Việc xây dựng với 2 quy tắc trên, nhằm mục đích phục vụ việc lưu trữ và duyệt nhanh, chỉ áp dụng trên cây nhị phân tìm kiếm.

Thao tác trên cây nhị phân

Khởi tạo cây (init)

• Khởi tạo node: cấp phát bộ nhớ cho 1 node,  truyền data cần lưu trữ, gán pLeft = pRight = NULL.
• Khởi tạo cây: khởi tạo cây và gán root = NULL.

struct NODE
{
    int data;
    NODE* pLeft;
    NODE* pRight;
};

NODE* CreateNode(int x)
{
    NODE* p = new NODE();
    p->data = x;
    p->pLeft = p->pRight = NULL;
    return p;
}

Chèn (insertion)

Chèn node chứa dữ liệu vào cây có gốc là root và trả về địa chỉ node mới chèn, việc chèn dữ liệu phải dựa trên đặc điểm của cây nhị phân tìm kiếm.

Ví dụ:

Input: { 40, 5, 35, 45, 15, 56, 48, 13, 16, 49, 47 };

1. Tìm vị trí node cần chèn

NODE* FindInsert(NODE* root, int x)
{
    if (root == NULL)
    {
        return NULL;
    }
    NODE* p = root;
    NODE* f = p;
    while (p != NULL)
    {
        f = p;
        if (p->data > x)
        {
            p = p->pLeft;
        }
        else
        {
            p = p->pRight;
        }
    }        
    return f;
}

2. Chèn node

void InsertNode(NODE* &root, int x)
{
    NODE* n = CreateNode(x);
    if (root == NULL)
    {
        root = n;
        return;
    }
    else
    {
        NODE* f = FindInsert(root, x);
        if (f != NULL)
        {
            if (f->data > x)
            {
                f->pLeft = n;
            }
            else
            {
                f->pRight = n;
            }
        }
    }
}

Tạo cây nhị phân tìm kiếm 

void CreateTree(NODE* &root, int a[], int n)
{
    for (int i = 0; i < n; i++)
    {
        InsertNode(root, a[i]);
    }
}

Tìm kiếm (searching)

Tìm node "x" trên cây root, trả về địa chỉ nếu tìm thấy node x.

1. Sử dụng đệ quy

NODE* SearchNode_Re(NODE* root, int x)
{
    if (root == NULL)
        return NULL;

	if (root->data == x)
	{
		return root;
	}
	if (root->data > x)
	{
		SearchNode_Re(root->pLeft, x);
	}
	else
	{
		SearchNode_Re(root->pRight, x);
	}
}

2. Sử dụng vòng lặp

NODE* SearchNode(NODE* root, int x)
{
    if (root == NULL)
        return NULL;

	NODE* p = root;
	while (p != NULL)
	{
		if (p->data == x)
		{
			return p;
		}
		else if (p->data > x)
		{
			p = p->pLeft;
		}
		else
		{
			p = p->pRight;
		}
	}
}

Duyệt cây nhị phân

Có 6 cách duyệt trên cây nhị phân: NLR, LNR, LRN, NRL, RNL, RLN.

1. Duyệt theo Node - Left - Right (NLR)

Duyệt node gốc, duyệt node trái, duyệt node phải.

void NLR(NODE* root)
{
	if (root != NULL)
	{
		printf("%d \t", root->data);
		NLR(root->pLeft);
		NLR(root->pRight);
	}
}

2. Duyệt theo Left - Node - Right (LNR)

Xuất ra giá trị tăng dần, duyệt Right - Node - Left (RNL) sẽ cho giá trị giảm dần.

void LNR(NODE* root)
{
	if (root != NULL)
	{
		LNR(root->pLeft);
		printf("%d \t", root->data);
		LNR(root->pRight);
	}
}

3. Duyệt theo Left - Right - Node (LRN)

void LRN(NODE* root)
{
	if (root != NULL)
	{
		LRN(root->pLeft);
		LRN(root->pRight);
		printf("%d \t", root->data);
	}
}

Cài đặt hàm main()

int main()
{
	NODE* root = NULL;
	int a[] = { 40, 5, 35, 45, 15, 56, 48, 13, 16, 49, 47 };
	int n = 11;
	CreateTree(root, a, n);
	//NLR(root);
	//LNR(root);
	LRN(root);
	
	return 0;
}