0

у меня задача реализовать бинарное дерево поиска и сделать его визуализацию. Код срабатывает, не дерево в окно не выводится, подскажите в чем у меня ошибка

#include <iostream>
#include <queue>
#include <SFML/Graphics.hpp>
#include <map>
#include <vector>
#include <iostream>
#include <iomanip>

using namespace std;

// Описание узла дерева
struct Node {
    int key;
    Node* left;
    Node* right;
    Node* parent;
    int level; // уровень узла

    Node(int k) {
        key = k;
        left = nullptr;
        right = nullptr;
        parent = nullptr;
    }
};

// Описание бинарного дерева поиска
class BinarySearchTree
{
private:
    Node* root;
    vector<int> nodes;
    // Рекурсивная вспомогательная функция для вставки узла в дерево
    Node* insertHelper(Node* node, int key) {
        if (node == nullptr) {
            return new Node(key);
        }
        if (key < node->key) {
            Node* leftChild = insertHelper(node->left, key);
            leftChild->parent = node;
            node->left = leftChild;
        }
        else if (key > node->key) {
            Node* rightChild = insertHelper(node->right, key);
            rightChild->parent = node;
            node->right = rightChild;
        }
        return node;
    }

    // Рекурсивная вспомогательная функция для удаления узла из дерева
    Node* deleteHelper(Node* node, int key) {
        if (node == nullptr) {
            return nullptr;
        }
        if (key < node->key) {
            node->left = deleteHelper(node->left, key);
        }
        else if (key > node->key) {
            node->right = deleteHelper(node->right, key);
        }
        else {
            if (node->left == nullptr && node->right == nullptr) {
                delete node;
                node = nullptr;
            }
            else if (node->left == nullptr) {
                Node* temp = node;
                node = node->right;
                node->parent = temp->parent;
                delete temp;
            }
            else if (node->right == nullptr) {
                Node* temp = node;
                node = node->left;
                node->parent = temp->parent;
                delete temp;
            }
            else {
                Node* minRight = node->right;
                while (minRight->left != nullptr) {
                    minRight = minRight->left;
                }
                node->key = minRight->key;
                node->right = deleteHelper(node->right, minRight->key);
            }
        }
        return node;
    }

    // Рекурсивная вспомогательная функция для поиска узла в дереве
    Node* searchHelper(Node* node, int key) {
        if (node == nullptr) {
            return nullptr;
        }
        if (node->key == key) {
            return node;
        }
        else if (key < node->key) {
            return searchHelper(node->left, key);
        }
        else {
            return searchHelper(node->right, key);
        }
    }

    // Рекурсивная вспомогательная функция для обхода дерева в симметричном порядке
    void inOrderHelper(Node* node) {
        if (node != nullptr) {
            inOrderHelper(node->left);
            cout << node->key << " ";
            inOrderHelper(node->right);
        }
    }

    // Рекурсивная вспомогательная функция для обхода дерева в обратном порядке
    void postOrderHelper(Node* node) {
        if (node != nullptr) {
            postOrderHelper(node->left);
            postOrderHelper(node->right);
            cout << node->key << " ";
        }
    }
    // Вспомогательная функция для обхода дерева в прямом порядке
    void preOrderHelper(Node* node) {
        if (node != nullptr) {
            nodes.push_back(node->key);
            preOrderHelper(node->left);
            preOrderHelper(node->right);
        }
    }

    // Рекурсивная вспомогательная функция для подсчета количества узлов в дереве
    int countNodesHelper(Node* node) {
        if (node == nullptr) {
            return 0;
        }
        return 1 + countNodesHelper(node->left) + countNodesHelper(node->right);
    }

    // Рекурсивная вспомогательная функция для вычисления высоты дерева
    int heightHelper(Node* node) {
        if (node == nullptr) {
            return -1;
        }
        return 1 + max(heightHelper(node->left), heightHelper(node->right));
    }

    // Рекурсивная вспомогательная функция для балансировки дерева
    void balanceHelper(vector<Node*>& nodes, int start, int end) {
        if (start > end) {
            return;
        }
        int mid = (start + end) / 2;
        insert(nodes[mid]->key);
        balanceHelper(nodes, start, mid - 1);
        balanceHelper(nodes, mid + 1, end);
    }

public:

    BinarySearchTree() {
        root = nullptr;
    }

    Node* getRoot() {
        return root;
    }

    // Вставка узла в дерево
    void insert(int key) {
        root = insertHelper(root, key);
    }

    // уровень узла относительно корня дерева
    int getLevel(Node* root, Node* node, int level) {
        if (root == nullptr) {
            return 0;
        }
        if (root == node) {
            return level;
        }
        int downlevel = getLevel(root->left, node, level + 1);
        if (downlevel != 0) {
            return downlevel;
        }
        downlevel = getLevel(root->right, node, level + 1);
        return downlevel;
    }

    // Удаление узла из дерева
    void deleteNode(int key) {
        root = deleteHelper(root, key);
    }

    // Поиск узла по ключу
    Node* search(int key) {
        return searchHelper(root, key);
    }

    // Обход дерева в прямом порядке
    void preOrder() {
        preOrderHelper(root);
    }

    // Обход дерева в симметричном порядке
    void inOrder() {
        inOrderHelper(root);
    }

    // Обход дерева в обратном порядке
    void postOrder() {
        postOrderHelper(root);
    }

    // Подсчет количества узлов в дереве
    int countNodes() {
        return countNodesHelper(root);
    }

    // Вычисление высоты дерева
    int height() {
        return heightHelper(root);
    }

    // Балансировка дерева
    void balance() {
        int n = countNodes();
        vector<Node*> nodes;
        storeBSTNodes(root, nodes);
        root = nullptr;
        balanceHelper(nodes, 0, n - 1);
    }

    void storeBSTNodes(Node* node, vector<Node*>& nodes) {
        if (node == nullptr) {
            return;
        }
        storeBSTNodes(node->left, nodes);
        nodes.push_back(node);
        storeBSTNodes(node->right, nodes);
    }

    // Вывод дерева в горизонтальном виде
    void printHorizontal(Node* node, int depth) {
        if (node == nullptr) {
            return;
        }
        printHorizontal(node->right, depth + 1);
        cout << setw(4 * depth) << "";
        cout << node->key << endl;
        printHorizontal(node->left, depth + 1);
    }

    // Вывод дерева в вертикальном виде
    void printVertical(Node* node, int indent = 0) {
        if (node != nullptr) {
            if (node->right) {
                printVertical(node->right, indent + 4);
            }
            if (indent) {
                cout << setw(indent) << " ";
            }
            if (node->right) {
                cout << " /\n" << setw(indent) << " ";
            }
            cout << node->key << "\n ";
            if (node->left) {
                cout << setw(indent) << " " << " \\\n";
                printVertical(node->left, indent + 4);
            }
        }
    }

    // Отображение дерева с помощью графической библиотеки SFML
    void visualize()
    {
        sf::RenderWindow window(sf::VideoMode(800, 600), "Binary Search Tree");
        window.setFramerateLimit(60);

        vector<Node*> nodes;
        storeBSTNodes(root, nodes);

        const int nodeRadius = 25;
        const int spacing = 75;

        // Рассчитываем координаты для каждого узла
        map<Node*, sf::Vector2f> nodePositions;
        for (int i = 0; i < nodes.size(); i++) {
            int x = (i + 1) * spacing;
            int y = (nodes[i]->level + 1) * spacing;
            nodePositions[nodes[i]] = sf::Vector2f(x, y);
        }

        // Рисуем связи между узлами
        vector<sf::VertexArray> lines;
        for (int i = 0; i < nodes.size(); i++)
        {
            Node* node = nodes[i];
            if (node->left != nullptr)
            {
                sf::VertexArray line(sf::Lines, 2);
                line[0].position = nodePositions[node];
                line[1].position = nodePositions[node->left];
                lines.push_back(line);
            }
            if (node->right != nullptr)
            {
                sf::VertexArray line(sf::Lines, 2);
                line[0].position = nodePositions[node];
                line[1].position = nodePositions[node->right];
                lines.push_back(line);
            }
        }

        // Рисуем узлы
        vector<sf::CircleShape> circles;
        for (int i = 0; i < nodes.size(); i++)
        {
            Node* node = nodes[i];
            sf::CircleShape circle(nodeRadius);
            circle.setFillColor(sf::Color::White);
            circle.setOutlineThickness(2);
            circle.setOutlineColor(sf::Color::Black);
            circle.setPosition(nodePositions[node].x - nodeRadius, nodePositions[node].y - nodeRadius);
            circles.push_back(circle);
        }

        // Рисуем текст внутри узлов
        vector<sf::Text> texts;
        sf::Font font;
        if (!font.loadFromFile("ARIALN.TTF")) { 
            cerr << "Error loading font" << endl;
            return;
        }
        for (int i = 0; i < nodes.size(); i++)
        {
            Node* node = nodes[i];
            sf::Text text(to_string(node->key), font);
            text.setCharacterSize(nodeRadius);
            text.setFillColor(sf::Color::Black);
            sf::FloatRect textRect = text.getLocalBounds();
            text.setOrigin(textRect.left + textRect.width / 2.0f, textRect.top + textRect.height / 2.0f);
            text.setPosition(nodePositions[node].x, nodePositions[node].y);
            texts.push_back(text);
        }

        // Отображаем все на экране
        while (window.isOpen())
        {
            sf::Event event;
            while (window.pollEvent(event))
            {
                if (event.type == sf::Event::Closed)
                {
                    window.close();
                }
            }
            window.clear(sf::Color::White);
            for (int i = 0; i < lines.size(); i++) {
                window.draw(lines[i]);
            }
            for (int i = 0; i < circles.size(); i++) {
                window.draw(circles[i]);
            }
            for (int i = 0; i < texts.size(); i++) {
                window.draw(texts[i]);
            }   
            window.display();

        }
        
    }
    // Поиск узла по ключу
    Node* search(Node* node, int key)
    {
        if (node == nullptr || node->key == key) {
            return node;
        }
        if (node->key < key) {
            return search(node->right, key);
        }
        return search(node->left, key);
    }


};

int main()
{
    
    BinarySearchTree bst;
    // Вставка узлов
    bst.insert(50);
    bst.insert(30);
    bst.insert(20);
    bst.insert(40);
    bst.insert(70);
    bst.insert(60);
    bst.insert(80);

    // Вывод дерева в горизонтальном виде
    bst.printHorizontal(bst.getRoot(), 0);

    // Вывод дерева в вертикальном виде
    bst.printVertical(bst.getRoot(), 0);

    // Отображение дерева с помощью графической библиотеки SFML
    bst.visualize();

    // Поиск узла по ключу
    Node* node = bst.search(bst.getRoot(), 60);
    if (node != nullptr) {
        cout << "Found node with key " << node->key << endl;
    }
    else {
        cout << "Node not found" << endl;
    }

    // Удаление узлов
    bst.deleteNode(20);
    bst.deleteNode(30);
    bst.deleteNode(50);
    bst.printHorizontal(bst.getRoot(), 0);

    // Вывод дерева в вертикальном виде после удаления узлов
    bst.printVertical(bst.getRoot(), 0);

    // Отображение дерева после удаления узлов
    bst.visualize();
    cin.get();

    return 0;
}

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Посмотрите другие вопросы с метками или задайте свой вопрос.