Can someone PLEASE FIX THIS C++ code THE code below was written on this #include
ID: 3697352 • Letter: C
Question
Can someone PLEASE FIX THIS C++ code
THE code below was written on this
#include <iostream>
#include <string>
#include <fstream>
#include <iomanip>
using namespace std;
static bool balanceRequired = false;
static int absoluteCounter = 1;
struct treePtr
{
struct tree *address;
};
struct tree
{
char value[15] = {};
char;
struct treePtr *vertex;
struct tree *parent = NULL;
struct tree *leftChild = NULL;
struct tree *rightChild = NULL;
int height = 0;
int factor = 0;
int multiplicity = 0;
};
void test(struct tree *node);
char firstAlpha(char input[], char current[], int height);
int operation(struct treePtr *nodePtr);
int balanceFactor(int left, int right);
struct tree *balancer(struct tree *root, int mainTree, int subTree);
void traverse(struct tree *node, bool first);
struct tree *subTreeFinder(struct tree *root);
bool balanceSetup(struct tree *node);
void fileOutput(struct tree *node);
void traverseOutput(struct tree *node);
int main()
{
ifstream inputFile;
struct tree *treeNode;
struct tree *parent;
struct treePtr *prevPtr;
struct treePtr *nodePtr;
struct treePtr *vertexPtr;
char input[15] = {};
char direction = ' ';
inputFile.open("trees");
vertexPtr = new struct treePtr;
nodePtr = new struct treePtr;
prevPtr = new struct treePtr;
cout << " ------------------- " << absoluteCounter << " -------------------" << endl;//error
inputFile >> input;
cout << input << endl << endl;
parent = new struct tree;
parent->vertex = vertexPtr;
treeNode = new struct tree;
treeNode->vertex = vertexPtr;
int x = 0;
while (input[x])
{
treeNode->value[x] = input[x];
x++;
}
vertexPtr->address = treeNode;
vertexPtr->address->parent = parent;
inputFile >> input;
while (inputFile)//file
{
cout << " VERTEX: " << vertexPtr->address->value << endl << endl; // test
traverseOutput(vertexPtr->address); // test
absoluteCounter++; cout << " ------------------- " << absoluteCounter << " -------------------" << endl;//error checker
cout << input << endl; // test statements
// standard setup--------------------------------------------------------------------------------
nodePtr->address = vertexPtr->address;
while (nodePtr->address)
{
prevPtr->address = nodePtr->address;
direction = firstAlpha(input, nodePtr->address->value, nodePtr->address->height);
if (direction == 'l') nodePtr->address = nodePtr->address->leftChild;
else if (direction == 'r') nodePtr->address = nodePtr->address->rightChild;
else //extra credit
{
nodePtr->address->multiplicity++;
nodePtr->address = NULL;
}
}
if (direction != 's')
{
treeNode = new struct tree;
treeNode->vertex = vertexPtr;
int x = 0;
while (input[x])
{
treeNode->value[x] = input[x];
x++;
}
treeNode->onSide = direction;
treeNode->parent = prevPtr->address;
if (direction == 'l') prevPtr->address->leftChild = treeNode;
if (direction == 'r') prevPtr->address->rightChild = treeNode;
//-----------------SETUP (set heights, check balancefactors and balance if required)-------------
traverse(vertexPtr->address, true);
}
inputFile >> input;
}
traverseOutput(vertexPtr->address);
system("PAUSE");
return 0;
}
char firstAlpha(char input[], char current[], int height)
{
int i = 0;
do
{
if (input[i] < current[i]) return 'l'; //left node
else if (input[i] > current[i]) return 'r'; //right node
else
{
if (i > 14) return 's'; //same vaule
i++;
}
} while (input[i] && current[i]);
if (!input[i] && !current[i]) return 's'; //same vaule
if (!input[i] && current[i]) return 'l'; //left node
if (input[i] && !current[i]) return 'r'; //right node
}
int operation(struct treePtr *nodePtr)
{
if ((nodePtr->address->leftChild) && !(nodePtr->address->rightChild))
{
return balanceFactor(nodePtr->address->leftChild->height, -1);
}
else if (!(nodePtr->address->leftChild) && (nodePtr->address->rightChild))
{
return balanceFactor(-1, nodePtr->address->rightChild->height);
}
else
{
return balanceFactor(nodePtr->address->leftChild->height, nodePtr->address->rightChild->height);
}
}
int balanceFactor(int left, int right)
{
return left - right;
}
struct tree *balancer(struct tree *root, int mainTree, int subTree)
{
if (mainTree < 0) //right - right shift
{
if (subTree > 0) // right - left shift (makes right-left >>right-right)
{
root->rightChild = balancer(root->rightChild, 1, 1);
root->rightChild->onSide = 'r';
root->rightChild->parent = root;
}
//left rotation
root->parent = root->rightChild;
root->onSide = 'l';
root->rightChild = root->parent->leftChild;
root->parent->leftChild = root;
if (root->rightChild)
{
root->rightChild->parent = root;
root->rightChild->onSide = 'r';
}
}
else //left - left shift
{
if (subTree < 0) //left - right shift (makes left - right >> left - left)
{
root->leftChild = balancer(root->leftChild, -1, -1);
root->leftChild->onSide = 'l';
root->leftChild->parent = root;
}
//right rotation
root->parent = root->leftChild;
root->onSide = 'r';
root->leftChild = root->parent->rightChild;
root->parent->rightChild = root;
if (root->leftChild)
{
root->leftChild->parent = root;
root->leftChild->onSide = 'l';
}
}
return root->parent; //new vertex is always the root's parent
}
void traverse(struct tree *node, bool first)
{
/*
when this is called initially pass in
true for first
*/
struct treePtr *tracker;
tracker = new struct treePtr;
int balFac = 0;
int subTree = 0;
if (node)
{
traverse(node->leftChild, false);
if (balanceRequired && !first) return;
traverse(node->rightChild, false);
if (balanceRequired && !first) return;
if (balanceRequired && first)
{
balanceRequired = false;
traverse(node->vertex->address, true);
}
else
{
if (!(node->leftChild) && !(node->rightChild))
{
node->height = 0;
node->factor = 0;
}
else
{
tracker->address = node;
balFac = operation(tracker);
if ((balFac == -2) || (balFac == 2))
{
if (absoluteCounter == 8)
{
cout << "";
}
cout << "Balance on: " << node->value << endl;
balanceRequired = balanceSetup(node);
if (!first) return;
}
else
{
if ((node->leftChild) && (node->rightChild))
{
if (node->leftChild->height == node->rightChild->height) node->height = node->leftChild->height + 1;
else node->height = subTreeFinder(node)->height + 1;
}
else node->height = subTreeFinder(node)->height + 1;
node->factor = balFac;
}
}
}
}
if (balanceRequired && first)
{
balanceRequired = false;
traverse(node->vertex->address, true);
}
return;
}
struct tree *subTreeFinder(struct tree *root)
{
if (!root->leftChild) return root->rightChild;
else if (!root->rightChild) return root->leftChild;
else
{
int left;
int right;
left = root->leftChild->height;
right = root->rightChild->height;
if (left > right) return root->leftChild;
else if (left < right) return root->rightChild;
else
{
cout << "ERROR 3!!!!! the node value [" << root->value << "] was passed with equal sub heights" << endl;
system("pause");
}
}
}
bool balanceSetup(struct tree *node)
{
struct treePtr *vertex;
vertex = new struct treePtr;
struct treePtr *tracker;
tracker = new struct treePtr;
struct treePtr *subTracker;
subTracker = new struct treePtr;
struct treePtr *prevTracker;
prevTracker = new struct treePtr;
vertex = node->vertex;
tracker->address = node;
subTracker->address = subTreeFinder(node);
//run balancer
if (node == vertex->address) //check if vertex is invovled
{
vertex->address = balancer(node, operation(tracker), operation(subTracker));
vertex->address->parent = NULL;
}
else
{
prevTracker->address = node->parent;
if (node->onSide == 'l')
{
prevTracker->address->leftChild = balancer(node, operation(tracker), operation(subTracker));
prevTracker->address->leftChild->onSide = 'l';
prevTracker->address->leftChild->parent = prevTracker->address;
}
else if (node->onSide == 'r')
{
prevTracker->address->rightChild = balancer(node, operation(tracker), operation(subTracker));
prevTracker->address->rightChild->onSide = 'r';
prevTracker->address->rightChild->parent = prevTracker->address;
}
else cout << "ERROR 5 node actually has no parent check vertex parameter!!!! "; //error check
}
return true;
}
void test(struct tree *node)
{
if (node)
{
struct treePtr *test;
test = new struct treePtr;
test->address = node;
cout << "current node " << test->address->value << " has a balance Factor is ";
if (!(node->leftChild) && !(node->rightChild)) cout << "0 ";
else cout << operation(test) << endl;
if (node->leftChild) cout << "Left child: [ " << test->address->leftChild->value << " ] ";
else cout << "Left child: [ N/A ] ";
if (node->rightChild) cout << " Right child: [ " << test->address->rightChild->value << " ] ";
else cout << " Right child: [ N/A ] ";
}
return;
}
void traverseOutput(struct tree *node)
{
if (node)
{
traverseOutput(node->leftChild);
fileOutput(node);
traverseOutput(node->rightChild);
}
return;
}
void fileOutput(struct tree *node)
{
if (node)
{
struct treePtr *test;
test = new struct treePtr;
test->address = node;
//cout << "NODE " << "LEFT " << "RIGHT " << "H " << "BAL ";
cout << test->address->value << " ";
if (test->address->parent->value) cout << "<" << test->address->parent->value << "> ";
else cout << "<NULL> ";
cout << test->address->onSide << " ";
if (node->leftChild) cout << test->address->leftChild->value << " ";
else cout << "[NULL] ";
if (node->rightChild) cout << test->address->rightChild->value << " ";
else cout << "[NULL] ";
cout << test->address->height << " ";
cout << test->address->factor << " ";
}
return;
}
Explanation / Answer
Lets look at the code in Java for achieving the above logic: