Lượt xem 0 Nhận xét

Cây nhị phân tìm kiếm trong C và CSharp

Cập nhật: 25 thg 10, 2018 4:36 CH
Cây nhị phân (binary tree) là một dạng của cấu trúc dữ liệu "cây". Đây là một trong những cấu trúc dữ liệu mà chúng ta cần nắm vững khi học về thuật toán.

Để biểu diễn cây nhị phân người ta thường dùng Danh sách liên kết đôi. Vì thế sau loạt bài về Danh sách liên kết đơnDanh sách liên kết đôi, sẽ là lúc phù hợp để mình viết bài về cây nhị phân tìm kiếm.

Trong bài viết mình sẽ minh họa code trong C++ và CSharp.


Như đã nói ở trên, người ta thường ứng dụng Danh sách liên kết đôi để biểu diễn cây nhị phân, vì thế nếu các bạn chưa biết cách khởi tạo và sử dụng danh sách liên kết đôi thì có thể đọc bài viết này: Danh sách liên kết đôi.

1. Cấu trúc của một cây nhị phân.


Cây nhị phân được tạo ra để giúp cho các bài toán tìm kiếm trở nên dễ dàng hơn.

Đặc điểm của một cây nhị phân:

- Gồm các nút. Mỗi nút thì có thể có tối đa 2 nút con. (Tức là một nút có thể có 1 hoặc 2 nút con, hoặc không có nút con nào.)

- Mỗi nút nút trong cây sẽ chứa 3 thông tin: + Dữ liệu mà của nút đó. (Ở bài này để các bạn dễ hình dung và hiểu thì mình sẽ minh họa cây nhị phân chưa dữ liệu là các nguyên.)
                                                                       + Liên kết con trỏ tới nút con trái và nút con phải. Nếu nút đang xét khuyết mất nút con nào thì liên kết tới nút con đó sẽ được gán với một giá trị đặc biệt.

- Dữ liệu của các nút con bên trái của một nút bất kì trong cây luôn bé hơn nút này.

- Dữ liệu của các nút con bên phải của một nút bất kì trong cây luôn lớn hơn nút này.

Hai đặc điểm đầu tiên là lý do cây nhị phân thường được biểu diễn bằng danh sách liên kết đôi. Hai đặc điểm cuối là lý do nó giúp cho việc tìm kiếm trở nên dễ dàng hơn.

Để dễ hiểu hơn, các bạn bạn hãy xem hình dưới đây.

Hình minh hoa cây nhị phân tìm kiếm.

Các bạn có thể thấy mỗi nút trong cây có nhiều nhất là 2 nút con. Và:

+ với nút có dữ liệu là 9, các bạn có thể thấy tất cả các nút con nằm phía bên trái của nút này (bao gồm các nút 3, 1, 5, 4, 7) đều có dữ liệu nhỏ hơn dữ liệu của nút này là 9. Và các nút con nằm bên phải của nút này (bao gồm các nút 10, 14, 11) đều có dữ liệu lớn hơn dữ liệu của nút này là 9.

+ với nút có dữ liệu là 3, các nút con bên trái nút này (nút 1) có dữ liệu nhỏ hơn 3. Còn các nút con bên phải (bao gồm nút 5, 4, 7) đều có dữ liệu lớn hơn 3.

2. Tạo kiểu dữ liệu cây nhị phân.


Chúng ta sẽ dựa vào Danh sách liên kết đôi để biểu diễn cây nhị phân, vì thế việc tạo kiểu dữ liệu cây nhị phân cũng tương tự như Danh sách liên kết đôi thôi.

Csharp:
class Tree
{
    public Tree leftChild;  
    public Tree rightChild;
    public int info;   // dữ liệu mà nút chứa
}

C++:
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;

3. Thêm phần tử vào cây nhị phân.


Giả sử: chúng ta đang có một dãy các số nguyên như sau: 9, 3, 1, 5, 4, 7, 10, 14, 11.

Chúng ta sẽ thêm lần lượt các số này vào một cây nhị phân. (thêm lần lượt từ trái qua phải.)

Quá trình thêm sẽ diễn ra như sau. Các bạn hãy xem hình để dễ hình dùng.


+ Thêm 9 cây nhị phân. 9 là nút đầu tiên của cây.

+ Thêm 3 vào cây nhị phân: Vì 3 < 9 nên 3 sẽ là nút con bên trái của nút 9 và bên trái của 9 chưa có nút nào (9.leftChild = null *) nên ta thêm 3 vào phía bên trái của 9.

+ Thêm 1 vào cây nhị phân: Vì 1 < 9 nên 1 sẽ là phải nằm phía bên trái của 9. Ta duyệt cây về bên trái của 9, sẽ đi tới được nút 3. Tiếp tục so sánh, vì 1 < 3 nên 1 sẽ tiếp tục nằm về phía bên trái của nút 3 này. Nút 3 này hiện tại chưa có nút con nào (3.leftChild = null *), nên ta có thể thêm ngay 1 là nút con trái của nút 3.

+ Thêm 5 vào cây nhị phân: Vì 5 < 9, nên 5 nằm phía bên trái của 9. Ta duyệt cây về bên trái của 9, sẽ tới được nút 3. Tiếp tục so sánh, vì 5 > 3 nên 5 sẽ nằm về phía bên phải của 3. Nút 3 hiện tại chưa có nút con phải (3.rightChild = null *) nào nên ta có thể thêm ngay vào làm nút con phải của 3.

+ Tương tự: Thêm 4 vào cây nhị phân : Vì 4 < 9 → so sánh 4 > 3 → so sánh 4 < 5 mà 5 chưa có nút con trái (5.leftChild = null *) nên thêm 4 làm nút con trái của 3.

......

 * mình ghi bằng theo kiểu này chỉ để các bạn dễ hình dung thôi, thực chất là ta sẽ thao tác trên node (vùng nhớ của chúng) chứ không phải là trên dữ liệu các node như này.

Chúng ta sẽ cứ so sánh và duyệt liên tục theo quy tắc:
+ nếu dữ liệu cần thêm nhỏ hơn dữ liệu nút đang xét thì duyệt sang trái.
+ nếu dữ liệu cần thêm lớn hơn dữ liệu nút đang xét thì duyệt sang phải.
+ cứ duyệt theo hai quy tắc trên cho đến khi tới một nút rỗng (null) thì tiến hành thêm dữ liệu cần thêm vào vị trí này.

Với quy tắc duyệt và thêm dữ liệu như trên thì các đặc điểm của cây nhị phân mà mình bên trên luôn được đảm bảo.

Code hàm thêm nút vào cây nhị phân.

CSharp:
static void themPhanTu(ref Tree tree, int data)
{
    if (tree == null)  // nếu duyệt tới một nút đang là null thì thêm vào
    {
        Tree element = new Tree();
        element.info = data;
        element.leftChild = element.rightChild = null;

        tree = element;
    }

    else  // cứ duyệt theo quy tắc khi nút đang xét chưa rỗng.
    {
        if (data < tree.info)  // nếu dữ liệu thêm vào nhỏ hơn dữ liệu nút đang xét
        {
            themPhanTu(ref tree.leftChild, data);  // đi tiếp sang trái
        }

        else if (data > tree.info)  // nếu dữ liệu thêm vào lớn hơn dữ liệu nút đang xét
        {
            themPhanTu(ref tree.rightChild, data); // đi tiếp sang phải
        }

        else  // dữ liệu thêm vào không thể trùng nhau
        {
            Console.Write("Phần tử cần thêm đã có trong cây.");
        }
    }
}

C++:
void ThemNodeVaoCay(TREE &t, int x) // x là dữ liệu cần thêm vào
{
    if (t == NULL)  // nếu cây rỗng
    {
        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);
        }
    }
}

Lưu ý: Các bạn có thể thấy dãy số: (9, 3, 1, 5, 4, 7, 10, 14, 11) được mình thêm vào theo đúng thứ tự từ trái qua phải. Và do đó mình được một cây nhị phân như hình demo bên trên. Nếu với cùng bộ dãy số này nhưng nếu các bạn thêm vào theo thứ tự khác thì có thể sẽ ra một cây nhị phân khác.

