Материал: Larin_Anton_AiSD_21_KW

заключение

В ходе данной работы был изучен принцип работы АВЛ-дерева, освоены алгоритмы для работы с данной структурой данных. Далее с использованием среду QtCreator была написана программа для визуализации работы с АВЛ-деревом, демонстрирующая полученные знания на практике.

список использованных источников

1. Qt Documentation // Qt Docs. URL: https://doc.qt.io/ (Дата обращения: 25.10.2019)

2. Бинарные деревья поиска // habr. URL: https://habr.com/en/post/267855/ (Дата обращения: 25.10.2019)

1. АВЛ-деревья // habr. URL: https://habr.com/en/post/150732/ (Дата обращения: 25.10.2019)

приложение А

Содержимое main.cpp

#include "mainwindow.h"
#include <QApplication>
#include <iostream>
int main(int argc, char *argv[]) {
    QApplication a(argc, argv);
    MainWindow w;
    w.setWindowTitle("AVL tree");
    w.show();
    return a.exec();
}

приложение Б

Содержимое mainwindow.h

#ifndef MAINWINDOW_H
#define MAINWINDOW_H
#include <QMainWindow>
#include "ui_mainwindow.h"
#include <QPushButton>
#include <QBoxLayout>
#include <QPixmap>
#include <QFileDialog>
#include <QTextBrowser>
#include <QMessageBox>
#include <QListView>
#include <QtDebug>
#include <QStandardItemModel>
#include <QStandardItem>
#include <QButtonGroup>
#include <QPushButton>
#include <QSpinBox>
#include "graphgraphicview.h"
#include "listviewactionlogger.h"
namespace Ui {
class MainWindow;
}
class MainWindow : public QMainWindow
{
    Q_OBJECT
public:
    explicit MainWindow(QWidget *parent = nullptr);
    ~MainWindow();
signals:
private slots:
    void slot_butAdd_clicked(bool);
    void slot_butRem_clicked(bool);
    void slot_butNew_clicked(bool);
    void slot_butSkip_clicked(bool);
    void slot_listView_clicked(QModelIndex);
    void slot_listView_selectionChanged(QItemSelection,QItemSelection);
    void slot_listView_select(int);
private:
    Ui::MainWindow *ui;
    GraphGraphicView *graphicsView;
    QHBoxLayout *sideslayout;
    QVBoxLayout *vertlayout;
    QHBoxLayout *buttonslayout;
    QWidget *central_widget;
    QPixmap stdPixmap;
    QListView *lstVw;
    ListViewActionLogger* listViewAL;
    QPushButton* butNew;
    QPushButton* butAdd;
    QPushButton* butRem;
    QPushButton* butSkip;
    QSpinBox* spinBox;
    AVL::AVL<int> avl;
};
#endif // MAINWINDOW_H

Приложение в содержимое mainWindow.Cpp

