I am getting an error in my AVL tree. The output is very close the correct answer but I can't seem to figure out what is going on. I've checked all the traversal algorithms within the program and they seem to make sense.
The program itself reads 2 text files. One file has all the integers for the AVL tree and the other file gives you commands for the program to print by preorder, postorder and inorder traversals of the tree.
In this example the input is:
3 10 15 23 65 85 235 457 51 9 2 1 235 457 51 9 2 1
And the command text:
Preorder Traversal
Postorder Traversal
Output:
23 1 2 3 9 10 15 51 65 85 235 457
1 2 3 9 10 15 51 65 85 235 457 23
My output is:
23 3 2 1 10 9 15 85 65 51 235 457
1 2 9 15 10 3 51 65 457 235 85 23
It is slightly off which leads me to believe maybe the rotation is wrong or perhaps something within the print function I'm not seeing? Here is my current code trimmed down a bit for readability:
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <ctime>
using namespace std;
typedef struct node {
int data = -1;
int height = 1;
node* left = nullptr;
node* right = nullptr;
} node;
class Tree {
private:
node* root = nullptr;
vector<string> outputStorage;
vector<string> originalArray;
vector<string> cleanArray;
string level = "";
string container = "";
bool flag = false;
public:
// ###################### Read/Command/Write ######################
void readFile(string filePath) {
ifstream fileInput;
string line;
fileInput.open(filePath);
if (!fileInput.is_open())
cout << "input file not read!" << endl;
while (fileInput >> line) {
originalArray.push_back(line);
}
populateTree(originalArray);
outputStorage.clear();
fileInput.close();
}
void commandLine(string commandPath) {
ifstream inCommand;
string line;
inCommand.open(commandPath);
if (!inCommand.is_open())
cout << "command file not read!" << endl;
while (!inCommand.eof()) {
getline(inCommand, line);
if (line == "Preorder Traversal") {
preorderTraversal(root);
outputStorage.push_back(container);
cout << "container (preorder): " << container << endl;
container.clear();
}
else if (line == "Inorder Traversal") {
inorderTraversal(root);
outputStorage.push_back(container);
cout << "container (inorder): " << container << endl;
container.clear();
}
else if (line == "Postorder Traversal") {
postorderTraversal(root);
outputStorage.push_back(container);
cout << "container (post): " << container << endl;
container.clear();
}
else {
string stringTemp = line;
if (stringTemp.substr(0, 5) == "Level") {
level = stringTemp.substr(6, stringTemp.length() - 6);
nodesOnLevel(root, stoi(level), 1);
outputStorage.push_back(container);
container.clear();
}
}
}
inCommand.close();
}
void outFile(string outFilePath) {
ofstream output;
output.open(outFilePath);
for (int i = 0; i < outputStorage.size(); i++) {
output << outputStorage[i] << endl;
}
output.close();
}
// ###################### TREE FUNCTIONS ######################
node* newNode(int num) {
node* temp = new node;
temp->data = num;
temp->left = temp->right = nullptr;
temp->height = 1;
return temp;
}
node* insert(int x, node* t) {
if (t == nullptr)
{
node* temp = new node;
temp->data = x;
temp->left = temp->right = nullptr;
t = temp;
if (root == nullptr)
root = temp;
}
else if (x < t->data)
t->left = insert(x, t->left);
else if (x > t->data)
t->right = insert(x, t->right);
else
return t;
if (getBalance(t) > 1 && x < t->left->data)
return singleRightRotate(t);
if (getBalance(t) < -1 && x > t->right->data)
return singleLeftRotate(t);
if (getBalance(t) > 1 && x > t->left->data)
return doubleLeftRotate(t);
if (getBalance(t) < -1 && x < t->right->data)
return doubleRightRotate(t);
t->height = max(height(t->left), height(t->right)) + 1;
return t;
}
void insertFromArray(int x) {
root = insert(x, root);
}
void populateTree(vector<string> t) {
for (int i = 0; i < t.size(); i++) {
insertFromArray(stoi(t[i]));
}
}
// ###################### UTILITY FUNCTIONS ######################
void showTree(node* root) {
if (root != nullptr) {
cout << root->data << " ";
showTree(root->left);
showTree(root->right);
}
}
node* singleRightRotate(node*& t)
{
node* newroot = t->left;
t->left = newroot->right;
newroot->right = t;
t->height = max(height(t->left), height(t->right)) + 1;
return newroot;
}
node* singleLeftRotate(node*& t) {
node* newroot = t->right;
t->right = newroot->left;
newroot->left = t;
t->height = max(height(t->left), height(t->right)) + 1;
return newroot;
}
node* doubleLeftRotate(node*& t) {
t->left = singleLeftRotate(t->left);
return singleRightRotate(t);
}
node* doubleRightRotate(node*& t) {
t->right = singleRightRotate(t->right);
return singleLeftRotate(t);
}
node* findMin(node* t) {
if (t->left == nullptr)
return t;
return findMin(t->left);
}
node* findMax(node* t) {
if (t->right == nullptr)
return t;
return findMax(t->right);
}
int height(node* t) {
if (t == nullptr)
return 0;
return t->height;
}
int getBalance(node * t) {
if (t == nullptr)
return 0;
return height(t->left) - height(t->right);
}
void nodesOnLevel(node* n, int level, int currentLevel) {
if (n != NULL) {
if (level == currentLevel) {
container += to_string(n->data) + " ";
return;
}
else {
nodesOnLevel(n->left, level, currentLevel + 1);
nodesOnLevel(n->right, level, currentLevel + 1);
return;
}
}
else {
if (flag == false) {
container += "empty";
flag = true;
}
return;
}
}
// ###################### COMMAND FUNCTIONS ######################
void inorderTraversal(node* root) {
if (root != nullptr) {
inorderTraversal(root->left);
container += to_string(root->data) + " ";
inorderTraversal(root->right);
}
}
void preorderTraversal(node* root) {
if (root != nullptr) {
container += to_string(root->data) + " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
void postorderTraversal(node* root) {
if (root != nullptr) {
postorderTraversal(root->left);
postorderTraversal(root->right);
container += to_string(root->data) + " ";
}
}
};
int main() {
Tree trees;
trees.readFile("input52.txt");
trees.commandLine("command52.txt");
trees.outFile("output69.txt");
}