Ví dụ: Các bạn có thể tự vẽ một cây nhị phân ra giấy với dữ liệu là dãy số như sau: (9, 5, 3, 1, 4, 7, 10, 14, 11). Với quá trình thêm nút tương tự như mình làm bên trên. Và các bạn nhớ thêm theo đúng thứ tự từ trái qua phải. Sau đó so sánh với hình demo của mình, các bạn sẽ thấy dù cùng một bộ dữ liệu nhưng nếu thêm theo thứ tự khác nhau thì có thể sẽ ra một cây nhị phân mới.

4. Hàm tìm kiếm phần tử trong cây.


Thường thì người ta sẽ thường nói về hàm xóa phần tử khỏi cây ngay dưới hàm thêm phần tử, nhưng muốn xóa một phần tử khỏi cây thì chúng ta sẽ cần duyệt cây để xem phần tử này có trong cây không. Sau đó nếu tìm thấy thì mới xóa phần tử này đi. Công việc tìm kiếm phần tử trong cây ở hai hàm này là như nhau.

Như ở trên mình có nói, kiểu cấu trúc dữ liệu cây nhị phân rất phù hợp với các bài toán tìm kiếm, nhờ vào hai đặc điểm là:

- Dữ liệu của các nút con bên trái của một nút bất kì trong cây luôn bé hơn nút này.

- Dữ liệu của các nút con bên phải của một nút bất kì trong cây luôn lớn hơn nút này.

Tại sao? Để đơn giản ta xét ví dụ sau:

 Ta quay trở lại với cây demo ở bên trên:


Giả sử chúng ta cần tìm phần tử 4 trong cây bên trên. Ta sẽ thực hiện như sau:
  • Đầu tiên, ta đang ở nút 9.
  • Vì 4 < 9 mà các nút có dữ liệu nhỏ hơn nút đang xét (nút 9) thì chắc chắn phải nằm về phía bên trái của nút này để đảm bảo đặc điểm của cây nhị phân. Do đó nếu muốn tìm 4 thì ta sẽ chỉ cần sang trái nút 9 để tìm. Hiển nhiên ta không cần đi sang bên phải nút 9 vì bên này toàn mấy nút có dữ liệu lớn hơn 9 thôi. Đi sang trái nút 9 ta tới được nút 3.
  • Vì 4 > 3 nên hiển nhiên là ta đi sang phải nút 3 rồi. vì nếu đi sang trái nút 3 thì chỉ có thể gặp các nút có dữ liệu nhỏ hơn 3 thôi. Nên đi sang trái là chắc chắn không thể gặp được 4 rồi. Đi sang phải nút 3 ta tới được nút 5.
  • Vì 4 < 5 nên ta sẽ đi sang trái nút 5 để tiếp tục quá trình tìm kiếm nút 4. Không cần đi sang phải nút 5 làm gì cho tốn công. Đi sang trái nút 5 ta tới được nút 4.
  • So sánh: 4 = 4 suy ra ngay là có tìm thấy 4 trong cây đang xét. hay nói cách khác trong cây đang xét có một nút có dữ liệu là 4.

Quá trình tìm kiếm nút có dữ liệu là 4 trong cây.

Còn nếu các bạn muốn tìm một nút có dữ liệu là 6, thì cứ đi theo quy luật như trên, đến cuối cùng sẽ tới được nút 7. Mà 6 nhỏ hơn 7, nên sẽ phải đi sang trái nút 7. Mà bên trái nút 7 là null. Hay nói cách khác là đi tới tận cùng thế giới hết cây rồi mà vẫn không thấy nút nào có dữ liệu là 6. Suy ra là cây không có nút có dữ liệu là 6 cả.

