hàm xóa node trong cây nhị phân tìm kiếm
void thaythe(tree &t,node *p)
{
if(t->left) thaythe(t->left,p);
//nếu nhánh bên trái còn tức là khác NULL thì tiếp tực nhảy đến nhánh bến trái
//cho đến khi nào nó là cực trái thì thôi
else//nó đã là node cực trái
{
p->key=t->key;
//p là con trỏ truyền vào, mọi thay đỏi về bộ nhớ, ô nhớ hay giá trị đều thay đỏi trên
//hàm xoa(tree &t,int x) đã gọi nó.
//lúc này p là node cần xóa ở hàm xóa, ta không xóa node mà thay thế giá trị cho nó
//rồi chuyển nó đến 1 ô nhớ khác,
//ô nhớ mà t đang tìm để thay thế để hàm xoa() gọi delete nó.
p=t;//node t là node ta đã tìm ra để thay thế
//nên p=t; tức là sẽ xóa T thay cho p ban đầu
//nên p(node sẽ xóa ở hàm ngoài) nhảy đến ô nhớ của node thay thế là node T , p=t;
t=t->right;
//vì t sẽ bị xóa thông qua p nên t phải nhay đến nhánh bên phải
//để làm liến mạch liên kết với cha như đã lý giải ở hàm xóa
//vì sao lại trỏ right là không phải trỏ left?
//vì T là node thay thế, là node cực trái,
//tức nhánh trái = NULL còn nhánh phải có thể khác NULL
//hoắc bằng NULL, t không cần xác định, chỉ cần
//trỏ t->right để làm liền mạch liên kết đến node cha đã gọi đến nó
//là ok.
}
}
void xoa(tree &t,int x)//hàm xóa node trong cây nhị phân tìm kiếm
{
if(t)//nếu cây t!=NULL
{
if(x<t->key) xoa(t->left,x);//nếu x < key xóa bên trái
else if(x>t->key) xoa(t->right,x);//xóa bên phải
else//đã tìm thấy node cần xóa
{
node *p=t;//gán node cần xóa cho p
if(t->left==NULL) t=t->right;
//nếu node cần xóa có 1 cây con bên phải
else if(t->right==NULL) t=t->left;
//hoặc 1 cây con bên trái
//thì T được truyền vào trong đối số hàm nhảy sang trái hoăc sang phải như trên
//vì sao nó liên kết được với node cha??
//vì node cha đang trỏ đến con trỏ t (tree &t)
//ở dạng tham chiếu luôn nên mọi thay đổi trên t
//thì đều thay đổi trên cấu trúc của node cha, node gọi đến hàm này
//vì thế node cha của node cần xóa hiện tại
//sẽ trỏ đến t, và khi t=t->right; thì
//node cha của node cần t cần xóa vẫn đang trỏ
//đến t với giá trị là ô địa chỉ mới t->right;
else thaythe(t->right,p);
//nếu ndoe t cần xóa có 2 nhánh con thì tìm node cực trái của nhánh phải
//hoặc ngược lại cũng có thể được
delete p;
}
}
//lưu ý cần nhớ.
//khi đối số của hàm là còn trỏ hoặc tham chiếu
//thì mọi thay đổi trên nó đều thay đổi đến biến của hàm đã gọi nó,
//thay đổi đến cụ diện chung của biến, của hàm đã gọi nó.
}
.png)
.png)
.png)
.png)
.png)
.png)
.png)
