I am getting these errors for my AVL tree C++ code and don\'t understand why, ho
ID: 3910892 • Letter: I
Question
I am getting these errors for my AVL tree C++ code and don't understand why, how do I fix it? Code below it
Code Below:
#include <iostream>
#include <ctime>
#include <stack>
using namespace std;
template <class T>
class BST;
template <class T>
class BSTNode {
BSTNode* right;
BSTNode* left;
BSTNode* parent;
int data;
int height;
public:
BSTNode(T newData = T(), BSTNode* newParent = nullptr, BSTNode* newRight = nullptr, BSTNode* newLeft = nullptr) {
data = newData;
parent = newParent;
right = newRight;
left = newLeft;
}
friend class BST < T > ;
};
template <class T>
class BST {
BSTNode<T>* root;
int countNodes;
BSTNode<T>* recursiveCopy(const BSTNode<T>* rhs);
public:
BST(): root(nullptr) {}
BST(const BST<T>&rhs): root(nullptr) {
return *this;
}
BST operator=(BST<T>&rhs);
void clear() {
if(isEmpty()==false) {
remove(root);
}
}
~BST(){clear();}
void remove(BSTNode<T>* ptr);
bool isEmpty() {
if(root==nullptr) {
return true;
}
else {
return false;
}
}
BSTNode<T>* find(T& data); //find a node
void printInOrder(BSTNode<T>* root); //print the nodes
BSTNode<T>* RrRotate(BSTNode<T>* ptr);
BSTNode<T>* RlRotate(BSTNode<T>* ptr);
BSTNode<T>* LlRotate(BSTNode<T>* ptr);
BSTNode<T>* LrRotate(BSTNode<T>* ptr);
int max(int a, int b); //find the maximum of 2 numbers
int getHeight(BSTNode<T>* ptr); //get the nodes height
BSTNode<T>* insert(int data);
BSTNode<T>* getNode(); //getter for root
BSTNode<T>* setNode(BSTNode<T>* temp); //setter for root
int diff(BSTNode<T> *ptr); //get the L-R differential
BSTNode<T>* balanceTree(BSTNode<T>* ptr); //balance the tree
};
template <class T>
void BST<T>::printInOrder(BSTNode<T>* root) {
while(root->left!=nullptr) {
printInOrder(root->left);
}
cout<<root->data<<endl;
while(root!=nullptr) {
printInOrder(root->right);
}
}
template <class T>
BSTNode<T>* BST<T>::find(T& data) {
BSTNode<T>* ptr;
ptr = root;
while(ptr!=nullptr && ptr->data != data) {
if (data < ptr->data)
ptr = ptr->left;
else {
ptr = ptr->right;
}
}
return ptr;
}
template <class T>
int BST<T>::max(int a, int b) {
if(a>b) {
return a;
}
else {
return b;
}
}
template <class T>
int BST<T>::getHeight(BSTNode<T>* ptr) {
int height = 0;
while(ptr!=nullptr) {
int leftHeight = getHeight(ptr->left);
int rightHeight = getHeight(ptr->right);
int finalHeight = max(leftHeight, rightHeight);
height = finalHeight + 1;
}
return height;
}
template <class T>
int BST<T>::diff(BSTNode<T> *ptr) //find the differential
{
int leftHeight = height(ptr->left);
int rightHeight = height (ptr->right);
int diff= leftHeight - rightHeight;
return diff;
}
template <class T>
BSTNode<T>* BST<T>::LrRotate(BSTNode<T>* ptr) {
BSTNode<T> *temp;
temp = ptr->left;
ptr->left = rr_rotation (temp);
return ll_rotation (ptr);
}
template <class T>
BSTNode<T>* BST<T>::RlRotate(BSTNode<T>* ptr) {
BSTNode<T> *temp;
temp = ptr->right;
ptr->right = rr_rotation (temp);
return ll_rotation (ptr);
}
template <class T>
BSTNode<T>* BST<T>::LlRotate(BSTNode<T>* ptr) {
BSTNode<T> *temp;
temp = ptr->left;
ptr->left = temp->right;
temp->right = ptr;
return temp;
}
template <class T>
BSTNode<T>* BST<T>::RrRotate(BSTNode<T>* ptr) {
BSTNode<T> *temp;
temp = ptr->right;
ptr->right = temp->left;
temp->left = ptr;
return temp;
}
template <class T>
BSTNode<T>* BST<T>::balanceTree(BSTNode<T>* ptr) {
int diff = diff(ptr);
if(diff>=2) {
if(diff(ptr->left)>0) {
ptr = LlRotation(ptr);
}
else {
ptr = LrRotation(ptr);
}
}
else if(diff<=-2) {
if(diff(ptr->right) > 0) {
ptr = RlRotation(ptr);
}
else {
ptr = LrRotation(ptr);
}
}
return ptr;
}
template <class T>
BSTNode<T>* BST<T>::getNode() {
return this->root;
}
template <class T>
BSTNode<T>* insert(int data) {
BSTNode<T>* getNode = getNode();
BSTNode<T>* root = getNode;
BSTNode<T>* ptr;
if (root == nullptr)
{
root= new BSTNode<T>;
root->data = data;
root->left = nullptr;
root->right = nullptr;
return root;
}
else if(data<root->data){
BSTNode<T>* newNode = new BSTNode<T>;
root->left = newNode;
newNode->data = data;
newNode->left = nullptr;
newNode->right = nullptr;
newNode = balanceTree(newNode);
ptr = newNode;
}
else if(data >= root->data) {
BSTNode<T>* newNode = new BSTNode<T>;
root->right = newNode;
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
newNode = balanceTree(newNode);
ptr = newNode;
}
return ptr;
}
template<class T>
void BST<T>::remove(BSTNode<T>* ptr) {
if(root == nullptr) {
return;
}
else if(ptr==root && countNodes==1) {
delete root;
root = nullptr;
countNodes--;
}
else if(ptr->left == nullptr && ptr->right == nullptr) {
BSTNode<T>* parent = ptr->parent;
if(parent->left == ptr) {
parent->left = nullptr;
}
else {
parent->right = nullptr;
}
delete root;
ptr = nullptr;
countNodes--;
}
else if(ptr->left == nullptr && ptr->right != nullptr) {
BSTNode<T>* child = ptr->right;
BSTNode<T>* parent = ptr->parent;
if(parent->left == ptr) {
parent->left = nullptr;
}
else {
parent->right = child;
}
ptr = nullptr;
ptr = child;
}
else if(ptr->right == nullptr && ptr->left != nullptr) {
BSTNode<T>* child = ptr->left;
BSTNode<T>* parent = ptr->parent;
if(parent->right == ptr) {
parent->right = nullptr;
}
else {
parent->left = child;
}
ptr = nullptr;
ptr = child;
}
else if(ptr->left != nullptr && ptr->right != nullptr) {
BSTNode<T>* right = root->right;
BSTNode<T>* temp;
while(right->left !=nullptr) {
temp = right->left = nullptr;
}
ptr->data = temp->data;
remove(temp);
}
}
template <class T>
BSTNode<T>* BST<T>::recursiveCopy(const BSTNode<T>* rhs){
if (rhs == nullptr)
return nullptr;
BSTNode<T>* temp = new BSTNode<T>(rhs->data);
temp->left = recursiveCopy(rhs->left);
temp->right = recursiveCopy(rhs->right);
if (temp->left!=nullptr)
temp->left->parent = temp;
if (temp->right)
temp->right->parent = temp;
return temp;
}
template <class T>
BST<T> BST<T>::operator=(BST<T>& rhs) {
if(this == rhs) {
return *this;
}
clear();
countNodes = rhs->countNodes;
root = recursiveCopy(rhs.root);
return *this;
}
int main()
{
BST<int> t;
srand(time(NULL));
t.insert(20);
t.insert(25);
t.insert(15);
t.insert(10);
t.insert(30);
t.insert(5);
t.insert(35);
t.insert(67);
t.insert(43);
t.insert(21);
t.printInOrder(t.getNode());
}
Undefined symbols for architecture x86_64: "BST::insert(int)", referenced from: _main in main.o ld: symbol(s) not found for architecture x86_64 clang: error: linker command failed with exit code 1 (use -v to see invocation) "BST cint>:insert(int)", referenced from: main in main.o Symbol(s) not found for architecture x86 64 Linker command failed with exit code 1 (use -v to see invocation) Activity Log Complete 7/3/18, 2:02 PM 2 errors, 2 warningsExplanation / Answer
The compilation error was because the function insert() was not declared like
BSTNode<T>* BST<T>::insert(int data);
Now, there are no compilation errors.
---------------------------------------------------------------------------------------------------------
#include <iostream>
#include<cstdlib>
#include <ctime>
#include <stack>
using namespace std;
template <class T>
class BST;
template <class T>
class BSTNode {
public:
BSTNode* right;
BSTNode* left;
BSTNode* parent;
int data;
int height;
BSTNode(T newData = T(), BSTNode* newParent = NULL, BSTNode* newRight = NULL, BSTNode* newLeft = NULL) {
data = newData;
parent = newParent;
right = newRight;
left = newLeft;
}
friend class BST < T > ;
};
template <class T>
class BST {
BSTNode<T>* root;
int countNodes;
BSTNode<T>* recursiveCopy(const BSTNode<T>* rhs);
public:
BST(): root(NULL) {}
BST(const BST<T>&rhs): root(NULL) {
//return *this;
}
BST operator=(BST<T>&rhs);
void clear() {
if(isEmpty()==false) {
remove(root);
}
}
~BST(){clear();}
void remove(BSTNode<T>* ptr);
bool isEmpty() {
if(root==NULL) {
return true;
}
else {
return false;
}
}
BSTNode<T>* find(T& data); //find a node
void printInOrder(BSTNode<T>* root); //print the nodes
BSTNode<T>* RrRotate(BSTNode<T>* ptr);
BSTNode<T>* RlRotate(BSTNode<T>* ptr);
BSTNode<T>* LlRotate(BSTNode<T>* ptr);
BSTNode<T>* LrRotate(BSTNode<T>* ptr);
int max(int a, int b); //find the maximum of 2 numbers
int getHeight(BSTNode<T>* ptr); //get the nodes height
BSTNode<T>* insert(int data);
//BSTNode<T>* insert_util(BSTNode<T>* , int data);
BSTNode<T>* getNode(); //getter for root
BSTNode<T>* setNode(BSTNode<T>* temp); //setter for root
int diff(BSTNode<T> *ptr); //get the L-R differential
BSTNode<T>* balanceTree(BSTNode<T>* ptr); //balance the tree
};
template <class T>
void BST<T>::printInOrder(BSTNode<T>* root) {
while(root->left!=NULL) {
printInOrder(root->left);
}
cout<<root->data<<endl;
while(root!=NULL) {
printInOrder(root->right);
}
}
template <class T>
BSTNode<T>* BST<T>::find(T& data) {
BSTNode<T>* ptr;
ptr = root;
while(ptr!=NULL && ptr->data != data) {
if (data < ptr->data)
ptr = ptr->left;
else {
ptr = ptr->right;
}
}
return ptr;
}
template <class T>
int BST<T>::max(int a, int b) {
if(a>b) {
return a;
}
else {
return b;
}
}
template <class T>
int BST<T>::getHeight(BSTNode<T>* ptr) {
int height = 0;
while(ptr!=NULL) {
int leftHeight = getHeight(ptr->left);
int rightHeight = getHeight(ptr->right);
int finalHeight = max(leftHeight, rightHeight);
height = finalHeight + 1;
}
return height;
}
template <class T>
int BST<T>::diff(BSTNode<T> *ptr) //find the differential
{
int leftHeight = getHeight(ptr->left);
int rightHeight = getHeight (ptr->right);
int diff= leftHeight - rightHeight;
return diff;
}
template <class T>
BSTNode<T>* BST<T>::LrRotate(BSTNode<T>* ptr) {
BSTNode<T> *temp;
temp = ptr->left;
ptr->left = RrRotate (temp);
return LlRotate (ptr);
}
template <class T>
BSTNode<T>* BST<T>::RlRotate(BSTNode<T>* ptr) {
BSTNode<T> *temp;
temp = ptr->right;
ptr->right = RrRotate (temp);
return LlRotate (ptr);
}
template <class T>
BSTNode<T>* BST<T>::LlRotate(BSTNode<T>* ptr) {
BSTNode<T> *temp;
temp = ptr->left;
ptr->left = temp->right;
temp->right = ptr;
return temp;
}
template <class T>
BSTNode<T>* BST<T>::RrRotate(BSTNode<T>* ptr) {
BSTNode<T> *temp;
temp = ptr->right;
ptr->right = temp->left;
temp->left = ptr;
return temp;
}
template <class T>
BSTNode<T>* BST<T>::balanceTree(BSTNode<T>* ptr) {
int _diff = diff(ptr);
if(_diff>=2) {
if(diff(ptr->left)>0) {
ptr = LlRotate(ptr);
}
else {
ptr = LrRotate(ptr);
}
}
else if(_diff<=-2) {
if(diff(ptr->right) > 0) {
ptr = RlRotate(ptr);
}
else {
ptr = LrRotate(ptr);
}
}
return ptr;
}
template <class T>
BSTNode<T>* BST<T>::getNode() {
return this->root;
}
template <class T>
BSTNode<T>* BST<T>::insert(int data) {
//BSTNode<T>* getNode = getNode();
BSTNode<T>* root = getNode();
BSTNode<T>* ptr;
if (root == NULL)
{
root= new BSTNode<T>(data);
root->data = data;
root->left = NULL;
root->right = NULL;
return root;
}
else if(data<root->data){
BSTNode<T>* newNode = new BSTNode<T>;
root->left = newNode;
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
newNode = balanceTree(newNode);
ptr = newNode;
}
else if(data >= root->data) {
BSTNode<T>* newNode = new BSTNode<T>;
root->right = newNode;
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
newNode = balanceTree(newNode);
ptr = newNode;
}
return ptr;
}
template<class T>
void BST<T>::remove(BSTNode<T>* ptr) {
if(root == NULL) {
return;
}
else if(ptr==root && countNodes==1) {
delete root;
root = NULL;
countNodes--;
}
else if(ptr->left == NULL && ptr->right == NULL) {
BSTNode<T>* parent = ptr->parent;
if(parent->left == ptr) {
parent->left = NULL;
}
else {
parent->right = NULL;
}
delete root;
ptr = NULL;
countNodes--;
}
else if(ptr->left == NULL && ptr->right != NULL) {
BSTNode<T>* child = ptr->right;
BSTNode<T>* parent = ptr->parent;
if(parent->left == ptr) {
parent->left = NULL;
}
else {
parent->right = child;
}
ptr = NULL;
ptr = child;
}
else if(ptr->right == NULL && ptr->left != NULL) {
BSTNode<T>* child = ptr->left;
BSTNode<T>* parent = ptr->parent;
if(parent->right == ptr) {
parent->right = NULL;
}
else {
parent->left = child;
}
ptr = NULL;
ptr = child;
}
else if(ptr->left != NULL && ptr->right != NULL) {
BSTNode<T>* right = root->right;
BSTNode<T>* temp;
while(right->left !=NULL) {
temp = right->left = NULL;
}
ptr->data = temp->data;
remove(temp);
}
}
template <class T>
BSTNode<T>* BST<T>::recursiveCopy(const BSTNode<T>* rhs){
if (rhs == NULL)
return NULL;
BSTNode<T>* temp = new BSTNode<T>(rhs->data);
temp->left = recursiveCopy(rhs->left);
temp->right = recursiveCopy(rhs->right);
if (temp->left!=NULL)
temp->left->parent = temp;
if (temp->right)
temp->right->parent = temp;
return temp;
}
template <class T>
BST<T> BST<T>::operator=(BST<T>& rhs) {
if(this == rhs) {
return *this;
}
clear();
countNodes = rhs->countNodes;
root = recursiveCopy(rhs.root);
return *this;
}
int main()
{
BST<int> t;
srand(time(NULL));
t.insert(20);
t.insert(25);
t.insert(15);
t.insert(10);
t.insert(30);
t.insert(5);
t.insert(35);
t.insert(67);
t.insert(43);
t.insert(21);
t.printInOrder(t.getNode());
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.