patterncppMinor
BST implementation
Viewed 0 times
implementationbststackoverflow
Problem
My implementation of BST. Critique will be appreciated!
```
#include
template
class Node {
template
friend class BST;
template
friend void clear(Node *root);
template
friend bool search(const Node *root, const X x);
template
friend Node to_add(Node root, const X x);
template
friend std::ostream& preorder(std::ostream& ss, Node *root);
template
friend std::ostream& postorder(std::ostream& ss, Node *root);
T data;
Node *left;
Node *right;
Node(): data(), left(nullptr), right(nullptr) { }
Node(T dt): data(dt), left(nullptr), right(nullptr) { }
T get() const { return data; }
};
template
void clear(Node *root);
template
class BST {
template
friend void clear(Node* root);
template
friend std::ostream& bst_preorder(std::ostream& ss, BST& tree);
template
friend std::ostream& bst_postorder(std::ostream& ss, BST& tree);
Node *root;
public:
BST(): root(nullptr) { }
BST(Node *n): root(n) { }
~BST() {
clear(root);
}
bool in_tree(T x) const;
BST& insert(T x);
};
template
void clear(Node* root) {
if (root) {
if (root->left) {
clear(root->left);
}
if (root->right) {
clear(root->right);
}
delete root;
}
}
template
bool search(const Node* root, const T x) {
if (root) {
if (x == root->data)
return true;
else if (x data)
return search(root->left, x);
else
return search(root->right, x);
}
else
return false;
}
template
bool BST::in_tree(const T x) const {
return search(root, x);
}
template
Node to_add(Node root, const T x) {
if (root->left == nullptr && root->data > x)
return root;
else if (root->right == nullptr && root->data data > x)
return to_add(root->left, x);
else if (root->data right, x);
else
return nullptr;
}
template
B
```
#include
template
class Node {
template
friend class BST;
template
friend void clear(Node *root);
template
friend bool search(const Node *root, const X x);
template
friend Node to_add(Node root, const X x);
template
friend std::ostream& preorder(std::ostream& ss, Node *root);
template
friend std::ostream& postorder(std::ostream& ss, Node *root);
T data;
Node *left;
Node *right;
Node(): data(), left(nullptr), right(nullptr) { }
Node(T dt): data(dt), left(nullptr), right(nullptr) { }
T get() const { return data; }
};
template
void clear(Node *root);
template
class BST {
template
friend void clear(Node* root);
template
friend std::ostream& bst_preorder(std::ostream& ss, BST& tree);
template
friend std::ostream& bst_postorder(std::ostream& ss, BST& tree);
Node *root;
public:
BST(): root(nullptr) { }
BST(Node *n): root(n) { }
~BST() {
clear(root);
}
bool in_tree(T x) const;
BST& insert(T x);
};
template
void clear(Node* root) {
if (root) {
if (root->left) {
clear(root->left);
}
if (root->right) {
clear(root->right);
}
delete root;
}
}
template
bool search(const Node* root, const T x) {
if (root) {
if (x == root->data)
return true;
else if (x data)
return search(root->left, x);
else
return search(root->right, x);
}
else
return false;
}
template
bool BST::in_tree(const T x) const {
return search(root, x);
}
template
Node to_add(Node root, const T x) {
if (root->left == nullptr && root->data > x)
return root;
else if (root->right == nullptr && root->data data > x)
return to_add(root->left, x);
else if (root->data right, x);
else
return nullptr;
}
template
B
Solution
The main thing I can think of, is that anyone using the BST class, shouldn't have to know what a Node is. The user should just be adding a value, searching for a value, etc.in the BST class. With this in mind, I would suggest keeping the Node class a private member of BST, and all the functions, add,search, etc. should be members of BST.
Context
StackExchange Code Review Q#155818, answer score: 6
Revisions (0)
No revisions yet.