Announcement

Collapse
No announcement yet.

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

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

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

    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); //[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.
    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.
    Last edited by 11520132; 13-05-2012, 23:21.


  • #2
    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 đó
    :love:
    Tương lai khóc hay cười phụ thuộc vào độ lười của quá khứ.
    :cry:

    Comment


    • #3
      Code của chương trình nhập xóa:
      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);
          }

      Last edited by 11520132; 13-05-2012, 22:50.

      Comment


      • #4
        Originally posted by 11520132 View Post
        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)){
                [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.

        Comment


        • #5
          Originally posted by 11520132 View Post

          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
          http://picshome.com/getfile.php?id=1...ame=MySign.png

          Comment


          • #6
            Originally posted by 11520473 View Post
            Mình nghĩ là cây phải thế này chứ:

            Code:
                  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á

            Comment


            • #7
              Originally posted by truonganpn View Post
              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
              http://picshome.com/getfile.php?id=1...ame=MySign.png

              Comment


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

                Comment

                LHQC

                Collapse
                Working...
                X