C++... Prepare a class TreeNode<T> • Prepare a class named BinarySearchTree with
ID: 3760424 • Letter: C
Question
C++... Prepare a class TreeNode<T>
• Prepare a class named BinarySearchTree with the following methods
o int treeHeight(TreeNode<T>* root) : Returns the tree height when the root is passed as argument
o TreeNode* insert(TreeNode<T>* root,T val): Inserts a new value to the tree in the appropriate location
o void insertValue(T val) : Calls insert(TreeNode<T>* root,T val) internally
o int getSize() : returns total number of nodes in the tree
o void BreathFirstTravarsal(TreeNode<T>* root): Traverse the tree following the breath first traversal methodology and can print the BFS sequence of node Hint:
o void inOrderTravarsal(TreeNode<T>* root): Traverse the tree in order manner and prints the sequence.
o void preOrderTravarsal(TreeNode<T>* root): Traverse the tree pre order manner and prints the sequence.
o void postOrderTravarsal(TreeNode<T>* root): Traverse the tree in order manner and prints the sequence.
o bool contains(T val): Returns true if an element is found in tree; false otherwise
• Write a main function and perform actions using all the methods defined
--what I have at the moment (need help please):
#include <iostream>
#include <cstddef>
using namespace std;
template <typename T> class TreeNode{
private:
T value;
TreeNode *right;
TreeNode *left;
public:
TreeNode();
TreeNode (T data);
T getValue();
TreeNode* getLeft();
TreeNode* getRight();
void setValue(T data);
void setLeft(TreeNode *leftNode);
void setRight(TreeNode *rightNode);
};
template <typename T> class BinarySearchTree{
private:
TreeNode<T>* rootPtr;
int numOfNodes;
TreeNode<T>* insert(TreeNode<T>* root, T val);
public:
BinarySearchTree(T val);
void insertValue(T val);
int getSize();
void BreadthFirstSearch(TreeNode<T>* root);
void inOrder(TreeNode<T>* root);
void preOrder(TreeNode<T>* root);
void postOrder(TreeNode<T>* root);
int treeHeight(TreeNode<T>* root);
//bool contains(T val);
};
Explanation / Answer
Your program is good. i think you just need to know the logic to impelement other methods.
Below is the Method logic.Kindly understand the Logic and implement into your program and it will work :)
int TreeHeight(TreeNode<T> basenode)
{
if(basenode = = 0)
return -1;
int leftheight,rightheight;
rightheight = TreeHeight( basenode.Rightnode );
leftheight = TreeHeight( basenode.Leftnode );
if(leftheight > rightheight)
return leftheight++;
else
return rightheight++
}
TreeNode* Insert(TreeNode<T> basenode, int data)
{
if (basenode == NULL) return newNode(data);
if (data < basenode->data)
basenode->L = insert(basenode->L, data);
else if (data > basenode->data)
basenode->R = insert(basenode->R, data);
return basenode;
}
int getSize(TreeNode<T> basenode)
{
int count = 1;
if (basenode == NULL)
return 0;
else
{
count += getSize(basenode->l);
count += getSize(basenode->r);
return count;
}
}
void DOBreadthFirstTravseral(struct node* basenode)
{
queue<node*> qu;
if (!basenode) {
return;
}
for (qu.push(basenode); !qu.empty(); qu.pop()) {
const node * const temp_node = qu.front();
if( temp_node->special_blank ){
cout << "\0 " ;
continue;
}else{
cout<<temp_node->data << " ";
}
if (temp_node->L) {
qu.push(temp_node->L);
}else{
}
if (temp_node->R) {
qu.push(temp_node->R);
}else{
}
}
}
void inOrderTraversal(Node* n) {
if ( n ) {
inOrderTraversal(n->L);
cout << n->data << " ";
inOrderTraversal(n->R);
}
}
void preOrderTraversal(Node* basenode) {
if ( basenode ) {
cout << basenode->data << " ";
preOrderTraversal(basenode->L);
preOrderTraversal(basenode->R);
}
}
void postOrderTraversal(Node* n) {
if ( n ) {
postOrderTraversal(n->L);
postOrderTraversal(n->R);
cout << n->data << " ";
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.