Các bạn có thể thấy với việc sắp xếp dữ liệu ở cây nhị phân, khi chúng ta cần tìm kiếm dữ liệu thì chúng ta sẽ không cần so sánh dữ liệu cần tìm với tất cả các nút có trong cây như ở mảng,... Mà chúng ta chỉ cần tìm theo quy luật là có thể biết dữ liệu có trong cây hay không ngay. Các phép so sánh sẽ ít đi rất nhiều, và sẽ càng hiệu quả với dữ liệu lớn.

Cũng như chúng ta vào thư viện tìm quyển "Tán gái đại cương". Nhưng thư viện xếp sách lộn xộn, không xếp theo kiểu: Giá Sách tâm lý và xã hội rồi trong giá sách này lại chia theo bảng chữ cái A B C ... T ... thì các bạn sẽ phải tìm hết tất các các sách có trong thư viện, mà có khi tìm hết rồi rõ tốn thời gian mà không thấy ấy chứ.

Code hàm tìm kiếm trong cây nhị phân:

CSharp:
static void timKiem(Tree tree, int data)
{
    if (tree == null) // cây đang rỗng hoặc là đã đi đến tận cùng của cây mà vẫn không thấy
    {
        Console.Write("\nKhông tìm thấy {0} trong cây.", data);
    }
    else
    {
        if (data < tree.info) // nếu dữ liệu cần tìm nhỏ hơn dữ liệu nút đang xét
        {
            timKiem(tree.leftChild, data);
        }

        else if (data > tree.info) // nếu dữ liệu cần tìm lớn hơn dữ liệu nút đang xét
        {
            timKiem(tree.rightChild, data);
        }

        else // tìm thấy dữ liệu rồi
        {
            Console.Write("\nPhần tử {0} có tồn tại trong cây.", data);
        }
    }
}

C++:
NODE* TimKiem(TREE t, int x)  // x là phần tử cần tìm
{
    // nếu cây rỗng
    if (t == NULL)
    {
        cout << "\nPhan tu " << x << " khong ton tai trong cay";
    }
    else
    {
        // nếu phần tử cần tìm kiếm mà nhỏ hơn node gốc thì duyệt(đệ quy) sang bên trái để tìm
        if (x < t->data)
        {
            TimKiem(t->pLeft, x);
        }
        else if (x > t->data) // duyệt sang bên phải
        {
            TimKiem(t->pRight, x);
        }
        else // <=> t->data == x
        {
            cout << "\nPhan tu " << x << " co ton tai trong cay";
        }
    }
}

5. Xóa nút trong cây:


Như đã nói bên trên, nếu chúng ta muốn xóa một phần tử thì chúng ta cũng cần tìm phần tử này xem nó có trong cây không đã. Nhưng khác với hàm tìm kiếm, nếu tìm thấy ta sẽ thông báo là sẽ tìm thấy thì khi ở hàm này, ta sẽ tiến hành xóa nó đi.


Khi ta xóa một nút trong cây ta sẽ phải xét 3 trường hợp sau:

- Nút cần xóa không có nút con trái. Ta chỉ cần thay nút này bằng nút con bên phải của nó.

Ví dụ: Với nút 10 ở hình bên trên, ta chỉ cần gán nó bằng nút con phải của nó là nút 14 là được.

10 = 10.rightChild; // mình ghi bằng theo kiểu này chỉ để các bạn dễ hình dung thôi, thực chất là ta sẽ thao tác trên node (vùng nhớ của chúng) chứ không phải là trên dữ liệu các node như này


- Nút cần xóa không có nút con phải. Ta làm tương tự. Chỉ cần gán lại nó bằng nút con trái là được.

Ví dụ như nút 14 bên trên, ta gán nó bằng nút con trái là 11.

14 = 14.leftChild; // mình ghi bằng theo kiểu này chỉ để các bạn dễ hình dung thôi, thực chất là ta sẽ thao tác trên node (vùng nhớ của chúng) chứ không phải là trên dữ liệu các node như này

- Trường hợp nút cần xóa không có cả nút con phải và nút con trái thì chúng ta không cần làm. Vì nó sẽ rơi vào một trong 2 trường bên trên rồi. Lúc gán lại nút cần xóa bằng nút con (phải hoặc trái) thì thực chất là gán nó bằng null.

