Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 13 kết quả

Đề tài: [LT][Tìm kiếm]Xóa node trong cây nhị phân tìm kiếm

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

    Unhappy [LT][Tìm kiếm]Xóa node trong cây nhị phân tìm kiếm

    Có bác nào giúp Schtroumpfs với, cái đề nó kiu là xóa một node nào đó trong cây nhị phần tìm kiếm sao cho khi xóa node ấy thì các node con của nó sẽ mất đi với số lượng ít nhất đồng thời thỏa mãn cây sau khi xóa vẫn là cây nhị phân tìm kiếm

    Em chỉ biết mỗi thuật giải xóa một phần tử X nào đó thui hà
    Đã được chỉnh sửa lần cuối bởi schtroumpfs : 27-05-2007 lúc 07:59 PM.

  2. #2
    Ngày gia nhập
    04 2007
    Bài viết
    128

    Hix chắc ý bạn là xóa 1 nút chứ, nếu đã là cây nhị phân thì xóa ít nhất là 0 nút để trở thành 1 cây nhị phân . Nếu tui nói sai thì cho ví dụ lại nhá. Còn xóa 1 nút bất kì thì trong sách có hết mà.

  3. #3
    Ngày gia nhập
    01 2007
    Bài viết
    412

    Trích dẫn Nguyên bản được gửi bởi schtroumpfs Xem bài viết
    Có bác nào giúp Schtroumpfs với, cái đề nó kiu là xóa node trong cây nhị phần tìm kiếm sao cho số node xóa đi là ít nhất mà vẫn thỏa mãn cây sau khi xóa vẫn là cây nhị phân tìm kiếm

    Em chỉ biết mỗi thuật giải xóa một phần tử X nào đó thui hà
    Bạn cho ví dụ minh họa được không, đọc đề khó hiểu quá, xóa n nút à??
    Cách xóa nhanh nhất là xóa mấy nút lá, gặp-là-xóa, khỏi cần dùng hàm kiểm tra xem cây nhị phân đó còn là cây NPTK nữa hay không.

  4. #4
    Ngày gia nhập
    05 2007
    Bài viết
    6

    Dạ! giả sử như cây mình có 10 node, khi mình xóa 1 node nào đó thì các node con dưới nó sẽ mất đi, và giả sử ta có các trường hợp
    xóa node A thì làm mất 2 node con
    xóa node B thì làm mất 3 node con
    xóa node C thì làm mất 7 node con
    ------> như vậy ta chọn cách xóa node A
    ý em là thế ạh

    Hông bít như dzậy có rõ nghĩa chưa nữa
    Cám ơn mấy bạn nhìu ^_^

  5. #5
    Ngày gia nhập
    04 2007
    Bài viết
    128

    Hix, vẫn chưa hiểu, tức là nhập vô 3 hay 4 nút để xóa, rồi chương trình sẽ chọn ra 1 nút xóa ít nhất. Chứ nếu bắt buộc xóa 1 nút bất kì thì cứ nút lá mà xóa chứ nhỉ?

  6. #6
    Ngày gia nhập
    05 2007
    Bài viết
    6

    Mặc định [LT][Tìm kiếm]Xóa node trong cây nhị phân tìm kiếm

    nhưng sau khi xóa node lá liệu nó có còn là cây nhị phân tìm kiếm nữa ko nhỉ,

    nhưng em vẩn ko biết được làm cách nào cho nó xóa một cách tự động, để thỏa mãn kia

  7. #7
    Ngày gia nhập
    04 2007
    Bài viết
    128

    Hè,tất nhiên là còn rồi, thử đi rồi biết!!

  8. #8
    Ngày gia nhập
    05 2007
    Bài viết
    6

    híc, em đang pótay cái vụ để nó xóa tự động muh phải chi chỉ định xóa node nào còn đỡ, còn cái này cho nó xóa ngẫu nhiên, em pó chiếu

  9. #9
    Ngày gia nhập
    01 2007
    Bài viết
    412

    Trích dẫn Nguyên bản được gửi bởi schtroumpfs Xem bài viết
    Dạ! giả sử như cây mình có 10 node, khi mình xóa 1 node nào đó thì các node con dưới nó sẽ mất đi, và giả sử ta có các trường hợp
    xóa node A thì làm mất 2 node con
    xóa node B thì làm mất 3 node con
    xóa node C thì làm mất 7 node con
    ------> như vậy ta chọn cách xóa node A
    ý em là thế ạh

    Hông bít như dzậy có rõ nghĩa chưa nữa
    Cám ơn mấy bạn nhìu ^_^
    xóa node A thì làm mất 2 node con
    xóa node B thì làm mất 3 node con
    xóa node lá thì làm mất 0 con
    ==> như vậy ta chọn cách xóa nút lá (và luôn luôn phải chọn rồi)
    Ý mình như thế được không bạn?

  10. #10
    Ngày gia nhập
    04 2007
    Bài viết
    128

    hè, ngẫu nhiên, ờ... hàm xóa :
    Code:
    xoa(NUT *gốc)
    { NUT*p=gốc;
        if (gốc->trái==NULL || gốc->phải==NULL)
                    delete p;
        else if (gốc->trái==NULL)
                   xóa(gốc ->phải);
              else if(gốc->phải==NULL) 
                   xóa(gốc->trai);
                    else
                          if(random(1 hoặc 0))
                              xóa (gốc ->trai);  
                          else xóa(gốc-> phải);
    }
    viết trên đây nhìn hơi rối, nhưng tui nghĩ xóa random nó vậy, ko biết có ý kiến bào hay hơn ko?

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 tất cả các node là số nguyên tố trong cây nhị phân tìm kiếm
    Gửi bởi mr.anonymous trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 0
    Bài viết cuối: 19-06-2013, 11:40 PM
  3. Bài tập C Lỗi hàm xóa 1 node trong cây nhị phân tìm kiếm không dùng đệ quy
    Gửi bởi taphoc_c trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 06-06-2013, 11:02 AM
  4. Hàm trong C Khẩn cấp về hàm chèn node trong cây nhị phân tìm kiếm
    Gửi bởi rongphuthuy1 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 10-05-2013, 12:16 AM
  5. 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

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