Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Từ 1 tới 6 trên tổng số 6 kết quả

Đề tài: Kỹ thuật xóa node trên cây nhị phân

  1. #1
    No Avatar
    hiepsithong Khách

    Talking Kỹ thuật xóa node trên cây nhị phân

    C Code:
    1. TREE delete_node(TREE &p)
    2. {
    3.   TREE rp,f;
    4.  
    5.   if (p==NULL)
    6.     printf("Ko co nut nay");
    7.   else
    8.     {
    9.     if (p->left==NULL)   //ko co nhanh ben phai
    10.       p = p->right;
    11.     else
    12.       if (p->right==NULL)    // ko co nhanh ben trai
    13.     p = p->right;
    14.       else                // co hai nhanh
    15.       {
    16.     //tim nut the mang rp va nut f la nut cha cua nut the mang
    17.     f = p;
    18.     rp = p->right;      //chon nut trai nhat cua cay con ben phai
    19.     while (rp->left!=NULL)
    20.     {
    21.        f = rp;
    22.        rp = rp->left;
    23.     }
    24.     p->info = rp->info;
    25.     if (f!=p)
    26.        f->left = rp->right;
    27.     else
    28.        p->right = rp->right;  //neu nut p chi co duy I 2 con
    29.       }
    30.       free(rp);
    31.       return p;
    32.     }
    33. }

    Đây là code xóa 1 node trên cây nhị phân nhưng sao mình chỉ xóa được node gốc, node có 2 con, node lá còn lại các node chỉ có 1 con thì lại ko xóa được mong các pác chỉ giúp cho. Thank for your help.
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

  2. #2
    Ngày gia nhập
    07 2006
    Bài viết
    121

    Thần chú : Xóa con rồi mới xóa cha.
    Thử viết đệ quy như sau coi
    Code:
     Xóa(n){
        if(n!=null){
           if(n->left!=null) //tức con bên trái còn.
                xóa(n->left);//xóa con bên trái.
           if(n->right!=null)//tức con bên phải còn
                xóa(n->right);//xóa con bên phải.
           delete n;
       }

  3. #3
    Ngày gia nhập
    07 2006
    Bài viết
    121

    À quên nữa mình muốn hỏi cậu là định xóa một node hay xóa toàn bộ luôn các nhánh con của node ?
    Và khi xóa thì các node con được dồn lên theo cơ chế nào?
    Chú ý: cho ví dụ mô tả càng tốt.

  4. #4
    No Avatar
    hiepsithong Khách

    Ví dụ như mình có cây nhị phân tìm kiếm gom 1 mảng các số nguyên sau: 5,10,12,15,16,18,20,25,28,30,35
    Giờ mình cần xóa nút mang giá trị 18 thì chương trình trên lại ko cho kết quả đúng. Chương trình đó chỉ đúng với các nút có 2 con còn với nút lá và các nút chỉ có 1 con thì lại cho kết quả sai. Xin các bro chỉ giáo???

  5. #5
    Ngày gia nhập
    07 2006
    Bài viết
    121

    Trích dẫn Nguyên bản được gửi bởi hiepsithong
    Ví dụ như mình có cây nhị phân tìm kiếm gom 1 mảng các số nguyên sau: 5,10,12,15,16,18,20,25,28,30,35
    Giờ mình cần xóa nút mang giá trị 18 thì chương trình trên lại ko cho kết quả đúng. Chương trình đó chỉ đúng với các nút có 2 con còn với nút lá và các nút chỉ có 1 con thì lại cho kết quả sai. Xin các bro chỉ giáo???
    Cậu thử làm theo các sau đây:
    Tôi có một số hàm sau:
    Hàm node_t SearchLa(tree t); //Hàm này dùng để tìm node lá gần nhất của một cây hàm này cậu cũng có thể cài đặt đệ quy duyệt tìm thấy nú là thì trả về nút đó.(tự cài đặt)
    Hàm swapNode(Node_t node1,Node_t node2); dùng để hoán đổi giá trị của hai node trên cây nhị phân (tự cài đặt)
    Code chính:
    Input node_t node là node cần xóa.
    Code:
    Nếu node không có con thì xóa node;
    Nếu node có con bên trái thì 
           {
                 temp=SearchLa(node->left);//duyệt tìm lá gần nhất của cây con bên trái
                 swapNode(node,temp);
                 delete temp;
           }
    Ngược lại nếu có cây con bên phải thì
         {
                  temp=SearchLa(node->left);
                  swapNode(node,temp);
                  delete temp;
         }
    Thuật toán trên như sau: Nếu node bạn cần xóa là node không có con thì xóa. Nếu có con thì tìm 1 là của cây con bên trái hay phải sau đó chuyển giá trị của lá lên node cần xóa cuối cùng là xóa lá.

  6. #6
    No Avatar
    hiepsithong Khách

    Mặc định Kỹ thuật xóa node trên cây nhị phân

    thank for your help
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

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

  1. Cấu trúc dữ liệu Tìm thuật toán trả về Node cha của một Node bất kỳ trong cây nhị phân tìm kiếm
    Gửi bởi A10932 trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 10
    Bài viết cuối: 20-08-2013, 12:30 PM
  2. Xóa hết các NODE tron cây như thế nào?
    Gửi bởi namboygacon trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 29-04-2011, 01:28 PM
  3. xóa node có ràng buộc
    Gửi bởi dangwru trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 4
    Bài viết cuối: 29-06-2010, 11:29 AM
  4. Tạo cây tìm kiếm thêm node và xóa
    Gửi bởi huy1710 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: 03-03-2010, 05:45 PM
  5. không thể xóa node theo ý muốn dc
    Gửi bởi thaibinhindex trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 28-02-2009, 09:55 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