Cây nhị phân tìm kiếm có phần tử trùng nhau đc không !
co thi duyet cay nhu the nao?
cho mh cây ví dụ (neu co), ai biết giúp vơi`:dapdau2:
co thi duyet cay nhu the nao?
cho mh cây ví dụ (neu co), ai biết giúp vơi`:dapdau2:
Bài tập C: Cây nhị phân tìm kiếm có phần tử trùng nhau
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
Bạn cứ việc theo sát cái convention như post #2 là đc, ko có gì phức tạp cả.
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
Sửa lần cuối:
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;
}
}Bạn cần 1 struct kiểu thế này:cho minh hoi, tao 1 cay nhi phan tim kiem kieu phan so. lam nhu the nao ban
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;
}
};
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);
}
}Trước tiên bạn cần hiểu rõ cái node trong tree chứa cái gì đã.
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
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.
Mã:
struct Node {
[B][COLOR=#ff0000]int val;[/COLOR][/B]
Node * left, * right;
... // constructor nếu muốn thêm và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 < kBạ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.
Đạ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 {
[B]Fraction info;[/B]
Node * left, * right;
};
int chennut(Node &tree, [B]Fraction k[/B]) {
...
}
int themphantu(Node &tree, [B]Fraction x[/B]) {
...
}
void taocay(tree &root) {
int [B]kx, ky[/B], n;
cout<<"\nNhap vao n=";cin>>n;
root=NULL;
for(int i=1;i<=n;i++)
{
[B] cin >> kx >> ky;
Fraction k(kx, ky); [/B]// 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);
}
}
Mã:
#include <iostream.h>
#include <math.h>
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;
}
bool operator==(const Fraction &f) const {
return num == f.num && den == f.den;
}
};
struct Node {
Fraction info;
Node * left, * right;
};
int chennut(Node &root, Fraction 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(Node &root, Fraction 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(Node &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);
chennut(root, k);
}
}
int main()
{
int x,y;
Node root;
taocay(root);
cout<<endl;
return 0;
}Mình thay đổi tí xíu chương trình của bạn:
Mình thấy bạn chỉ cần 2 functions chuyên chèn phần tử thôi (1 input, 1 thực hiện), đâu cần tới 3 functions.
Mã:
#include <iostream>
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;
}
bool operator==(const Fraction &f) const {
return num == f.num && den == f.den;
}
};
struct Node {
Fraction info;
Node * left, *right;
Node(Fraction f) : info(f), left(0), right(0) {}
};
int chennut(Node * &root, Fraction k) {
if (root != NULL)
{
if (root->info == k) return 0;
if (k < root->info) return chennut(root->left, k);
else return chennut(root->right, k);
}
else
{
root = new Node(k);
if (root == NULL) return -1;
return 1;
}
}
int themphantu(Node * &root, Fraction x) {
if (root != NULL)
{
if (x < root->info)
return themphantu(root->left, x);
else
return themphantu(root->right, x);
}
root = new Node(x);
if (root == NULL) return -1;
return 1;
}
void taocay(Node * &root)
{
int kx, ky, n;
std::cout << "\nNhap vao n="; std::cin >> n;
for (int i = 1; i <= n; i++)
{
std::cin >> kx >> ky;
Fraction k(kx, ky);
chennut(root, k);
}
}
int main() {
Node * root = 0;
taocay(root);
std::cout << root->info.num << " " << root->info.den << std::endl;
// In thử 2 node trái phải của root.
if (root->left)
std::cout << root->left->info.num << " " << root->left->info.den << std::endl;
if (root->right)
std::cout << root->right->info.num << " " << root->right->info.den << std::endl;
return 0;
}
Mã:
Fraction tong(Node *root)
{
if(root!=NULL)
return root->info+tong(root->left)+tong(root->right);
}Bạn chỉ cần viết 1 hàm tính tổng phân số ở trong struct Fraction là đc. Mình viết định nghĩa cho dấu + phân số luôn.
Mã:
Fraction operator+(const Fraction &f) const {
return Fraction(num * f.den + den * f.num, den * f.den);
}PS: Thanks bạn, mình với mấy bạn học CNTT còn kém xa lắm, ko "thánh" đc đâu.