- Trường hợp nút cần xóa có cả con trái và con phải.  

Với trường hợp này, thực chất ta sẽ không xóa nút này đi, mà sẽ tìm một nút con của nó để thế mạng cho nó. Cụ thể là ta sẽ cần tìm một nút con của nút cần xóa, sao cho khi thay dữ liệu của nút cần xóa bằng dữ liệu của nút con thế mạng này thì các đặc điểm của cây nhị phân vẫn được bảo toàn. Nút con thế mạng cần tìm này luôn tồn tại.

Sau khi thay dữ liệu nút cần xóa bằng nút con thế mạng thì ta sẽ xóa nút thế mạng này đi.

Chúng ta có hai cách để tìm nút con thế mạng của một nút:

+ Ta sẽ thay thế nút cần xóa bằng bằng nút con phải nhất bên nhánh trái:

Vì sao? Vì nút con phải nhất bên nhánh trái sẽ là nút con có dữ liệu lớn nhất bên nhánh trái. Nó sẽ lớn hơn mọi nút bên nhánh trái. Nhưng vì nó thuộc nhánh trái nên chắc chắn dữ liệu của nó sẽ bé hơn nhánh phải. Do đó khi thay thế nút cần xóa bằng nút này thì đặc điểm của cây sẽ bảo toàn.

Đọc ví dụ dưới cho dễ hiểu nha.

Ví dụ: Ta cần xóa nút 9 ở hình demo bên trên. Thì ta sẽ tìm con phải nhất bên nhánh trái của nút 9:
  • Đi sang nhánh trái 1 lần duy nhất tới được nút 3.
  • Từ nút 3, ta sẽ chỉ đi sang phải cho tới nút cuối cùng bên nhánh phải của nút 3. Khi đi sang phải ta tới nút 5. Từ nút 5 tiếp tục đi sang phải ta tới đươc nút 7. Nút 7 là nút cuối cùng bên nhanh phải của nút 3.
  • Nút 7 là nút cuối cùng bên nhánh phải của nút 3. Hay nói cách khác nút 7 là nút phải nhất của nút 3. Mà nút 3 là nút con đầu tiên bên nhánh trái của nút 9. Do đo sẽ là nút 7 sẽ là nút con phải nhất bên nhánh trái của nút 9.
  • Khi tìm được 7 rồi thì ta thay dữ liệu nút 9 đang dữ bằng 7. và xóa nút 7 khỏi cây theo quy tắc xóa nút không nút con phải.
Đọc đoạn trên hơi phức tạp, các bạn hãy xem tiếp bên dưới sẽ thấy hiểu ngay.

Cây sẽ trở thành như hình dưới sau khi "xóa" nút 9 khỏi cây:


Thật kì diệu phải không. Sau khi thay 9 bằng 7 và xóa 7 khỏi cây thì ta được một cây mới những vẫn thỏa mãn các đặc điểm của cây nhị phân.

Tại sao?

- 7 là phần tử phải nhất bên nhánh trái của 9. Hay 7 sẽ là phần tử lớn nhất bên nhánh trái của 9.
  • Sau khi từ 9 sang trái 1 lần tới được 3. Tiếp theo, ta cứ đi về bên phải của 3 và tới được 7. Vì khi chỉ đi về bên phải ta sẽ gặp được phần tử lớn nhất bên nhánh phải của 3. Hay nói cách khác là các phần tử bên nhánh phải của 3 chắc chắn sẽ bé 7. Các phần tử bên nhánh trái của 3 sẽ nhỏ hơn 3 và sẽ nhỏ hơn 7. 
  • Do đó mọi phần tử bên nhánh trái của 9 luôn bé hơn 7. Và khi ta thay 9 bằng 7 thì chắc chắn vẫn sẽ thỏa mãn đặc điểm của cây nhị phân: các phần tử bên nhánh trái của một nút luôn bé hơn nút này.
