I\'m trying to implement a C++ avl tree and its only printing 3 of the Nodes and
ID: 3911646 • Letter: I
Question
I'm trying to implement a C++ avl tree and its only printing 3 of the Nodes and not printing the full nodes and displaying the AVL character. Please help me fix it so it prints the full amount of nodes. Thanks, code is 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);
root = nullptr;
}
}
~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>* ptr); //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
void 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>* ptr) {
if(ptr==nullptr) {
return;
}
printInOrder(ptr->left);
cout<<ptr->data<<endl;
printInOrder(ptr->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 = 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 root;
}
template <class T>
void BST<T>::setNode(BSTNode<T>* temp) {
root = temp;
}
template <class T>
BSTNode<T>* BST<T>::insert(int data) {
BSTNode<T>* root = getNode();
BSTNode<T>* ptr;
if (root == nullptr)
{
root= new BSTNode<T>;
root->data = data;
root->left = nullptr;
root->right = nullptr;
setNode(root);
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 && countNodes>1) {
BSTNode<T>* parent = ptr->parent;
if(parent!=nullptr)
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!=nullptr)
if(parent->left == ptr) {
parent->left = nullptr;
}
else {
parent->right = child;
}
delete root;
ptr = nullptr;
countNodes--;
ptr = child;
}
else if(ptr->right == nullptr && ptr->left != nullptr) {
BSTNode<T>* child = ptr->left;
BSTNode<T>* parent = ptr->parent;
if(parent!=nullptr)
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 = right;
while(right->left !=NULL) {
temp = nullptr;
temp = temp->left;
}
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());
}
Explanation / Answer
#include <iostream>
#include <ctime>
#include <stack>
//modified
#define nullptr NULL
//the problem is with your insertion method...
//you written code...such that it can only insert ...3 nodes to the tree..
//root, left child and right child..
//thats why only 3 nodes are printed
//check your logic for inserting method..
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);
root = nullptr;
}
}
~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>* ptr); //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
void 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>* ptr) {
//modified
/*
if(ptr==nullptr) {
return;
}
*/
if(ptr->left!=NULL)
printInOrder(ptr->left);
cout<<ptr->data<<endl;
if(ptr->right!=NULL)
printInOrder(ptr->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 = 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 root;
}
template <class T>
void BST<T>::setNode(BSTNode<T>* temp) {
root = temp;
}
template <class T>
BSTNode<T>* BST<T>::insert(int data) {
BSTNode<T>* root = getNode();
BSTNode<T>* ptr;
if (root == nullptr)
{
root= new BSTNode<T>;
root->data = data;
root->left = nullptr;
root->right = nullptr;
setNode(root);
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 && countNodes>1) {
BSTNode<T>* parent = ptr->parent;
if(parent!=nullptr)
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!=nullptr)
if(parent->left == ptr) {
parent->left = nullptr;
}
else {
parent->right = child;
}
delete root;
ptr = nullptr;
countNodes--;
ptr = child;
}
else if(ptr->right == nullptr && ptr->left != nullptr) {
BSTNode<T>* child = ptr->left;
BSTNode<T>* parent = ptr->parent;
if(parent!=nullptr)
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 = right;
while(right->left !=NULL) {
temp = nullptr;
temp = temp->left;
}
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());
}