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 Freetuts.net";
}