HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

BST implementation

Submitted by: @import:stackexchange-codereview··
0
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

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.