#include "graphgraphicview.h"
GraphGraphicView::GraphGraphicView(QGraphicsView *parent) : QGraphicsView(parent) {
    this->setHorizontalScrollBarPolicy(Qt::ScrollBarAlwaysOff); // Disable scroll horizontally
    this->setVerticalScrollBarPolicy(Qt::ScrollBarAlwaysOff);   // Disable scroll vertically
    this->setAlignment(Qt::AlignCenter);                        // Make the contents of binding to the center
    this->setSizePolicy(QSizePolicy::Expanding, QSizePolicy::Expanding);    // Stretch the widget content
    this->setMinimumHeight(100);
    this->setMinimumWidth(100);
    scene = new QGraphicsScene();   // Initialize the scene to render
    this->setScene(scene);          // Set the scene in a widget
    group_1 = new QGraphicsItemGroup(); // Initialize the first group of elements
    group_2 = new QGraphicsItemGroup(); // Initialize the elements of the second group
    scene->addItem(group_1);            // Add the first group into the scene
    scene->addItem(group_2);            // Add the second group into the scene
    timer = new QTimer();               // Initialize Timer
    timer->setSingleShot(true);
    //_avl=AVL::AVL<int>();
    _width = this->width()*9/10;
    _height = this->height();
    timer->start(50);
}
GraphGraphicView::~GraphGraphicView()
{
    
}
void GraphGraphicView::slotDrawAvl(AVL::AVL<int> _avl)
{
    last_drawn_avl = _avl;//Save last drawn tree to redraw if needed
    this->deleteItemsFromGroup(group_1);//Clead groups
    this->deleteItemsFromGroup(group_2);//They will be refilled
    scene->setSceneRect(0,0,_width,_height);
    _lvlInt = (_height - 2*_nodeSize) / _avl.height();//Calculate interval between levels of tree
    if(!_avl.isEmpty())_slotDrawAvl(_avl,1,_width/2);//Is tree is not empty - draw it
    else{
        group_1->addToGroup(scene->addText("Empty tree!"));//Otherwise print empty tree tittle
    }
}
void GraphGraphicView::_slotDrawAvl(AVL::AVL<int> avl, int lvl, float xCoord)
{
    QPen penBlack(Qt::black);
    QPen penRed(Qt::red);
    int penWidth = penBlack.width();
    penRed.setWidth(2*penWidth);
    int x=xCoord;
    int y=_lvlInt*lvl-_lvlInt/2;
    if(avl.Root->highlight)// Draw root node
        group_1->addToGroup(scene->addEllipse(xCoord,y,_nodeSize,_nodeSize,penRed));
    else
        group_1->addToGroup(scene->addEllipse(xCoord,y,_nodeSize,_nodeSize,penBlack));
    //Do stuff with text. Here and hence!
    std::string strRoot = std::to_string( avl.root() );
    QFont font = QFont();
    font.setStyleHint(QFont::Monospace);
    font.setLetterSpacing(QFont::SpacingType::AbsoluteSpacing,0);
    font.setPixelSize(_nodeSize/strRoot.length());
    QGraphicsTextItem* text = scene->addText(QString::fromStdString( strRoot ),font);
    text->setTextWidth(_nodeSize);
    QTextBlockFormat format;//Text alignment
    format.setAlignment(Qt::AlignCenter);
    format.setIndent(0);
    format.setTextIndent(0);
    QTextCursor cursor = text->textCursor();
    cursor.select(QTextCursor::Document);
    cursor.mergeBlockFormat(format);
    cursor.clearSelection();
    text->setTextCursor(cursor);
    text->document()->setDocumentMargin(0);
    text->setTransformOriginPoint(xCoord+_nodeSize/2,(y)+_nodeSize/2);
    text->setPos(0,0);
    QRectF rect = text->boundingRect();
    text->setPos(xCoord+(_nodeSize-text->boundingRect().width())/2 ,y + (strRoot.length()==1? -10:strRoot.length()>2?15:0));//some magic going on here
    //Done messing with text
    group_1->addToGroup(text);//Adding text
    if(!avl.left().isEmpty()){//Draw left line
        if(avl.Root->highlightLeft)
            group_1->addToGroup(scene->addLine(xCoord,y+_nodeSize,xCoord-_width/(1<<(lvl+1))+_nodeSize/2,y+_lvlInt,penRed));
        else
            group_1->addToGroup(scene->addLine(xCoord,y+_nodeSize,xCoord-_width/(1<<(lvl+1))+_nodeSize/2,y+_lvlInt,penBlack));
        _slotDrawAvl(avl.left(),lvl+1,xCoord-_width/(1<<(lvl+1)));
    }
    else
    {
        if(avl.Root->highlightLeft)group_1->addToGroup(scene->addLine(xCoord,y+_nodeSize,xCoord-_width/(1<<(lvl+1))+_nodeSize/2,y+_lvlInt,penRed));
    }
    if(!avl.right().isEmpty()){//Draw right line
        if(avl.Root->highlightRight)
            group_1->addToGroup(scene->addLine(xCoord+_nodeSize,y+_nodeSize,xCoord+_width/(1<<(lvl+1))+_nodeSize/2,y+_lvlInt,penRed));
        else
            group_1->addToGroup(scene->addLine(xCoord+_nodeSize,y+_nodeSize,xCoord+_width/(1<<(lvl+1))+_nodeSize/2,y+_lvlInt,penBlack));
        _slotDrawAvl(avl.right(),lvl+1,xCoord+_width/(1<<(lvl+1)));
    }
    else
    {
        if(avl.Root->highlightRight)group_1->addToGroup(scene->addLine(xCoord+_nodeSize,y+_nodeSize,xCoord+_width/(1<<(lvl+1))+_nodeSize/2,y+_lvlInt,penRed));
    }
}// This method catches widget resize event
void GraphGraphicView::resizeEvent(QResizeEvent *event)
{
    timer->start(50);   // As soon as we start the timer event has occurred to render
    _width = this->width()*9/10;
    _height= this->height();
    slotDrawAvl(last_drawn_avl);
    QGraphicsView::resizeEvent(event);  //Run event the parent class
}
/* Method for removing all the elements from the group
 * */