- Các phần tử thuộc nhánh trái luôn nhỏ hơn 9 và 9 luôn nhỏ hơn các phần tử ở nhánh phải. Mà 7 thuộc nhánh trái nên chắc chắn 7 < 9 < toàn bộ phần tử bên nhanh phải của 9. Do đó khi thay 9 bằng 7 thì vẫn sẽ luôn thỏa mãn đặc điểm nhánh con phải luôn lớn hơn nút cha.
Vậy cách thứ nhất để tìm nút thế mạng là tìm nút con phải nhất bên trái. Từ nút cần xóa, ta đi sang nhánh trái 1 lần. Sau đó ta cứ đi về bên phải cho tới khi gặp null.

+ Ta sẽ thay thế nút cần xóa bằng bằng nút con trái nhất bên nhánh phải:

Cách này tương tự như cách trên thôi. Nên các bạn có thể tự phân tích nhé. (Vì nút con trái nhất bên nhánh phải sẽ là bé nhất bên nhánh phải nhưng chắc chắn vẫn lớn hơn nhánh trái.)

Khi chúng ta viết chương trình thì các bạn có thể chọn 1 trong 2 cách trên để làm đều được. Chỉ cần 1 trong 2 thôi nhá.

Code minh họa:

CSharp:
static void xoaPhanTu(ref Tree tree, int data)
{
    if (tree == null)
    {
        Console.Write("Cây không chứa phần tử cần xóa");
    }

    else
    {
        if (data < tree.info) // đi tìm nút cần xóa
        {
            xoaPhanTu(ref tree.leftChild, data);
        }

        else if (data > tree.info) // đi tìm nút cần xóa
        {
            xoaPhanTu(ref tree.rightChild, data);
        }

        else  // tìm thấy nút cần xóa
        {             
            if (tree.leftChild == null)  // nút cần xóa không có nút con trái
            {
                tree = tree.rightChild;
            }

            else if (tree.rightChild == null)  // nút cần xóa không có nút con phải
            {
                tree = tree.leftChild;
            }

            else  // nút cần xóa có cả nút con trái và phải
            {
                // thay nút cần xóa bằng nút trái nhất bên phải
                Tree b = tree.rightChild; // sang phải 1 lần
                Tree a = b;

                while (b.leftChild != null) // đi tiếp tục sang trái
                {
                    a = b;
                    b = b.leftChild;
                }

                // sẽ có hai trường hợp:
                // nút con đầu tiên bên phải nút cần xóa có nút con trái
                if (a != b)
                {
                    tree.info = b.info;
                    a.leftChild = b.rightChild;
                    b = null;
                }

                // nút con đầu tiên bên phải nút cần xóa không có nút con trái
                else
                {
                    tree.info = b.info;
                    tree.rightChild = b.rightChild;
                    b = null;
                }
            }
        }
    }
}

C++
// hàm tìm node thế mạng
void DiTimNodeTheMang(TREE &X, TREE &Y) // NODE Y là node thế mạng cho node cần xóa - node này sẽ đảm nhận nhiệm vụ tìm ra node trái nhất(TÌM NODE TRÁI NHẤT CÂY CON PHẢI) hoặc phải nhất(TÌM NODE PHẢI NHẤT CỦA CÂY CON TRÁI)
{
    // CÁCH 1: TÌM NODE TRÁI NHẤT CỦA CÂY CON PHẢI
    // duyệt sang bên trái nhất
    if (Y->pLeft != NULL)
    {
        DiTimNodeTheMang(X, Y->pLeft);// tìm ra node trái nhất ?
    }
    else // tìm ra được node trái nhất rồi nek..
    {
        X->data = Y->data; // cập nhật cái data của node cần xóa chính là data của node thế mạng
        X = Y; // cho node X(là node mà chúng ta sẽ đi xóa sau này) trỏ đến node thế mạng ==> ra khỏi hàm thì ta sẽ xóa node X
        Y = Y->pRight; // bản chất chỗ này chính là cập nhật lại mối liên kết cho node cha của node thế mạng(mà chúng ta sẽ xóa) với node con của node thế mạng 
    }

    //// CÁCH 2: TÌM NODE PHẢI NHẤT CỦA CÂY CON TRÁI
    //// duyệt sang bên phải
    //if (Y->pRight != NULL)
    //{
    //  DiTimNodeTheMang(X, Y->pRight);// tìm ra node phải nhất ?
    //}
    //else // tìm ra được node phải nhất rồi nek..
    //{
    //  X->data = Y->data; // cập nhật cái data của node cần xóa chính là data của node thế mạng
    //  X = Y; // cho node X(là node mà chúng ta sẽ đi xóa sau này) trỏ đến node thế mạng ==> ra khỏi hàm thì ta sẽ xóa node X
    //  Y = Y->pLeft; // bản chất chỗ này chính là cập nhật lại mối liên kết cho node cha của node thế mạng(mà chúng ta sẽ xóa) với node con của node thế mạng  
    //}
}

