Cây 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.
Data Structure & Algorithm C/C++ Nguyễn Đăng Khánh 2015-11-04 16:21:27

Giới thiệu

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ạn có thể đọc thêm về Cây Nhị Phân.

Bài viết hướng đến các bạn đang thắc mắc về cây nhị phân, kết hợp với kiến thức về Pointer và Recursive. Trong bài viết sẽ giúp các bạn 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

end

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 mục đích giải quyết 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 node): 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 tôi sẽ nói về 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.

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

ss_9

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

  • 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);
	}
}
  • 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.

  • Duyệt theo Node - Left - Right (NLR): Duyệt node gốc, duyệt node trái, duyệt node phải.

ss_7

void NLR(NODE* root)
{
	if (root != NULL)
	{
		printf("%d \t", root->data);
		NLR(root->pLeft);
		NLR(root->pRight);
	}
}
  • 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.

ss_10

void LNR(NODE* root)
{
	if (root != NULL)
	{
		LNR(root->pLeft);
		printf("%d \t", root->data);
		LNR(root->pRight);
	}
}
  • Duyệt theo Left - Right - Node (LRN)

ss_11

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