Hi all,
My program is supposed to read data from an input file and position the read data into an AVL tree - in alphabetical order. My output at the end is supposed to show each node in this format...
i.e. (Current, Current->LeftChild (could be NULL), Current->RightChild (could be NULL), Balance (-1, 0, or 1))
Each line represents each node in my AVL tree, the first group of output (when compiled and ran) is the tree listed in Inorder method, the second group is the tree in Preorder method. I tested this program before adding rebalancing features - and was able to get correct output (as though the tree was just an unbalanced tree).
When I added rebalancing functions - LeftLeft(), RightLeft(), etc. and other code to balance the tree that's when things fell apart. I suspect something is wrong in either my rebalancing functions, or my PreorderScan().
If anyone can offer aide I would greatly appreciate it! The first block of code is my .txt file input data - each line representing one node in the AVL tree. The next is obviously my program so far. Thank you!
BTW, I'm aware it would seem my balance variables are set to be backwards - this is so because my professor wants it that way!
Kay
Jon
Tim
Tom
Amy
Ann
Eva
Guy
JanProgram.....
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
struct AVLNode
{
string Name;
int Balance;
AVLNode *LeftChild;
AVLNode *RightChild;
};
AVLNode* AVLCreation(ifstream &);
void InorderTraversal(AVLNode *);
void PreorderTraversal(AVLNode *);
void PreorderScan(AVLNode *, AVLNode *);
void LeftLeft(AVLNode *, AVLNode *);
void RightRight(AVLNode *, AVLNode *);
void LeftRight(AVLNode *, AVLNode *, AVLNode *);
void RightLeft(AVLNode *, AVLNode *, AVLNode *);
int main()
{
ifstream CheckFile; //ifstream checks for file existence
CheckFile.open("a6.txt"); //attempts to open read file, and tests for existence
if(CheckFile.is_open())
cout << "Input file 'a6' exists." << endl << endl;
else
cout << "Input file 'a6' does not exist." << endl << endl;
AVLNode *head;
head = AVLCreation(CheckFile);
InorderTraversal(head);
cout << endl << endl;
PreorderTraversal(head);
system("PAUSE");
return EXIT_SUCCESS;
}
AVLNode *AVLCreation(ifstream &InFile)
{
AVLNode *Root = NULL;
AVLNode *Leaf, *temp, *Scan;
while(!InFile.eof())
{
temp = Root;
Leaf = new AVLNode;
getline(InFile, Leaf->Name);
Leaf->Balance = 0;
Leaf->RightChild = NULL;
Leaf->LeftChild = NULL;
if(Root == NULL)
{
Root = Leaf;
Scan = Root;
}
else
{
while(1)
{
if((Leaf->Name > temp->Name) && (temp->RightChild == NULL))
{
temp->RightChild = Leaf;
temp->Balance--;
break;
}
if((Leaf->Name < temp->Name) && (temp->LeftChild == NULL))
{
temp->LeftChild = Leaf;
temp->Balance++;
break;
}
if((Leaf->Name > temp->Name) && (temp->RightChild != NULL))
{
temp->Balance--;
temp = temp->RightChild;
}
else if((Leaf->Name < temp->Name) && (temp->LeftChild != NULL))
{
temp->Balance++;
temp = temp->LeftChild;
}
}
PreorderScan(Root, Scan);
}
}
return Root;
}
void PreorderScan(AVLNode *Root, AVLNode *Scan)
{
AVLNode *temp1, *temp2;
if(Scan != NULL)
{
if(Scan->Balance >= 2)
{
temp1 = Scan->LeftChild;
if(temp1->Balance == 1)
LeftLeft(Scan, temp1);
else if(temp1->Balance == -1)
{
temp2 = temp1->RightChild;
LeftRight(Scan, temp1, temp2);
}
}
else if(Scan->Balance <= -2)
{
temp1 = Scan->RightChild;
if(temp1->Balance == -1)
RightRight(Scan, temp1);
else if(temp1->Balance == 1)
{
temp2 = temp1->LeftChild;
RightLeft(Scan, temp1, temp2);
}
}
PreorderScan(Root, Scan->LeftChild);
PreorderScan(Root, Scan->RightChild);
}
return;
}
void LeftLeft(AVLNode *Rotate, AVLNode *Pivot)
{
Rotate->LeftChild = Pivot->RightChild;
Pivot->RightChild = Rotate;
Pivot->Balance = 0;
Rotate->Balance = 0;
return;
}
void RightRight(AVLNode *Rotate, AVLNode *Pivot)
{
Rotate->RightChild = Pivot->LeftChild;
Pivot->LeftChild = Rotate;
Pivot->Balance = 0;
Rotate->Balance = 0;
return;
}
void LeftRight(AVLNode *RotateTop, AVLNode *Rotate, AVLNode *Pivot)
{
Rotate->RightChild = Pivot->LeftChild;
Pivot->LeftChild = Rotate;
RotateTop->LeftChild = Pivot;
RotateTop->LeftChild = Pivot->RightChild;
Pivot->RightChild = RotateTop;
Pivot->Balance = 0;
Rotate->Balance = 0;
RotateTop->Balance = 0;
return;
}
void RightLeft(AVLNode *RotateTop, AVLNode *Rotate, AVLNode *Pivot)
{
Rotate->LeftChild = Pivot->RightChild;
Pivot->RightChild = Rotate;
RotateTop->RightChild = Pivot;
RotateTop->RightChild = Pivot->LeftChild;
Pivot->LeftChild = RotateTop;
Pivot->Balance = 0;
Rotate->Balance = 0;
RotateTop->Balance = 0;
return;
}
void InorderTraversal(AVLNode *Root)
{
AVLNode *temp;
if(Root != NULL)
{
InorderTraversal(Root->LeftChild); // print left subtree
cout << "(" << Root->Name << ", "; // print this node
if(Root->LeftChild == NULL)
cout << "NULL, ";
else
{
temp = Root->LeftChild;
cout << temp->Name << ", ";
}
if(Root->RightChild == NULL)
cout << "NULL, ";
else
{
temp = Root->RightChild;
cout << temp->Name << ", ";
}
cout << Root->Balance << ")" << endl;
InorderTraversal(Root->RightChild); // print right subtree
}
return;
}
void PreorderTraversal(AVLNode *Root)
{
AVLNode *temp;
if(Root != NULL)
{
cout << "(" << Root->Name << ", "; // print this node
if(Root->LeftChild == NULL)
cout << "NULL, ";
else
{
temp = Root->LeftChild;
cout << temp->Name << ", ";
}
if(Root->RightChild == NULL)
cout << "NULL, ";
else
{
temp = Root->RightChild;
cout << temp->Name << ", ";
}
cout << Root->Balance << ")" << endl;
PreorderTraversal(Root->LeftChild); // print left subtree
PreorderTraversal(Root->RightChild); // print right subtree
}
return;
}