// hàm xóa 1 cái node bất kì trong cây nhị phân tìm kiếm
void XoaNode(TREE &t, int data) // data chính là giá trị của cái node cần xóa
{
    // nếu như cây đang rỗng
    if (t == NULL)
    {
        return; // kết thúc hàm
    }
    else
    {
        // nếu như data nhỏ hơn node gốc
        if (data < t->data)
        {
            XoaNode(t->pLeft, data); // duyệt sang nhánh trái của cây 
        }
        else if (data > t->data)
        {
            XoaNode(t->pRight, data); // duyệt sang nhánh phải của cây 
        }
        else // data == t->data - đã tìm ra cái node cần xóa
        {
            NODE *X = t; // node X là node thế mạng - tí nữa chúng ta sẽ xóa nó
            // nếu như nhánh trái bằng NULL <=> đây là cây có 1 con chính là con phải
            if (t->pLeft == NULL)
            {
                // duyệt sang phải của cái node cần xóa để cập nhật mối liên kết giữa node 
                // cha của node cần xóa với node con của node cần xóa
                t = t->pRight; 
            }
            else if (t->pRight == NULL)
            {
                // duyệt sang trái của cái node cần xóa để cập nhật mối liên kết giữa node 
                // cha của node cần xóa với node con của node cần xóa
                t = t->pLeft;
            }
            else // node cần xóa là node có 2 con
            {
                // CÁCH 1: Tìm node trái nhất của cây con phải(cây con phải của cái node cần xóa)
                DiTimNodeTheMang(X, t->pRight);
                // CÁCH 2: Tìm node phải nhất của cây con trái(cây con trái của cái node cần xóa)
                //DiTimNodeTheMang(X, t->pLeft);
            }
            delete X; // xóa node cần xóa
        }
    }
}

6. Duyệt cây


Duyệt cây thì để thuận tiện, chúng ta duyệt theo quy tắc: duyệt sang trái xong mới duyệt sang phải.

Code hàm duyệt cây:

CSharp:
static void xuatCay(Tree tree)
{
    if (tree != null)
    {
        Console.Write(tree.info + "  ");
        xuatCay(tree.leftChild);
        xuatCay(tree.rightChild);
    }
}

C++:
void NLR(TREE t)
{
    if (t != NULL)
    {
        // xử lí
        cout << t->data << "  ";
        NLR(t->pLeft);
        NLR(t->pRight);
    }
}

7. Code chương trình hoàn chỉnh.


CSharp: https://paste.ubuntu.com/p/r3Pdhd4YMY/

C++ : https://paste.ubuntu.com/p/gctFt5HqVJ

Code C++ trong bài viết do hơi lười nên mình không làm lại. Bản code này mình lấy trên mạng ở kênh Youtube Thien Tam Nguyen. Kênh này có khá nhiều bài về lập trình C/C++ hay và dễ hiểu.

Nếu có gì thắc mắc hay góp ý gì các bạn có thể comment dưới bài viết này nhé.

Chúc các bạn học tập tốt.

Tham khảo thêm : So sánh Danh sách liên kết và Mảng.

Tài liệu : Giải thuật và lập trình - Lê Minh Hoàng.

Bản quyền bài viết thuộc về Rebvn.com. Mọi copy vui lòng ghi rõ nguồn.