[C++] Hàm xóa một phần tử trong cây nhị phân

[11520132]

Mình đang viết code về xóa một phần tử trong cây nhị phân, hàm của mình như sau:

//Trường hợp đầu tiên : Cây chỉ có 1 phần tử và phần tử muốn xóa là phần tử duy nhất trong cây
void Delete_Case1(Node* &R,Node* &S){
    if (R==S&&E_Replace(R)==NULL) R=NULL;
    else Delete_Case2(R,S);
}
//Trường hợp 2 : Phần tử muốn xóa là phần tử bất kì của cây có nhiều hơn 1 phần tử
void Delete_Case2(Node* &R,Node* &S){
    while (E_Replace(S)){
        S->Data=E_Replace(S)->Data;
        S=E_Replace(S);
    }
    Delete_Case3(R,S); //[COLOR="#FF0000"]<<<<<<<------------------Để ý chỗ này[/COLOR]
}
//Trường hợp 3: Phần tử muốn xóa là phần tử lá
//Hàm sẽ tìm tới Node cha và thay đổi con trỏ trỏ vào Node muốn xóa thành NULL 
void Delete_Case3(Node* &R,Node* &S){
    if (R->Left==S){
        R->Left=NULL;
        return;
    }
    if (R->Right==S){
        R->Right=NULL;
        return;
    }
    if (S->Data<R->Data) Delete_Case3(R->Left,S);
    if (S->Data>R->Data) Delete_Case3(R->Right,S);
}

Trong đó hàm E_Replace() dùng để tìm phần tử thay thế cho phần tử cần xóa.

Node *Max(Node *R){
    if (R)
        while (R->Right)
            R=R->Right;
    return R;
}
Node *Min(Node *R){
    if (R)
        while (R->Left)
            R=R->Left;
    return R;
}
Node *E_Replace(Node *R){
    if (R->Left) return Max(R->Left);
    if (R->Right) return Min(R->Right);
    return NULL;
}

Mình gặp một lỗi mà mình không giải thích được.
Bây giờ mình nhập theo thứ tự là 5 3 4, nghĩa là cây nó như thế này:
5
/
3
\
4

Mình muốn xóa số 4, kết quả là
5
/
3
Kết quả này đúng.
Nhưng bây giờ mình muốn xóa số 5, kết quả lại là
4
/
3
\
4
Khi xóa số 5, có nghĩa là nó sẽ lấy số 4 thế vào chỗ của nó và xóa số 4 đi.
Để ý chỗ dòng màu đỏ. Khi xóa số 4 thì dòng này được thực hiện và khi xóa số 5 cũng vậy. Với S là địa chỉ của số 4. Vậy tại sao khi xóa số 4 thì số 4 mất còn xóa số 5 thì số 4 lại còn đó.
Mình đã kiểm tra nhiều lần, thậm chí đã thay S trên dòng màu đỏ bằng R->Left->Right để chắc chắn lấy đúng địa chỉ của số 4 nhưng vẫn như vậy.

[11520139]

Bạn nên gửi chương trình có thể có ích hơn cho việc sửa lỗi của bạn đó

[11520132]

Code của chương trình nhập xóa:

#include <iostream>
using namespace std;
struct Node{
    int Data;
    Node *Left,*Right;
};
Node *CreateNewNode();
void Init(Node* &R);
void Insert_Case1(Node* &R,Node *E);
void Insert_Case2(Node* &R,Node *E);
Node *Search_Key(Node *R,int K);
void Delete(Node* &R);
void Delete_Case1(Node* &R,Node* &S);
void Delete_Case2(Node* &R,Node* &S);
void Delete_Case3(Node* &R,Node* &S);
Node *E_Replace(Node *R);
Node *Max(Node *R);
Node *Min(Node *R);
void LNR(Node *R);
void RNL(Node *R);
void NLR(Node *R);
int main()
{
    Node *R;
    int select=0;
    Init(R);
    do{
        Insert_Case1(R,CreateNewNode());
        cout<<"0.Exit\n1.Continue\nSelect: ";
        cin>>select;
    }while (select==1);
    Delete(R);
    LNR(R);
    cout<<endl;
    RNL(R);
    cout<<endl;
    NLR(R);
}
//Tạo một phần tử mới
Node *CreateNewNode(){
    Node *E=new Node;
    if (E==NULL) return NULL;
    cout<<"Insert Data :";
    cin>>E->Data;
    E->Left=E->Right=NULL;
    return E;
}
//Khởi tạo cây
void Init(Node* &R){
    R=NULL;
}
//Nhập cây
    //TH1: Cây mới khởi tạo
void Insert_Case1(Node* &R,Node *E){
    if (R==NULL)
        R=E;
    else Insert_Case2(R,E);
}
    //TH2: Cây đã có phần tử
