Chào mọi người, cho mình hỏi ai đã từng làm nạp chồng toán tử [] trong cây nhị phân tìm kiếm chưa ạ? Chỉ cho mình với. Ví dụ:
A 5 6 8 2 3 4 (key)
0.1 4.5 2.3 5.2 1.8 (data)
Bây giờ mình cần:
int x;
nếu x = key thì in ra A[x] = data;
còn x != key thì thông báo lỗi
Phần code của mình như sau:
class Tree {
private:
struct node {
int key;
float data;
node* left;
node* right;
};
node* root;
BST bạn tạo key làm gì nhỉ, nó làm tốn thêm bộ nhớ mà không có lợi ích gì.
ko có key làm sao truy cập theo key được :V :V
khai báo hàm vậy thôi :V
float operator[](int key) const;
Vì BST không có tính truy cập ngẫu nhiên nên overload [] không hợp lí lắm, nếu thêm key vào giống như bạn kia thì em thấy có lẽ hashtable sẽ hợp hơn
container nào mà ko truy cập ngẫu nhiên được, có nên hay ko thôi =] Ví dụ linked list muốn truy cập ngẫu nhiên cũng ok nhưng mà nó O(n) =]
cây này ko cân bằng nên có lẽ ko nên, trường hợp tệ nhất nó như liniked list O(n). Nhưng đề yêu cầu thì viết thôi :V
cây có cân bằng thì truy cập ngẫu nhiên chỉ tốn O(logn) thôi, cũng được mà :V
Ý em là vậy đó, không nên thì không làm luôn
đề yêu cầu sao em ko làm được :V Viết cho hiểu cách nó tìm kiếm node trong cây nhị phân thế nào chứ xài thì xài thư viện chuẩn hay thư viện người khác viết cho chắc :V
Có lẽ là vậy cũng nên được chứ nhỉ :v
Ví dụ: bảng tần suất 
viết chắc cũng dễ mà =]
float operator[](int key) const {
Node* node = findNodeWithKey(key, root);
if (node) return node->data;
throw ...;
}
Node* findNodeWithKey(int key, Node* node) {
if (!node || node->key == key) return node;
return findNodeWithKey(key, key < node->key ? node->left : node->right);
}
mình cảm ơn, để mình thử code xem sao
bạn xem chương trình này giúp mình với, hàm main giờ viết sao?
#include<iostream>
using namespace std;
class Tree {
private:
struct node {
int key;
float data;
node* left;
node* right;
};
node* root;
node* makeEmpty(node* t);
node* insertprivate(int x, float y, node* t);
node* findMin(node* t);
node* removeprivate(int x, float y, node* t);
void inorderprivate(node* t);
node* findprivate(node* t, int x);
int countprivate(node* t);
node* findNodeWithKey(int index, node* t);
public:
Tree();
~Tree();
void insert(int x, float y);
void remove(int x, float y);
void inorder();
void find(int x);
int count();
float& operator[](int index);
};
Tree::Tree() {
root = NULL;
}
Tree::~Tree() {
root = makeEmpty(root);
}
Tree::node* Tree::makeEmpty(node* t) {
if (t == NULL)
return NULL;
{
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
}
return NULL;
}
void Tree::insert(int x, float y) {
root = insertprivate(x, y, root);
}
Tree::node* Tree::insertprivate(int x, float y, node* t)
{
if (t == NULL)
{
t = new node;
t->key = x;
t->data = y;
t->left = t->right = NULL;
}
else if (x < t->key)
t->left = insertprivate(x, y, t->left);
else if (x > t->data)
t->right = insertprivate(x, y, t->right);
return t;
}
void Tree::remove(int x, float y) {
root = removeprivate(x, y, root);
}
Tree::node* Tree::removeprivate(int x, float y, node* t) {
node* temp;
if (t == NULL)
return NULL;
else if (x < t->key)
t->left = removeprivate(x, y, t->left);
else if (x > t->key)
t->right = removeprivate(x, y, t->right);
else if (t->left && t->right)
{
temp = findMin(t->right);
t->key = temp->key;
t->right = removeprivate(t->key, t->data, t->right);
}
else
{
temp = t;
if (t->left == NULL)
t = t->right;
else if (t->right == NULL)
t = t->left;
delete temp;
}
return t;
}
void Tree::inorder() {
inorderprivate(root);
cout << endl;
}
void Tree::inorderprivate(node* t) {
if (t == NULL)
return;
inorderprivate(t->left);
cout << t->key << "( " << t->data << " )\t";
inorderprivate(t->right);
}
void Tree::find(int x) {
root = findprivate(root, x);
}
Tree::node* Tree::findprivate(node* t, int x) {
if (t == NULL)
return NULL;
else if (x < t->data)
return findprivate(t->left, x);
else if (x > t->data)
return findprivate(t->right, x);
else
return t;
}
Tree::node* Tree::findMin(node* t)
{
if (t == NULL)
return NULL;
else if (t->left == NULL)
return t;
else
return findMin(t->left);
}
int Tree::countprivate(node* t)
{
if (t == NULL)
return 0;
else
return (countprivate(t->right) + countprivate(t->left)) + 1;
}
int Tree::count()
{
cout << "Count = " << countprivate(root);
cout << endl;
return 0;
}
float& Tree::operator[](int index) {
node* t = findNodeWithKey(index, root);
if (t) return t->data;
}
Tree::node* Tree::findNodeWithKey(int index, node* t) {
if (!t || t->key == index) return t;
return findNodeWithKey(index, index < t->key ? t->left : t->right);
}
int main() {
Tree* bst = new Tree();
bst->insert(20, 0.1);
bst->insert(25, 0.2);
bst->insert(10, 0.5);
bst->inorder();
bst->count();
bst->remove(20, 0.1);
bst->inorder();
bst->count();
//Tree A;
//cout << "A[key] = " << ;
return 0;
}viết hàm main nghĩa là sao :V
thì cái phần chỉ số mảng đó, viết dưới hàm main ra sao vậy bạn
bst[25] gì thôi :V
code của bạn ko có ktra xem key có trong tree hay ko, nếu ko có thì return cái gì? :V Sao ko throw ngoại lệ? Sao ko đọc warning trong toán tử []?
// trong operator[]
if (...) return t->data;
else throw std::runtime_error("Invalid key");
// trong main
int key;
std::cin >> key;
try {
std::cout << "A[" << key << "] = " << A[key] << "\n";
} catch (const std::exception& e) {
std::cerr << e.what() << "\n";
}
mình đang học đến phần xử lý ngoại lệ, trong bài làm yêu cầu phải xử lý ít nhất 4 ngoại lệ, mà mình muốn viết cho chương trình chạy được trước đã
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?