Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    huyenminh


    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ
    Bạn nào hiểu bài này làm giúp mình với, mình không đi học nên bài này khó hiểu quá.

    1. Cho dãy có n số nguyên {A1,...,An} đôi một khác nhau.
    a. Mô tả thủ tục xây dựng cây nhị phân tìm kiếm có khoá là các phần tử trong dãy.

    b. Vẽ sơ đồ khối mô tả thuật toán.

    c. Áp dụng vẽ cây nhị phân tìm kiếm cho danh sách

    19, 25, 21, 22, 18, 16, 45, 32, 11, 14, 37

    BanQT: Đề nghị viết tiêu đề rõ ràng, rành mạch để người khác tiện theo dõi. Không được ghi chung chung tiêu đề như bạn đã ghi như cứu với, xin giúp... khi BBT kích hoạt bộ lọc, tiêu đề như vậy sẽ bị autodelete.
    Ban QT: [You must be registered and logged in to see this link.]



    Được sửa bởi Admin ngày Sat Jul 23, 2011 11:10 pm; sửa lần 3. (Reason for editing : Sửa tiêu đề, nhắc nhở)

    Admin


    Quản trị viên
    Quản trị viên
    Vài nét về cây nhị phân tìm kiếm
    Cây nhị phân tìm kiếm là cây nhị phân trong đó:
    - Mỗi con của một đỉnh hoặc là con bên phải, hoặc là con bên trái
    - Không có đỉnh nào có hơn 1 con bên phải hoặc hơn 1 con bên trái.
    Nói cách khác đó là mọt cây nhị phân được sắp mà mỗi đỉnh gán một giá trị khóa . Khóa này thỏa mãn yêu cầu là khóa của một đỉnh lớn hơn tất cả các đỉnh thuộc cây con bên trái và nhỏ hơn khóa của tất cả các đỉnh thuộc cây con bên phải của nó.
    Tạo một cây nhị phân tìm kiếm mà khóa tại mỗi đỉnh của nó chính là khóa trong danh sách (hay mảng đang được xem xét). Việc lưu trữ giá trị khóa trong danh sách vào khóa của các đỉnh được thực hiện như sau:
    - Khởi tạo cây có 1 đỉnh - gọi là gốc. Phần tử đầu tiên trong danh sách được dùng làm khóa của gốc.
    - Lần lượt xét từng giá trị trong danh sách , từ phần tử thứ 2 cho đến phần tử cuối cùng. Thực hiện thêm từng phần tử vào cây bằng cách:
    + So sánh nó với khóa của các đỉnh đã có trên cây bắt đàu từ gốc.
    + Rẽ sang trái nếu giá trị của phần tử này bé hơn khóa.
    + Rẽ sang phải nếu giá trị của phần tử này lớn hơn khóa.
    Trong trường hợp giá trị của phần tử này bé hơn khóa của đỉnh được xét mà đỉnh này không có con bên trái thì tạo ra đỉnh mới cho phần tử này (như con bên trái của nó). Phần tử đang xét được chọn làm khóa cho đỉnh mới. Tương tự như vậy nếu giá trị phần tử mới lớn hơn khóa của đình được xét mà đỉnh này không có con bên phải.
    Một số code cho bài toán cây nhị phân tìm kiếm
    a)
    Thủ tục con, thêm một phần tử:
    PROCEDURE Thêm_PT (Pt: Phần tử; VAR T: cây;
    IF T = Nil THEN T : = Pt;
              ELSE
                        IF Pt.Data < Khóa THEN Thêm_PT (Pt, T.Con_trái)
                                  ELSE Thêm_PT (PT, T.Con_phải)
    b)
    Thủ tục tạo cây nhị phân tìm kiếm:
    1)Khởi tạo T; T.Data := Phần tử thứ 1 trong mảng; T.Left = Nil; T.Right = Nil;
    2) FOR i := 2 TO n DO
              a) Khởi tạo Pt; Pt.Data = phần tử thứ i trong mảng; P.Left = Nil, P.Right = Nil;
              b) Thêm_Pt (Pt, T)
    Hi vọng với lý thuyết trên, bạn có thể thay tương ứng với bài tập của mình. Chúc bạn biết cách thay mà không bị lỗi. Nếu bạn đã điền đủ thông tin nghiêm túc và chính xác trong lý lịch, bạn sẽ thấy một thư mục bài chuẩn hiện ra để giúp bạn tham khảo bài giải mẫu.


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    HaiYen


    Thành viên cao cấp
    Thành viên cao cấp
    Em dám chắc là hầu như 100% chúng ta sẽ không viết đúng, gọn và kín kẽ được thuật toán: làm thế nào để xóa được một phần tử X của cây nhị phân tìm kiếm. Các thành viên siêu nhất cũng sẽ làm sai câu này, nên đề thi có ra câu này là câu khó nhất thì cũng không ai làm được trọn vẹn. Riêng xem cách lập luận thì may ra có anh Tongmanhcuong là có cách lập luận có lý, và ... sẽ là người sai nhiều nhất trong số chúng ta.


    ================
    Nhà em cách 4 quả đồi
    Cách 3 con suối, cách đôi cánh rừng
    Nhà em xa cách quá chừng
    Em van anh đấy, anh đừng yêu em!...

    FaceBook của em

    trinhgiang9793


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    sao khó hiểu vậy ak

    Sponsored content


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of http://khmt.123.st

    Free forum | © PunBB | Free forum support | Liên hệ | Report an abuse | Create a free blog