//nếu có 1 nhánh con thì dùng con trỏ Child trỏ vào nhánh con đÓ
if(P->P_L != NULL){
Child = P->P_L;
}else{
//nếu nhánh con là nhánh phải (hoặc không có nhánh nào, thì Child là NULL)
Child = P->P_R;
}
if(P == T){ //Nếu nút cần xoá là gốc cây
T = Child;
}else if(Q->P_L == P){
Q->P_L = Child;
}else{ //nếu P là nhánh phải của Q hoặc P là lá (gán lại thành Null)
Q->P_R = Child;
}
free(P);
}
Như ta thấy việc sửa lại cây chỉ cần sửa 1 mối nối, giải thuật có 2 vòng lặp while,vòng while đầu tiên sẽ đi tìm giá trị cần xoá từ trên xuống, vòng while thứ 2 sẽ tìm nút cực trái(phải) từ vị trí giá trị cần xoá xuống, vậy chi phí thời gian cho giải thuật là O(log2(n)) tương tự như giải thuật tìm kiếm rồi bổ sung
16. Trình bày (bằng ngôn ngữ tự nhiên và ngôn ngữ tựa C) giải thuật Kiểm tra cây nhị phân T có phải là "cây nhị phân tìm kiếm" hay không? Mỗi nút trên cây có cấu trúc như sau:
P_L Trỏ tới cây con trái
KEY Chứa giá trị khoá
P_R Trỏ tới cây con phải
BST_CHECK(TREE){
if(TREE == NULL){
printf("Cay rong");
return true; //vì cây rỗng vẫn là 1 BST
}
TOP = -1; //khởi tạo STACK rỗng
P = TREE; //P dùng để duyệt cây, gán thành gốc cây
NutTruoc = NULL; //con trỏ tro đến giá trị của nút được thăm trước đó
while(TOP > -1 || P != NULL){
while(P != NULL){
PUSH(STACK, TOP, P); //lưu địa chỉ gốc..
P = P->P_L; //..rồi chuyển đến con trái
}
P = POP(STACK, TOP);
if(NutTruoc != NULL && P->KEY < NutTruoc->KEY){
printf("Cây không phải BST");
return false;
}else{
NutTruoc = P;
}
P = P->P_R;
}
return true; //nếu vượt qua đoạn trên thì là BST}
Chia sẻ với bạn bè của bạn: |
