My assignment is separated into a header file (.h), implementation file (.cpp) and main file (*.cpp).
The program is supposed to do the following:
Build an AVL tree and display it on the screen at any time during the insertion. After the tree was completely built and balanced, perform: Inorder traversal, Preorder traversal, and Postorder traversal.
My code is as follows:
AVL.h (header file)
#ifndef AVL_H_
#define AVL_H_
struct node
{
int data;
struct node *left;
struct node *right;
}*root;
class AVL
{
public:
int height(node *);
int difference(node *);
node *rotateRight(node *);
node *rotateLeft(node *);
node *rotateLR(node *);
node *rotateRL(node *);
node *balance(node *);
node *insert(node *, int);
void displayAVL(node *, int);
void inOrder(node *);
void preOrder(node *);
void postOrder(node *);
AVL(){root = NULL;}
};
#endif
AVL.cpp (implementation file)
#include <iostream>
#include<cstdio>
#include<sstream>
#include<algorithm>
#include "AVL.h"
#define pow2(n)(1<<(n))
using namespace std;
int AVL::height(node *hold)
{
int ht;
if(hold != NULL)
{
int leftHt = height(hold->left);
int rightHt = height(hold->right);
int max_Ht = max(leftHt, rightHt);
ht = max_Ht + 1;
}
return ht;
}
int AVL::difference(node *hold)
{
int leftHt = height(hold->left);
int rightHt = height(hold->right);
int b_factor = leftHt - rightHt;
return b_factor;
}
node *AVL::rotateRight(node *parent)
{
node *hold;
hold = parent->right;
parent->right = hold->left;
hold->left = parent;
return hold;
}
node *AVL::rotateLeft(node *parent)
{
node *hold;
hold = parent->left;
parent->left = hold->right;
hold->right = parent;
return hold;
}
node *AVL::rotateLR(node *parent)
{
node *hold;
hold = parent->left;
parent->left = rotateRight(hold);
return rotateLeft(parent);
}
node *AVL::rotateRL(node *parent)
{
node *hold;
hold = parent->right;
parent->left = rotateLeft(hold);
return rotateRight(parent);
}
node *AVL::balance(node *hold)
{
int b_factor = difference(hold);
if(b_factor > 1)
{
if(difference(hold->left) > 0)
hold = rotateLeft(hold);
else
hold = rotateLR(hold);
}
else if(b_factor < -1)
{
if(difference(hold->right) > 0)
hold = rotateRL(hold);
else
hold = rotateRight(hold);
}
return hold;
}
node *AVL::insert(node *root, int value)
{
if(root == NULL)
{
root = new node;
root->data = value;
root->left = NULL;
root->right = NULL;
return root;
}
else if(value < root->data)
{
root->left = insert(root->left, value);
root = balance(root);
}
else if(value >= root->data)
{
root->right = insert(root->right, value);
root = balance(root);
}
return root;
}
void AVL::displayAVL(node *pointer, int level)
{
if(pointer != NULL)
{
displayAVL(pointer->right, level + 1);
cout<< "\n";
if(pointer == root)
cout<<"Root -> ";
for(int i = 0; i < level&&pointer != root; i++)
{
cout<<" ";
}
cout<< pointer->data;
displayAVL(pointer->left, level + 1);
}
}
void AVL::inOrder(node *tree)
{
if(tree == NULL)
return;
inOrder(tree->left);
cout<<tree->data<<" ";
inOrder(tree->right);
}
void AVL::preOrder(node *tree)
{
if(tree == NULL)
return;
cout<<tree->data<<" ";
preOrder(tree->left);
preOrder(tree->right);
}
void AVL::postOrder(node *tree)
{
if(tree == NULL)
return;
postOrder(tree->left);
postOrder(tree->right);
cout<<tree->data<<" ";
}
Exercise_4_main.cpp (main file)
#include <iostream>
#include "AVL.h"
using namespace std;
int main()
{
int choice;
int value;
AVL avlTree;
cout<< "-----------------------\n";
cout<< "AVL Tree Implementation\n";
cout<< "-----------------------\n";
cout<< "1. Insert an element into the tree\n";
cout<< "2. Display Balanced AVL Tree\n";
cout<< "3. InOrder tranversal\n";
cout<< "4. PreOrder tranversal\n";
cout<< "5. PostOrder tranversal\n";
cout<< "6. Exit";
cout<< "Enter your choice: ";
cin>> choice;
while(choice != 6)
{
if(choice == 1)
{
cout<<"Enter value to be inserted: ";
cin>> value;
root = avlTree.insert(root, value);
}
else if(choice == 2)
{
if(root == NULL)
{
cout<< "Tree is Empty\n";
}
cout<< "Balanced AVL Tree:\n";
avlTree.displayAVL(root, 1);
}
else if(choice == 3)
{
cout<< "Inorder Tranversal:\n";
avlTree.inOrder(root);
cout<<"\n";
}
else if(choice == 4)
{
cout<< "Preorder Tranversal:\n";
avlTree.preOrder(root);
cout<<"\n";
}
else
cout<< "Postorder Tranversal:\n";
avlTree.postOrder(root);
cout<< "\n";
cout<< "-----------------------\n";
cout<< "AVL Tree Implementation\n";
cout<< "-----------------------\n";
cout<< "1. Insert an element into the tree\n";
cout<< "2. Display Balanced AVL Tree\n";
cout<< "3. InOrder tranversal\n";
cout<< "4. PreOrder tranversal\n";
cout<< "5. PostOrder tranversal\n";
cout<< "6. Exit";
cout<< "Enter your choice: ";
cin>> choice;
}
system("pause");
return 0;
}
I compiled my code and I am getting the error LNK2005: "struct node * root" (?root@@3PAUnode@@A) already defined in AVL.obj. Can anyone help me figure out how to fix this problem?