Я получаю ошибку в моем дереве AVL. Вывод очень близок к правильному ответу, но я не могу понять, что происходит. Я проверил все алгоритмы обхода в программе, и они, кажется, имеют смысл.
Сама программа читает 2 текстовых файла. Один файл содержит все целые числа для дерева AVL, а другой файл дает вам команды для печати программы по обходам дерева по предзаказу, порядку и порядку.
В этом примере ввод:
3 10 15 23 65 85 235 457 51 9 2 1 235 457 51 9 2 1
и текст команды:
Preorder Traversal
Postorder Traversal
Вывод:
23 1 2 3 9 10 15 51 65 85 235 457
1 2 3 9 10 15 51 65 85 235 457 23
Мой вывод :
23 3 2 1 10 9 15 85 65 51 235 457
1 2 9 15 10 3 51 65 457 235 85 23
Это немного не так, что наводит меня на мысль, что, возможно, вращение неправильное или что-то в функции печати я не вижу? Вот мой текущий код немного урезан для удобства чтения:
#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");
}