void GraphGraphicView::deleteItemsFromGroup(QGraphicsItemGroup *group)
{
    /* Loop through all the elements of the scene,
     * and if they belong to the group, passed into the method, then delete them
     * */
    foreach( QGraphicsItem *item, scene->items(group->boundingRect())) {
       if(item->group() == group ) {
          delete item;
       }
    }
}

Приложение г содержание graphgraphicview.H

#pragma once
#ifndef GRAPHGRAPHICVIEW_H
#define GRAPHGRAPHICVIEW_H
#include <QWidget>
#include <QGraphicsView>
#include <QGraphicsScene>
#include <QGraphicsItemGroup>
#include <QTimer>
#include <QTextBlockFormat>
#include <QTextCursor>
#include <QTextDocument>
#include "AVLTreeClass.h"
// Extend the class QGraphicsView
class GraphGraphicView : public QGraphicsView
{
    Q_OBJECT
public:
    explicit GraphGraphicView(QGraphicsView *parent = nullptr);
    ~GraphGraphicView();
private:
    QGraphicsScene      *scene;//Graphics scene - canvas
    QGraphicsItemGroup  *group_1;//One group for elements containing
    QGraphicsItemGroup  *group_2;//Another one
    AVL::AVL<char> avltree;//Extra tree precaution purposes
    AVL::AVL<int> last_drawn_avl;//Last drawn tree saved for redrawing if needed
    int _width = 0;//Drawing field widtg
    int _height = 0;//Drawing field heitght
    float _nodeSize = 50;//Size of one tree node
    float _lvlInt = 0;//Interval between intervals
    QTimer              *timer;
signals:
public slots:
    void slotDrawAvl(AVL::AVL<int> _avl);
    void _slotDrawAvl(AVL::AVL<int> avl, int lvl, float xCoord);
    //void slotAlarmTimer();  /* slot timer overflow handler there will be repainting the widget*/
    void resizeEvent(QResizeEvent *event);
    void deleteItemsFromGroup(QGraphicsItemGroup *group_1);
};
//: QGraphicsView(parent)
#endif // GRAPHGRAPHICVIEW_H

Приложение д содержание graphgraphicview.Cpp

