Từ 1 tới 3 trên tổng số 3 kết quả

Đề tài: [Help]Lỗi kì lạ - Xóa một phần tử trong cây nhị phân tìm kiếm.

  1. #1
    Ngày gia nhập
    05 2012
    Bài viết
    0

    Mặc định [Help]Lỗi kì lạ - Xóa một phần tử trong cây nhị phân tìm kiếm.

    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:
    Code:
    //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); //<<<<<<<------------------Để ý chỗ này
    }
    //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.
    Code:
    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.
    Đã được chỉnh sửa lần cuối bởi A a : 13-05-2012 lúc 10:20 PM.

  2. #2
    Ngày gia nhập
    05 2012
    Bài viết
    0

    Mặc định Toàn bộ code bài của mình

    Còn đây là toàn bộ code bài của mình :
    PHP Code:
    #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->DataInsert_Case2(R->Left,E);
        if (
    R->Right&&E->Data>R->DataInsert_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)==NULLR=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->DataDelete_Case3(R->Left,S);
        if (
    S->Data>R->DataDelete_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);
        }


  3. #3
    Ngày gia nhập
    08 2011
    Bài viết
    117

    Mới xem qua code của bạn. bạn sửa function Delete_Case2 tạm thời thành thế này :

    C Code:
    1. void Delete_Case2(Node* &R,Node* &S){
    2.     Node *temp = E_Replace(S);
    3.     if(!temp) {
    4.         Delete_Case3(R,S);
    5.         return;
    6.     }
    7.     int dataTemp = temp->Data;
    8.     Delete_Case3(R,temp);
    9.     S->Data=dataTemp;
    10. }

    Caution : bộ nhớ của bạn chưa được giải phóng.

Các đề tài tương tự

  1. Giúp mình về xóa phần tử lá trong cây nhị phân tìm kiếm
    Gửi bởi bangdienc9 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 18-05-2012, 02:09 PM
  2. Lập trình C++ xóa một phần tử trong cây nhị phân tìm kiếm
    Gửi bởi nhatnha trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 16-12-2010, 01:40 AM
  3. tìm kiếm tất cả phần tử và xóa phần tử?
    Gửi bởi danchithancong trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 13
    Bài viết cuối: 28-09-2009, 03:28 PM
  4. [Hỏi] Xóa phần tử x trong cây nhị phân tìm kiếm
    Gửi bởi manasuke trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 3
    Bài viết cuối: 01-01-2009, 11:22 AM
  5. [LT][Tìm kiếm]Xóa node trong cây nhị phân tìm kiếm
    Gửi bởi schtroumpfs trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 12
    Bài viết cuối: 05-06-2007, 05:47 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn