Trang 1/2 12 cuối
kết quả từ 1 tới 12 trên 16

Bài tập C: Cây nhị phân tìm kiếm có phần tử trùng nhau

  1. #1
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 353076
    Giới tính: Nam
    Bài gửi
    45
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    874

    Reply: Cay nhi phan tim kiem cac gia tri co the trung nhau

    Với cây nhị phân thì cho phép 2 phần tử bằng nhau mà. Bạn chỉ cần quy định nếu bằng nhau thì theo về một nhánh nào đó. Ví dụ như x.left < x, còn x.right >= x. Khi tìm kiếm thì dựa vào đó để duyệt.
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. #3
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 353076
    Giới tính: Nam
    Bài gửi
    45

    Reply: Cay nhi phan tim kiem cac gia tri co the trung nhau

    cho minh xin 1 vi du duoc khong ban, hic

  4. #4
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    874

    Reply: Cay nhi phan tim kiem cac gia tri co the trung nhau

    Giả sử mình insert những số 3, 0, 7, 8, 7, 0, 1 3 vào binary search tree với convention như post #2 của mình, mình sẽ đc
    Mã:
               3
       0              7
          0       3       8
            1           7
    Bạn cứ việc theo sát cái convention như post #2 là đc, ko có gì phức tạp cả.

  5. #5
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 353076
    Giới tính: Nam
    Bài gửi
    45

    Reply: Bài tập C: Cây nhị phân tìm kiếm có phần tử trùng nhau

    Mã:
    int chennut(tree &root, int k)
    {
     if(root!=NULL)
     {
      if(root->info==k) return 0;
      if(root->info>k) return chennut(root->left,k);
      else return chennut(root->right,k);
     }
     else
     {
      root =new node;
      if(root==NULL) return -1;
      root->info=k;
      root->left=root->right=NULL;
      return 1;
     }
    }
    nho ban xem chinh lai code nay cho phu hop voi cay tren dc ko ban

  6. #6
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    874

    Reply: Bài tập C: Cây nhị phân tìm kiếm có phần tử trùng nhau

    Đoạn code của bạn chỉ cần bỏ dòng này thử chạy xem.
    Mã:
    if (root->info == k) return 0;
    Bạn nên hiểu cho rõ đoạn code trên làm gì trước đã rồi hãy modify nó.

  7. Đã cảm ơn tengiday:


  8. #7
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 353076
    Giới tính: Nam
    Bài gửi
    45

    Reply: Bài tập C: Cây nhị phân tìm kiếm có phần tử trùng nhau

    cho minh hoi, tao 1 cay nhi phan tim kiem kieu phan so. lam nhu the nao ban

  9. #8
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    874

    Reply: Bài tập C: Cây nhị phân tìm kiếm có phần tử trùng nhau

    Trích Nguyên văn bởi Organvn Xem bài viết
    cho minh hoi, tao 1 cay nhi phan tim kiem kieu phan so. lam nhu the nao ban
    Bạn cần 1 struct kiểu thế này:
    Mã:
    struct Fraction {
        int num, den;
        Fraction(int n, int d) : num(n), den(d) {}
        
        bool operator<(const Fraction &f) const {
            return num * f.den < den * f.num;
        }
    };
    Nếu cần operator nào khác thì có thể thêm vào nhé. Còn phần node trong tree thì bạn để kiểu dữ liệu là Fraction là xong.

  10. #9
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 353076
    Giới tính: Nam
    Bài gửi
    45

    Reply: Bài tập C: Cây nhị phân tìm kiếm có phần tử trùng nhau

    Mã:
    struct node
    {
     int info;
     struct node *left, *right;
    };
    typedef node *tree;
    int chennut(tree &root, int k)
    {
     if(root!=NULL)
     {
      if(root->info==k) return 0;
      if(root->info>k) return chennut(root->left,k);
      else return chennut(root->right,k);
     }
     else
     {
      root =new node;
      if(root==NULL) return -1;
      root->info=k;
      root->left=root->right=NULL;
      return 1;
     }
    }
    int themphantu(tree &root, int x)
    {
     if(root!=NULL)
     {
       if(root->info>x)
       return themphantu(root->left,x);
      else
       return themphantu(root->right,x);
     }
     root =new  node;
     if(root==NULL) return -1;
     root->info=x;
     root->left=root->right=NULL;
     return 1;
    }
    void taocay(tree &root)
    {
     int k,n;
     cout<<"\nNhap vao n=";cin>>n;
     root=NULL;
     for(int i=1;i<=n;i++)
     {
      cin>>k;
      chennut(root,k);
     }
    }
    code nay chinh lai nhu the nao ban, nho ban giup. do mh biet it nen nho ban xem qua dum mh

  11. #10
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    874

    Reply: Bài tập C: Cây nhị phân tìm kiếm có phần tử trùng nhau

    Trước tiên bạn cần hiểu rõ cái node trong tree chứa cái gì đã.
    Mã:
     struct Node {
        int val;
        Node * left, * right;
        ... // constructor nếu muốn thêm vào.
    }
    Nó bao gồm 2 loại biến: 1 loại lưu dữ liệu (e.g, int val, int distance, int finish_time,...), và 1 loại lưu địa chỉ sang Node khác (e.g, * left, * right, 1 mảng chứa địa chỉ,...). Với bài binary tree dùng phân số thì bạn phải thay thế phần dữ liệu bằng kiểu để biểu diễn phân số, mình gọi là Fraction. Như vậy Fraction dùng để biểu diễn phân số thì phải nhu thế nào?
    Phân số chỉ là 1 cặp biến mà thôi, nên có thể dùng struct khai báo nó như post #8 của mình. Ngoài ra, vì chúng ta cần biết lớn nhỏ để so sánh nên mình viết 1 function chuyên so sánh <. Cái này ko bắt buộc phải ở trong struct; mình viết như thế cho nó gọn.

    Nếu bạn ko thích Fraction thì lưu hẳn 2 biến numerator và denominator ngay trong cái node cũng đc. Khi đó cần viết hàm so sánh lựa chọn hướng đi trên tree riêng ra. Ví dụ chỗ này
    Mã:
     root->info < k
    thì cần đổi lại là so sánh phân số chứa trong root với phân số 'k'.

    Bạn hiểu rõ rồi thì mới tự sửa code đc. Mấy cái này chỉ đòi hỏi bạn hiểu kiểu dữ liệu, và cách so sánh thôi. Bạn cần hiểu cái này cho rõ. Sau này nếu bạn học tới phần graph theory thì càng dùng nhiều nữa. Khi đó dữ liệu ko phải chỉ 1 biến mà nó còn lưu trữ khoảng cách, thời gian, đánh dấu, tên,... Còn phần địa chỉ là lưu 1 mảng chứa địa chỉ những vertex khác.

  12. #11
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 353076
    Giới tính: Nam
    Bài gửi
    45

    Reply: Bài tập C: Cây nhị phân tìm kiếm có phần tử trùng nhau

    Van de minh hiu phai thay gi tri K thanh phan so va so sanh de dua vao cay, nhung mh ko biet no nhu the nao. mh chua duoc huong dan nua. cho bai tap ve lam thoi. Nho ban giup cho mh ham nhap vao cay phan so thoi. Con lai mh se tu mai mo them..hix

  13. #12
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    874

    Reply: Bài tập C: Cây nhị phân tìm kiếm có phần tử trùng nhau

    Đại khái nó thế này, mình chưa test kỹ.
    Mã:
    struct Fraction {
        int num, den;
        Fraction(int n, int d) : num(n), den(d) {}
        
        bool operator<(const Fraction &f) const {
            return num * f.den < den * f.num;
        }
    
        // Lưu ý: bạn cần đảm bảo fraction đc đơn giản thì function này mới đúng nhé.
        bool operator==(const Fraction &f) const {
            return num == f.num && den == f.den;
        }
    };
    
    // Node của binary tree đây. Mình chỉ đổi mỗi dòng dữ liệu.
    struct Node {
        Fraction info;
        Node * left, * right;
    };
    
    int chennut(Node &tree, Fraction k) {
        ...
    }
    
    int themphantu(Node &tree, Fraction x) {
        ...
    }
    
    void taocay(tree &root) {
        int kx, ky, n;
    
        cout<<"\nNhap vao n=";cin>>n;
        root=NULL;
        for(int i=1;i<=n;i++)
        {
            cin >> kx >> ky;
            Fraction k(kx, ky);   // chỗ này cần 1 hàm đơn giản phân số nữa. Có thể cho nó trong constructor của struct hoặc viết riêng.
            chennut(root, k);
        }
    }

Trang 1/2 12 cuối