#include "graphgraphicview.h"
GraphGraphicView::GraphGraphicView(QGraphicsView *parent) : QGraphicsView(parent) {
    this->setHorizontalScrollBarPolicy(Qt::ScrollBarAlwaysOff); // Disable scroll horizontally
    this->setVerticalScrollBarPolicy(Qt::ScrollBarAlwaysOff);   // Disable scroll vertically
    this->setAlignment(Qt::AlignCenter);                        // Make the contents of binding to the center
    this->setSizePolicy(QSizePolicy::Expanding, QSizePolicy::Expanding);    // Stretch the widget content
    this->setMinimumHeight(100);
    this->setMinimumWidth(100);
    scene = new QGraphicsScene();   // Initialize the scene to render
    this->setScene(scene);          // Set the scene in a widget
    group_1 = new QGraphicsItemGroup(); // Initialize the first group of elements
    group_2 = new QGraphicsItemGroup(); // Initialize the elements of the second group
    scene->addItem(group_1);            // Add the first group into the scene
    scene->addItem(group_2);            // Add the second group into the scene
    timer = new QTimer();               // Initialize Timer
    timer->setSingleShot(true);
    //_avl=AVL::AVL<int>();
    _width = this->width()*9/10;
    _height = this->height();
    timer->start(50);
}
GraphGraphicView::~GraphGraphicView()
{
    
}
void GraphGraphicView::slotDrawAvl(AVL::AVL<int> _avl)
{
    last_drawn_avl = _avl;//Save last drawn tree to redraw if needed
    this->deleteItemsFromGroup(group_1);//Clead groups
    this->deleteItemsFromGroup(group_2);//They will be refilled
    scene->setSceneRect(0,0,_width,_height);
    _lvlInt = (_height - 2*_nodeSize) / _avl.height();//Calculate interval between levels of tree
    if(!_avl.isEmpty())_slotDrawAvl(_avl,1,_width/2);//Is tree is not empty - draw it
    else{
        group_1->addToGroup(scene->addText("Empty tree!"));//Otherwise print empty tree tittle
    }
}
void GraphGraphicView::_slotDrawAvl(AVL::AVL<int> avl, int lvl, float xCoord)
{
    QPen penBlack(Qt::black);
    QPen penRed(Qt::red);
    int penWidth = penBlack.width();
    penRed.setWidth(2*penWidth);
    int x=xCoord;
    int y=_lvlInt*lvl-_lvlInt/2;
    if(avl.Root->highlight)// Draw root node
        group_1->addToGroup(scene->addEllipse(xCoord,y,_nodeSize,_nodeSize,penRed));
    else
        group_1->addToGroup(scene->addEllipse(xCoord,y,_nodeSize,_nodeSize,penBlack));
    //Do stuff with text. Here and hence!
    std::string strRoot = std::to_string( avl.root() );
    QFont font = QFont();
    font.setStyleHint(QFont::Monospace);
    font.setLetterSpacing(QFont::SpacingType::AbsoluteSpacing,0);
    font.setPixelSize(_nodeSize/strRoot.length());
    QGraphicsTextItem* text = scene->addText(QString::fromStdString( strRoot ),font);
    text->setTextWidth(_nodeSize);
    QTextBlockFormat format;//Text alignment
    format.setAlignment(Qt::AlignCenter);
    format.setIndent(0);
    format.setTextIndent(0);
    QTextCursor cursor = text->textCursor();
    cursor.select(QTextCursor::Document);
    cursor.mergeBlockFormat(format);
    cursor.clearSelection();
    text->setTextCursor(cursor);
    text->document()->setDocumentMargin(0);
    text->setTransformOriginPoint(xCoord+_nodeSize/2,(y)+_nodeSize/2);
    text->setPos(0,0);
    QRectF rect = text->boundingRect();
    text->setPos(xCoord+(_nodeSize-text->boundingRect().width())/2 ,y + (strRoot.length()==1? -10:strRoot.length()>2?15:0));//some magic going on here
    //Done messing with text
    group_1->addToGroup(text);//Adding text
    if(!avl.left().isEmpty()){//Draw left line
        if(avl.Root->highlightLeft)
            group_1->addToGroup(scene->addLine(xCoord,y+_nodeSize,xCoord-_width/(1<<(lvl+1))+_nodeSize/2,y+_lvlInt,penRed));
        else
            group_1->addToGroup(scene->addLine(xCoord,y+_nodeSize,xCoord-_width/(1<<(lvl+1))+_nodeSize/2,y+_lvlInt,penBlack));
        _slotDrawAvl(avl.left(),lvl+1,xCoord-_width/(1<<(lvl+1)));
    }
    else
    {
        if(avl.Root->highlightLeft)group_1->addToGroup(scene->addLine(xCoord,y+_nodeSize,xCoord-_width/(1<<(lvl+1))+_nodeSize/2,y+_lvlInt,penRed));
    }
    if(!avl.right().isEmpty()){//Draw right line
        if(avl.Root->highlightRight)
            group_1->addToGroup(scene->addLine(xCoord+_nodeSize,y+_nodeSize,xCoord+_width/(1<<(lvl+1))+_nodeSize/2,y+_lvlInt,penRed));
        else
            group_1->addToGroup(scene->addLine(xCoord+_nodeSize,y+_nodeSize,xCoord+_width/(1<<(lvl+1))+_nodeSize/2,y+_lvlInt,penBlack));
        _slotDrawAvl(avl.right(),lvl+1,xCoord+_width/(1<<(lvl+1)));
    }
    else
    {
        if(avl.Root->highlightRight)group_1->addToGroup(scene->addLine(xCoord+_nodeSize,y+_nodeSize,xCoord+_width/(1<<(lvl+1))+_nodeSize/2,y+_lvlInt,penRed));
    }
}// This method catches widget resize event
void GraphGraphicView::resizeEvent(QResizeEvent *event)
{
    timer->start(50);   // As soon as we start the timer event has occurred to render
    _width = this->width()*9/10;
    _height= this->height();
    slotDrawAvl(last_drawn_avl);
    QGraphicsView::resizeEvent(event);  //Run event the parent class
}
/* Method for removing all the elements from the group
 * */
void GraphGraphicView::deleteItemsFromGroup(QGraphicsItemGroup *group)
{
    /* Loop through all the elements of the scene,
     * and if they belong to the group, passed into the method, then delete them
     * */
    foreach( QGraphicsItem *item, scene->items(group->boundingRect())) {
       if(item->group() == group ) {
          delete item;
       }
    }
}