Trang 1 trên tổng số 3 123 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 25 kết quả

Đề tài: [LT][Cây]Các vấn đề về cây nhị phân

  1. #1
    Ngày gia nhập
    06 2007
    Nơi ở
    Binh Duong
    Bài viết
    26

    Mặc định [LT][Cây]Các vấn đề về cây nhị phân

    Cho 3 cách duyệt cây như sau (Kí hiệu L: Left; N: NodeRoot; R: Right)
    LNR: 12,36,18,40,10,45,11,8,5,55,21
    NLR: 40,36,12,18,55,45,10,8,11,2,21
    LRN: 12,18,36,10,11,5,8,45,21,55,40
    Hãy vẽ cây nhị phân trên

  2. #2
    Ngày gia nhập
    06 2007
    Nơi ở
    Binh Duong
    Bài viết
    26

    Bài này mình đưa ra cách giải như thế này, các bác thử xem sao. Mà bác nào có cách khac thì post lên cho anh em coi đi

  3. #3
    Ngày gia nhập
    06 2007
    Nơi ở
    Binh Duong
    Bài viết
    26

    Bước 1: T ừ 3 phép duyệt trên
    LNR: 12,36,18, 40, 10,45,11,8,5,55,21
    NLR: 40, 36,12,18 ,55,45,10,8,11,2,21
    LRN: 12,18,36,10,11,5,8,45,21,55, 40

    Ta dễ dàng tìm đ ược :
    -Node gốc l à 40
    -Cây con bên trái có 3 Node là 12,36,18
    -Cây con bên phải có 7 Node là:10,45,11,8,5,55,21
    Bước 2: Xét cây con bên trái với 3 phép duyệt trên như sau:
    LNR: 12 ,36, 18
    NLR: 36, 12, 18
    LRN: 12 ,18, 36
    Ta suy ra:
    -Node gốc cây con trái là 36
    -Node bên trái là 12
    -Node bên phải là 18
    Bước 3: Xét cây con phải cũng với ba phép duyệt trên như sau:

    LNR : 10,45,11,8,5, 55, 21
    NLR: 55, 45,10,8,11,2, 21
    LRN: 10,11,5,8,45, 21, 55
    Ta t ìm đ ược
    -Node gốc cây con phải l à 55
    -Cây con trái của cây con phải cây cần tìm có các ph ần tử 10,45,11,8,5
    -Cây con phải của c ây con phải cây cần tìm có các phần tử 21
    Bước 3: Ti ếp t ục x ét c ây con chứa các phần tử10,45,11,8,5 với 3 phép duyệt trên:
    LNR :10, 45, 11,8,5
    NLR:45, 10, 8,11,5
    LRN:10, 11,5,8, 45

    Bước…
    Tóm lại với việc chia nhỏ cây nhị phân cần tìm ra thành nhiều cây nhỏ hơn với 3 phép duyệt trên ta tìm đ ược cây nhị phân sau:

    Hi chúc một ngày vui vẻ
    Đã được chỉnh sửa lần cuối bởi BoBo : 26-06-2007 lúc 04:43 PM.

  4. #4
    Ngày gia nhập
    06 2007
    Nơi ở
    Binh Duong
    Bài viết
    26

    Bác nào vẽ ra cái cây dùm nhé

  5. #5
    Ngày gia nhập
    06 2007
    Nơi ở
    Binh Duong
    Bài viết
    26

    Ah ma wuen có ai có bài về cây nhị phân tìm kiếm không ta, càng nhiều càng ít post lên cho anh em coi tí đi

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

    Mặc định [LT][Cây]Các vấn đề về cây nhị phân

    """Ta dễ dàng tìm đ ược :
    -Node gốc l à 40
    -Cây con bên trái có 3 Node là 12,36,40
    -Cây con bên phải có 7 Node là:10,45,11,8,5,55,21"""
    trong nay toi nghi ban sai :
    Cay con ben trai co 3 Node la :12,36,18 chứ khong phải là "12,36,40"

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

    Tại sao tại bước 3 gốc là 55, cây con bên phải là 21 nhưng theo lý thuyết về cây nhị phân các khóa bên phải luôn > gốc ???????????Hình như dữ liệu đưa vào sai !!!!!1 Còn cách duyệt như bạn thì ok

  8. #8
    Ngày gia nhập
    06 2007
    Nơi ở
    Binh Duong
    Bài viết
    26

    Nhở tách nhỏ cây nhị phân ra với ba cách duyệt :
    LNR : 10,45,11,8,5, 55, 21
    NLR: 55, 45,10,8,11,2, 21
    LRN: 10,11,5,8,45, 21, 55
    Thì rõ ràng nhờ cách duyệt số 2: NLR ta dễ dàng tìm được Node gốc cây con phải là 55.
    Còn bạn cho rằng khóa bên phải luôn > gốc là một quan niệm đúng nhưng nó đúng với cây nhị phân tìm kiếm thui. Còn đây chỉ là một cây nhị phân bình thường.

  9. #9
    Ngày gia nhập
    06 2007
    Nơi ở
    Binh Duong
    Bài viết
    26

    Còn về cây con trái thì bạn nói đúng đấy. Cây con trái có ba node la 12,36 và 18.Mình viết sai. Hi cám ơn bạn ThaoThao nhiều nhé. Bo sửa lại rùi đấy

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

    Bác BoBo phân tích hết rồi mà vậy thì phải làm gì đây?
    Cây nhị phân tìm kiếm (C++)

    PHP Code:
    #include<stdio.h>
    #include<iostream.h>
    #include<conio.h>
    //kieu du lieu Khoa
    typedef int KieuKhoa;
    //kieu dliue trong nut
    typedef int KieuDL ;
    //kieu dlieu nut
    typedef struct Nut
    {
        
    struct Nut(KieuKhoa Khoa,KieuDL duLieu)
        {
            
    this ->Khoa=Khoa;
            
    this ->duLieu=duLieu;
            
    this ->trai=NULL;
            
    this ->phai=NULL;
        }
        
    KieuKhoa Khoa;
        
    KieuDL duLieu;
        
    struct Nut *trai;
        
    struct Nut *phai;
    NUT ;

    //Kieu CayNPTK
    class CayNPTK
    {
    private : 
        
        
    NUT *goc
        
    int soNut;
        
    void them(NUT *& ,NUT *);
        
    void xulyNut(NUT *);
        
    int demSoNutLa(NUT *);
        
    NUT *timCT(NUT *);
        
    int tinhCCao(NUT *);
        
    NUT *timCP(NUT *);
        
    void huyNut(NUT *);
    public :
        
    CayNPTK();
        ~
    CayNPTK();
        
    void themNut(KieuKhoa,KieuDL);
        
    void huyCayNPTK();
        
    bool CayRong();
        
    void huyNPTK();
        
    void duyetGTP();
        
    int demNutLa();
        
    NUT *timNutCT();
        
    NUT *timNutCP();
        
    int tinhChieuCao();
        
    NUT *timK(KieuKhoa);
    }; 
    Hiện thực các phương thức.
    PHP Code:
    #include<conio.h>
    #include "CayNPTK.h"
    #include<iostream.h>
    ///////////////////////////
     
    CayNPTK::CayNPTK()
    {
        
    this->goc=NULL;
        
    soNut=0;
    }
    ///////////////////////////////////////
    CayNPTK::~CayNPTK()
    {
        
    CayNPTK::huyCayNPTK();
    }
    ////////////////////////////
    void CayNPTK::them(NUT *&goc,NUT *nutMoi)
    {
        if (
    goc==NULL)
        {
            
    goc=nutMoi;
             
    soNut++;
        }
        else 
            if (
    goc->Khoa<nutMoi->Khoa)
                 
    them(goc->phai,nutMoi);
            else
                  
    them(goc->trai,nutMoi);
    }
    //////////////////////////////////////////////////
    void CayNPTK::themNut(KieuKhoa Khoa,KieuDL duLieu)
    {
        
    NUT *nutMoi= new NUT(Khoa,duLieu);
        
    them(goc,nutMoi);
    }
    /////////////////////////////////////////////////
    void CayNPTK::xulyNut(NUT *goc)
    {
        if(
    goc!=NULL)
        {
            
    cout<<goc->Khoa<<" "<<goc->duLieu;
            
    xulyNut(goc->trai);
            
    xulyNut(goc->phai);
        }
    }

    ////////////////////////////////////////////////
    void CayNPTK::duyetGTP()
    {
        
    xulyNut(goc);
    }
    ////////////////////////////////////////////////
    int CayNPTK::demSoNutLa(NUT *goc)
    {
        if(
    goc==NULL)
            return  
    0;
        if (
    goc->trai==NULL&&goc->phai==NULL)
            return 
    1;
        return 
    demSoNutLa(goc->trai)+demSoNutLa(goc->phai);
    }
    ////////////////////////////////////////////////////
    int CayNPTK::demNutLa()
    {
        return 
    demSoNutLa(this->goc);
    }
    //////////////////////////////////////////////////////
    NUT *CayNPTK::timCT(NUT *goc)
    {
        if(
    goc==NULL)
            return 
    NULL;
        else
            if(
    goc->trai==NULL)
                return 
    goc;
            else
                return 
    timCT(goc->trai);
    }
    /////////////////////////////////////////////////////////////
    NUT *CayNPTK::timNutCT()
    {
        return 
    timCT(this->goc);
    }
    /////////////////////////////////////////////////////////////
    int CayNPTK::tinhCCao(NUT *goc)
    {
        if(
    goc==NULL) return 0;
        else 
        {
            
    int caoTrai=tinhCCao(goc->trai);
            
    int   caoPhai=tinhCCao(goc->phai);
            return (
    1+(caoTrai>caoPhai?caoTrai:caoPhai));
        }
    }
    //////////////////////////////////////////////////////////////
    int CayNPTK::tinhChieuCao()
    {
        return 
    tinhCCao(this->goc);
    }
    /////////////////////////////////////////////////////////////////
    void CayNPTK::huyNut(NUT *goc)
    {
        if(
    goc!=NULL)
        {
            
    huyNut(goc->trai);
            
    huyNut(goc->phai);
            
    delete goc;
        }
    }
    ///////////////////////////////////////////////////////////////////
    void CayNPTK::huyCayNPTK()
    {
        
    huyNut(this->goc);
    }
    //////////////////////////////////////////////////////////////////// 

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