Xóa node khỏi 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;
            }
            delete X; // xóa node cần xóa
        }
    }
}

// hàm tìm node thế mạng
void NodeTheMang(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)
    {
        NodeTheMang(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)
                NodeTheMang(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
        }
    }
}

#include<iostream>
using namespace std;
// khai báo cấu trúc 1 cái node trong cây nhị phân tìm kiếm
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;
  
// hàm khởi tạo cây nhị phân tìm kiếm
void KhoiTaoCay(TREE &t)
{
    t = NULL;
}
  
// hàm thêm 1 cái phần tử vào cây
void ThemNodeVaoCay(TREE &t, int x)
{
    // nếu cây rỗng
    if (t == NULL)
    {
        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);
        }
    }
}
  
// hàm xuất phần tử trong cây nhị phân tìm kiếm
void NLR(TREE t)
{
    if (t != NULL)
    {
        // xử lí
        cout << t->data << "  ";
        NLR(t->pLeft);
        NLR(t->pRight);
    }
}
  
 
// hàm tìm node thế mạng
void NodeTheMang(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)
    {
        NodeTheMang(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)
                NodeTheMang(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
        }
    }
}
  
// hàm nhập cây nhị phân tìm kiếm
void Menu(TREE &t)
{
    int luachon;
    while(true)
    {
        cout << "\n\n\t\t ============ MENU ============";
        cout << "\n1. Nhập phần tử cho cây";
        cout << "\n2. Duyệt cây";
        cout << "\n3. Xóa một Node bất kì";
        cout << "\n0. Thoát";
        cout << "\n\n\t\t =============  END  =============";
  
        cout << "\nNhập lựa chọn của bạn: ";
        cin >> luachon;
  
        if (luachon == 1)
        {
            int x;
            cout << "\nNhập giá trị: ";
            cin >> x;
            ThemNodeVaoCay(t, x);
        }
        else if (luachon == 2)
        {
            cout << "\nCây nhị phân tìm kiếm\n";
            NLR(t);
        }
        else if (luachon == 3)
            {
                  int x;
                cout << "\nNhập giá trị cần xóa: ";
                cin >> x;
                XoaNode(t, x);
            }
        else
        {
            break;
        }
    }
}
  
  
int main()
{
    TREE t;
    KhoiTaoCay(t);
    Menu(t);
  
    cout<<"\n---------------------------------\n";
  cout<<"Chương trình này được đăng tại codehow.net";
}