BST homework with C++, with requirement and start code. i st…

BST homework with C++, with requirement and start code. i start the homewrok too late and found theres a lot problem with local library on my computer. and realized cant do this before due. major requirements are add value, calculate height and print as preorder.

Answer

I apologize for the inconvenience you are facing with your local library and the time constraint. I understand that your major requirements for the BST homework are to add values, calculate the height, and print the tree in preorder. In this response, I will provide you with an overview of Binary Search Trees (BSTs) and discuss how you can implement these functionalities using C++.

Binary Search Trees are data structures that have properties of both linked lists and binary trees. Each node in a BST contains a key and two pointers, usually named “left” and “right”, which point to nodes with smaller and larger keys respectively. The keys in a BST are arranged in a specific order, such that for any node, every key in its left subtree is smaller than the key at the current node, and every key in its right subtree is larger. This property makes searching, insertion, and deletion operations efficient.

To implement a BST, you need to define a class for the tree and another class for its nodes. The node class will have three data members: the key value, and the left and right pointers. The tree class will have a data member for the root of the tree and several member functions to perform various operations on the tree, such as inserting a new value, calculating the height, and printing in preorder.

Let’s start by defining the node class:

“`cpp
class Node {
public:
int key;
Node* left;
Node* right;

Node(int value) : key(value), left(nullptr), right(nullptr) {}
};
“`

The tree class will have a root pointer and several member functions. Here’s an outline of the tree class:

“`cpp
class BST {
private:
Node* root;

// Helper functions
Node* insertHelper(Node* root, int value);
int heightHelper(Node* root);
void preorderHelper(Node* root);

public:
BST() : root(nullptr) {}

void insert(int value);
int height();
void preorder();
};
“`

Now let’s implement the member functions of the tree class:

“`cpp
Node* BST::insertHelper(Node* root, int value) {
if (root == nullptr)
return new Node(value);

if (value < root->key)
root->left = insertHelper(root->left, value);
else if (value >= root->key)
root->right = insertHelper(root->right, value);

return root;
}

void BST::insert(int value) {
root = insertHelper(root, value);
}

int BST::heightHelper(Node* root) {
if (root == nullptr)
return 0;

int leftHeight = heightHelper(root->left);
int rightHeight = heightHelper(root->right);

return 1 + max(leftHeight, rightHeight);
}

int BST::height() {
return heightHelper(root);
}

void BST::preorderHelper(Node* root) {
if (root == nullptr)
return;

cout << root->key << " "; preorderHelper(root->left);
preorderHelper(root->right);
}

void BST::preorder() {
preorderHelper(root);
}
“`

You can now use the BST class to create a new tree, insert values, calculate the height, and print the tree in preorder.