void Insert_Case2(Node* &R,Node *E){
    if (R->Left==NULL&&E->Data<R->Data){
        R->Left=E;
        return;
    }
    if (R->Right==NULL&&E->Data>R->Data){
        R->Right=E;
        return;
    }
    if (R->Left&&E->Data<R->Data) Insert_Case2(R->Left,E);
    if (R->Right&&E->Data>R->Data) Insert_Case2(R->Right,E);
}
//Tìm kiếm với khóa K
Node *Search_Key(Node *R,int K){
    if (R==NULL) return NULL;
    if (R->Data==K) return R;
    if (K<R->Data) return Search_Key(R->Left,K);
    if (K>R->Data) return Search_Key(R->Right,K);
}
//Tìm phần tử thay thế cho phần tử bị xóa
Node *Max(Node *R){
    if (R)
        while (R->Right)
            R=R->Right;
    return R;
}
Node *Min(Node *R){
    if (R)
        while (R->Left)
            R=R->Left;
    return R;
}
Node *E_Replace(Node *R){
    if (R->Left) return Max(R->Left);
    if (R->Right) return Min(R->Right);
    return NULL;
}
//------------------------------------------
void Delete(Node* &R){
    if (R==NULL) return;
    int K;
    cout<<"Insert Key : ";
    cin>>K;
    Node *S=Search_Key(R,K);
    if (S==NULL){
        cout<<"Khong tim thay "<<K<<endl;
        return;
    }
    Delete_Case1(R,S);
}
//Trường hợp đầu tiên : Cây chỉ có 1 phần tử và phần tử muốn xóa là phần tử duy nhất trong cây
void Delete_Case1(Node* &R,Node* &S){
    if (R==S&&E_Replace(R)==NULL) R=NULL;
    else Delete_Case2(R,S);
}
//Trường hợp 2 : Phần tử muốn xóa là phần tử bất kì của cây có nhiều hơn 1 phần tử
void Delete_Case2(Node* &R,Node* &S){
    while (E_Replace(S)){
        S->Data=E_Replace(S)->Data;
        S=E_Replace(S);
    }
    Delete_Case3(R,S);
}
//Trường hợp 3: Phần tử muốn xóa là phần tử lá
//Hàm sẽ tìm tới Node cha và thay đổi con trỏ trỏ vào Node muốn xóa thành NULL
void Delete_Case3(Node* &R,Node* &S){
    if (R->Left==S){
        R->Left=NULL;
        return;
    }
    if (R->Right==S){
        R->Right=NULL;
        return;
    }
    if (S->Data<R->Data) Delete_Case3(R->Left,S);
    if (S->Data>R->Data) Delete_Case3(R->Right,S);
}
//--------------------------------------------------
void LNR(Node *R){
    if (R)
    {
        LNR(R->Left);
        cout<<"   "<<R->Data;
        LNR(R->Right);
    }
}
void RNL(Node *R){
    if (R)
    {
        RNL(R->Right);
        cout<<"   "<<R->Data;
        RNL(R->Left);
    }
}
void NLR(Node *R){
    if (R)
    {
        cout<<"   "<<R->Data;
        NLR(R->Left);
        NLR(R->Right);
    }
} 

[truonganpn]

Mình đang viết code về xóa một phần tử trong cây nhị phân, hàm của mình như sau:

//Trường hợp đầu tiên : Cây chỉ có 1 phần tử và phần tử muốn xóa là phần tử duy nhất trong cây
void Delete_Case1(Node* &R,Node* &S){
    if (R==S&&E_Replace(R)==NULL) R=NULL;
    else Delete_Case2(R,S);
}
//Trường hợp 2 : Phần tử muốn xóa là phần tử bất kì của cây có nhiều hơn 1 phần tử
void Delete_Case2(Node* &R,Node* &S){
    while (E_Replace(S)){
        [COLOR="#B22222"]S->Data=E_Replace(S)->Data;[/COLOR]
        S=E_Replace(S);
    }
    Delete_Case3(R,S); //[COLOR="#FF0000"]<<<<<<<------------------Để ý chỗ này[/COLOR]
}
//Trường hợp 3: Phần tử muốn xóa là phần tử lá
//Hàm sẽ tìm tới Node cha và thay đổi con trỏ trỏ vào Node muốn xóa thành NULL 
void Delete_Case3(Node* &R,Node* &S){
    if (R->Left==S){
        R->Left=NULL;
        return;
    }
    if (R->Right==S){
        R->Right=NULL;
        return;
    }
[COLOR="#2222B2"]    if (S->Data<R->Data) Delete_Case3(R->Left,S);
    if (S->Data>R->Data) Delete_Case3(R->Right,S);[/COLOR]
}

Chạy debug em sẽ thấy là 2 dòng if màu xanh đều có phần điều kiện sai và bị bỏ qua vì bây giờ S và R có data bằng nhau do cái dòng màu đỏ sậm ở trên.

[11520473]

Bây giờ mình nhập theo thứ tự là 5 3 4, nghĩa là cây nó như thế này:
5
/
3
\
4

Mình muốn xóa số 4, kết quả là
5
/
3
Kết quả này đúng.
Nhưng bây giờ mình muốn xóa số 5, kết quả lại là
4
/
3
\
4
Khi xóa số 5, có nghĩa là nó sẽ lấy số 4 thế vào chỗ của nó và xóa số 4 đi.
Để ý chỗ dòng màu đỏ. Khi xóa số 4 thì dòng này được thực hiện và khi xóa số 5 cũng vậy. Với S là địa chỉ của số 4. Vậy tại sao khi xóa số 4 thì số 4 mất còn xóa số 5 thì số 4 lại còn đó.
Mình đã kiểm tra nhiều lần, thậm chí đã thay S trên dòng màu đỏ bằng R->Left->Right để chắc chắn lấy đúng địa chỉ của số 4 nhưng vẫn như vậy.

Mình nghĩ là cây phải thế này chứ:

5
/ \
3 4

[truonganpn]

Mình nghĩ là cây phải thế này chứ:

      5
    /   \
  3     4

4 làm sao lớn hơn 5 được hả em?.

Lần sau muốn gõ có nhiều khoản trắng mà không bị cắt bớt thì để trong thẻ CODE nhá

[11520473]

4 làm sao lớn hơn 5 được hả em?.

Lần sau muốn gõ có nhiều khoản trắng mà không bị cắt bớt thì để trong thẻ CODE nhá

ủa em lộn. viết mà không để ý. hihi

[11520132]

Em cám ơn thầy, em làm được rồi