STDIO
Tìm kiếm gần đây
    Nội dung
    0
    0
    Chia sẻ
    Nội dung
    0
    0
    Chia sẻ

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

    Các thao tác trên cây nhị phân tìm kiếm - khởi tạo, chèn, tìm kiếm, duyệt cây với C/C++.
    01/02/2016 17/08/2020 5 phút đọc
    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

    Binary tree.

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

    ss_9

    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.

    ss_7
    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.

    ss_10
    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)

    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;
    }
    
    0 Bình luận
    Giải Thuật Lập Trình

    Giải Thuật Lập Trình

    STDIO Training - Chia sẻ các giải thuật lập trình từ cổ điển đến hiện đại.

    Khi bạn nhấn vào sản phẩm do chúng tôi đề xuất và mua hàng, chúng tôi sẽ nhận được hoa hồng. Điều này hỗ trợ chúng tôi có thêm kinh phí tạo nhiều nội dung hữu ích. Tìm hiểu thêm.
    STDIO

    Trang chính

    Công ty TNHH STDIO

    • 30, Trịnh Đình Thảo, Hòa Thạnh, Tân Phú, Hồ Chí Minh
      +84 28.36205514 - +84 942.111912
      developer@stdio.vn
    • 383/1 Quang Trung, Phường 10, Quận Gò Vấp, Hồ Chí Minh
      Số giấy phép ĐKKD: 0311563559 do sở Kế hoạch và Đầu Tư TPHCM cấp ngày 23/02/2012
    ©STDIO, 2013 - 2021