Реализация метода графического вывода в консоль для класса бинарного дерева
Производил собственно простое бинарное дерево, и решил для него красивый вывод в консоли. Возникла огромная куча проблем после создания класса для графического вывода (Graphic_in_width_travels), у него тип узла Graphic_Node(наследуется от обычного узла из tree).
Во время вызова метода (RecurAreaFilling класса Graphic_in_width_travels) для рекурсивного заполнения поля m_Area(массив строк, в которых содержатся все красиво упорядоченные узлы) вызывает точку останова сразу после окончания работы метода.
При этом, если продолжить отладку, дерево все же красиво выводится. Причем компилятор работает не стабильно, несколько раз запускаю один и тот же код, а он в разных местах вызывает точки останова.
Также иногда вызывает исключение в конце конструктора класса. Опять же, через раз вызывается точка ост.
После выполнения своего предназначения классом и после return 0 в main вызывается деструктор у tree, там всё тоже достаточно интересно. При удалении некоторых элементов не один раз вылазит debug error. При чем если деструктор вызывается без использования в программе класса для графического вывода, всё работает идеально, без малейших запинок.
Так что такого в классе Graphic_in_width_travels создает столько проблем?
Код:
main.cpp
#include <iostream>
#include "tree.h"
int main()
{
tree <int, int> tr;
tr.insert(16, 16);
tr.insert(5, 5);
tr.insert(25, 25);
tr.insert(1, 1);
tr.insert(12, 12);
tr.insert(20, 20);
tr.insert(30, 30);
tr.insert(-2, -2);
tr.insert(3, 3);
tr.insert(9, 9);
tr.insert(14, 14);
tr.insert(18, 18);
tr.insert(22, 22);
tr.insert(28, 28);
tr.insert(35, 35);
tr.insert(-3, -3);
tr.insert(0, 0);
tr.insert(2, 2);
tr.insert(4, 4);
tr.insert(6, 6);
tr.insert(11, 11);
tr.insert(13, 13);
tr.insert(15, 15);
tr.insert(17, 17);
tr.insert(19, 19);
tr.insert(21, 21);
tr.insert(24, 24);
tr.insert(26, 26);
tr.insert(29, 29);
tr.insert(33, 33);
tr.insert(36, 36);
tr.console_graphic_output();
return 0;
}
tree.h
#pragma once
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include "Graphic_in_width_travels.h"
#include "Node.h"
using namespace std;
template<typename Tkey, typename Tdata> class Node;
template<typename Tkey, typename Tdata>class tree
{
public:
tree();
~tree();
//adding
void insert(Tkey, Tdata);
//delete
bool delete_by_key(Tkey key);
void clear();
//capacity
int size();
//output console travers
void console_graphic_output();
private:
Node<Tkey, Tdata>* m_pRoot;
int m_Size;
};
template<typename Tkey, typename Tdata>tree<Tkey, Tdata>::tree()
{
this->m_pRoot = nullptr;
this->m_Size = 0;
}
template<typename Tkey, typename Tdata>tree<Tkey, Tdata>::~tree()
{
clear();
}
//adding
template<typename Tkey, typename Tdata> void tree<Tkey, Tdata>::insert(Tkey Key, Tdata Data)
{
Node<Tkey, Tdata>* newNode = new Node<Tkey, Tdata>(Key, Data);
if (this->m_pRoot == nullptr)
{
this->m_pRoot = newNode;
}
else
{
if constexpr (std::is_same_v<Tkey, string>)
{
Node<Tkey, Tdata>* current = m_pRoot;
while (current) {
int index = 0;
// is newNode->m_Key < current->m_Key? first(left)(-1), second(right)(1), Equal(0)
if (newNode->m_Key.size() == current->m_Key.size()) {
for (size_t i = 0; i < newNode->m_Key.size(); i++)
{
if (newNode->m_Key[i] < current->m_Key[i]) {
index = -1;
break;
}
else if (newNode->m_Key[i] > current->m_Key[i]) {
index = -1;
break;
}
else continue;
}
}
else if (newNode->m_Key.size() < current->m_Key.size()) index = -1;
else if (newNode->m_Key.size() > current->m_Key.size()) index = 1;
if (index == -1) {
if (current->pLeft == nullptr) {
current->pLeft = newNode;
newNode->pParent = current;
break;
}
current = current->pLeft;
}
else if (index == 1) {
if (current->pRight == nullptr) {
current->pRight = newNode;
newNode->pParent = current;
break;
}
current = current->pRight;
}
else if (index == 0) {
cout << "This key is already in the tree. \nIt is impossible to install two identical keys." << endl;
return;
}
}
}
else
{
Node<Tkey, Tdata>* current = m_pRoot;
while (current) {
if (newNode->m_Key < current->m_Key) {
if (current->pLeft == nullptr) {
current->pLeft = newNode;
newNode->pParent = current;
break;
}
current = current->pLeft;
}
else if (newNode->m_Key > current->m_Key) {
if (current->pRight == nullptr) {
current->pRight = newNode;
newNode->pParent = current;
break;
}
current = current->pRight;
}
else if (newNode->m_Key == current->m_Key) {
cout << "This key is already in the tree. \nIt is impossible to install two identical keys." << endl;
return;
}
}
}
}
this->m_Size++;
}
//delete
template<typename Tkey, typename Tdata> bool tree<Tkey, Tdata>::delete_by_key(Tkey key)
{
Node<Tkey, Tdata>* toDelete = m_pRoot;
if constexpr (std::is_same_v<Tkey, string>)
{
while (toDelete)
{
int index = 0;
// is newNode->m_Key < current->m_Key? first(left)(-1), second(right)(1), Equal(0)
if (key.size() == toDelete->m_Key.size())
{
for (size_t i = 0; i < key.size(); i++)
{
if (key[i] < toDelete->m_Key[i])
{
index = -1;
break;
}
else if (key[i] > toDelete->m_Key[i])
{
index = -1;
break;
}
else
{
continue;
}
}
}
else if (key.size() < toDelete->m_Key.size()) index = -1;
else if (key.size() > toDelete->m_Key.size()) index = 1;
if (index == -1)
{
toDelete = toDelete->pLeft;
}
else if (index == 1)
{
toDelete = toDelete->pRight;
}
else if (index == 0)
{
break;
}
}
}
else {
while (toDelete)
{
if (key < toDelete->m_Key)
{
toDelete = toDelete->pLeft;
}
else if (key > toDelete->m_Key)
{
toDelete = toDelete->pRight;
}
else
{
break;
}
}
}
if (toDelete == nullptr)
{
return false;
}
else
{
if (toDelete == m_pRoot)
{
if (toDelete->pLeft == nullptr && toDelete->pRight == nullptr)
{
delete toDelete;
toDelete = nullptr;
}
else if (toDelete->pLeft != nullptr && toDelete->pRight == nullptr)
{
this->m_pRoot = toDelete->pLeft;
delete toDelete;
this->m_pRoot->pParent = nullptr;
}
else if (toDelete->pLeft == nullptr && toDelete->pRight != nullptr)
{
this->m_pRoot = toDelete->pRight;
delete toDelete;
this->m_pRoot->pParent = nullptr;
}
else if (toDelete->pLeft != nullptr && toDelete->pRight != nullptr)
{
Node<Tkey, Tdata>* temp = toDelete->pRight;
while (temp->pLeft)
{
temp = temp->pLeft;
}
if ((toDelete->pRight)->pLeft == nullptr)
{
temp->pParent = toDelete->pParent;
temp->pLeft = toDelete->pLeft;
(toDelete->pLeft)->pParent = temp;
delete toDelete;
this->m_pRoot = temp;
}
else
{
if (temp->pRight == nullptr)
{
(temp->pParent)->pLeft = nullptr;
}
else
{
(temp->pRight)->pParent = temp->pParent;
(temp->pParent)->pLeft = temp->pRight;
}
temp->pParent = toDelete->pParent;
temp->pLeft = toDelete->pLeft;
temp->pRight = toDelete->pRight;
(toDelete->pLeft)->pParent = temp;
(toDelete->pRight)->pParent = temp;
this->m_pRoot = temp;
delete toDelete;
}
}
}
else
{
if (toDelete->pLeft == nullptr && toDelete->pRight == nullptr)
{
if ((toDelete->pParent)->pLeft == toDelete)
{
(toDelete->pParent)->pLeft = nullptr;
}
else if ((toDelete->pParent)->pRight == toDelete)
{
(toDelete->pParent)->pRight = nullptr;
}
delete toDelete;
}
else if (toDelete->pLeft != nullptr && toDelete->pRight == nullptr)
{
(toDelete->pLeft)->pParent = toDelete->pParent;
if ((toDelete->pParent)->pLeft == toDelete)
{
(toDelete->pParent)->pLeft = toDelete->pLeft;
}
else if ((toDelete->pParent)->pRight == toDelete)
{
(toDelete->pParent)->pRight = toDelete->pLeft;
}
delete toDelete;
}
else if (toDelete->pLeft == nullptr && toDelete->pRight != nullptr)
{
(toDelete->pRight)->pParent = toDelete->pParent;
if ((toDelete->pParent)->pLeft == toDelete)
{
(toDelete->pParent)->pLeft = toDelete->pRight;
}
else if ((toDelete->pParent)->pRight == toDelete)
{
(toDelete->pParent)->pRight = toDelete->pRight;
}
delete toDelete;
}
else if (toDelete->pLeft != nullptr && toDelete->pRight != nullptr)
{
Node<Tkey, Tdata>* temp = toDelete->pRight;
while (temp->pLeft)
{
temp = temp->pLeft;
}
if ((toDelete->pRight)->pLeft == nullptr)
{
temp->pRight = toDelete->pRight;
temp->pParent = toDelete->pParent;
(toDelete->pRight)->pParent = temp;
if ((toDelete->pParent)->pLeft == toDelete)
{
(toDelete->pParent)->pLeft = temp;
}
else if ((toDelete->pRight)->pRight == toDelete)
{
(toDelete->pParent)->pRight = temp;
}
delete toDelete;
}
else
{
if (temp->pRight == nullptr)
{
(temp->pParent)->pLeft = nullptr;
}
else
{
(temp->pRight)->pParent = temp->pParent;
(temp->pParent)->pLeft = temp->pRight;
}
temp->pLeft = toDelete->pLeft;
temp->pRight = toDelete->pRight;
temp->pParent = toDelete->pParent;
(toDelete->pLeft)->pParent = temp;
(toDelete->pRight)->pParent = temp;
if ((toDelete->pParent)->pLeft == toDelete)
{
(toDelete->pParent)->pLeft = temp;
}
else if ((toDelete->pRight)->pRight == toDelete)
{
(toDelete->pParent)->pRight = temp;
}
delete toDelete;
}
}
}
this->m_Size--;
return true;
}
}
template<typename Tkey, typename Tdata> void tree<Tkey, Tdata>::clear()
{
while (m_Size) delete_by_key(this->m_pRoot->m_Key);
}
//capacity
template<typename Tkey, typename Tdata> int tree<Tkey, Tdata>::size()
{
return this->m_Size;
}
//output console travers
template<typename Tkey, typename Tdata> void tree<Tkey, Tdata>::console_graphic_output()
{
Graphic_in_width_travels<Tkey, Tdata> F(this->m_pRoot);
F.print_console();
}
Node.h
#pragma once
template<typename Tkey, typename Tdata> class tree;
template<typename Tkey, typename Tdata> class Graphic_in_width_travels;
template<typename Tkey, typename Tdata> class Node
{
public:
friend class tree<Tkey, Tdata>;
friend class Graphic_in_width_travels<Tkey, Tdata>;
Node(Tkey key = Tkey(), Tdata data = Tdata(), Node* pLeft = nullptr, Node* pRight = nullptr, Node* pParent = nullptr)
{
this->m_Key = key;
this->m_Data = data;
this->pLeft = pLeft;
this->pRight = pRight;
this->pParent = pParent;
}
protected:
Node<Tkey, Tdata>* pLeft; //pointer left
Node<Tkey, Tdata>* pRight; //pointer right
Node<Tkey, Tdata>* pParent; //pointer parent
Tkey m_Key; //key
Tdata m_Data; //data
};
Graphic_in_width_travels.h
#pragma once
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include "Node.h"
#include "Graphic_Node.h"
using namespace std;
template<typename Tkey, typename Tdata> class Node;
template<typename Tkey, typename Tdata> class Graphic_Node;
template<typename Tkey, typename Tdata> class Graphic_in_width_travels
{
public:
Graphic_in_width_travels(Node<Tkey, Tdata>*);
~Graphic_in_width_travels();
//Print
void print_console();
void print_ncfile(string);
void print_cfile(ofstream&);
private:
//official
int middle_width(Graphic_Node<Tkey, Tdata>*);
int height_of_node(Graphic_Node<Tkey, Tdata>* node);
string get_type_dependence_str(Graphic_Node<Tkey, Tdata>*);
//helpers
int CheckСommonWidth();
void RecurAreaFilling(vector<Graphic_Node<Tkey, Tdata>*>);
Graphic_Node<Tkey, Tdata>* m_pRoot;
int m_Width;
string* m_Area;
};
template<typename Tkey, typename Tdata> Graphic_in_width_travels<Tkey, Tdata>::Graphic_in_width_travels(Node<Tkey, Tdata>* Root)
{
this->m_pRoot = new Graphic_Node<Tkey, Tdata>();
if (Root != nullptr)
{
this->m_pRoot->m_Key = Root->m_Key;
this->m_pRoot->m_Data = Root->m_Data;
this->m_pRoot->pLeft = Root->pLeft;
this->m_pRoot->pRight = Root->pRight;
this->m_pRoot->pParent = Root->pParent;
this->m_Width = CheckСommonWidth();
m_Area = new string[this->m_Width];
vector<Graphic_Node<Tkey, Tdata>*> roots;
roots.push_back(this->m_pRoot);
RecurAreaFilling(roots);
}
else
{
return;
}
}
template<typename Tkey, typename Tdata> Graphic_in_width_travels<Tkey, Tdata>::~Graphic_in_width_travels()
{
//if(this->m_pRoot != nullptr) delete[] m_Area;
//this->m_pRoot == nullptr;
}
template<typename Tkey, typename Tdata> int Graphic_in_width_travels<Tkey, Tdata>::CheckСommonWidth()
{
if (this->m_pRoot)
{
Graphic_Node<Tkey, Tdata>* currentR = (Graphic_Node<Tkey, Tdata>*)this->m_pRoot;
while (currentR->pRight) { currentR = (Graphic_Node<Tkey, Tdata>*)currentR->pRight; } //for widthInRigth
Graphic_Node<Tkey, Tdata>* currentL = (Graphic_Node<Tkey, Tdata>*)this->m_pRoot;
while (currentL->pLeft) { currentL = (Graphic_Node<Tkey, Tdata>*)currentL->pLeft; } //for widthInLeft
return (middle_width(currentR) - middle_width(currentL)) > 0 ? 2 * middle_width(currentR) + 1 : 2 * middle_width(currentL) + 1;
}
else
{
return 0;
}
}
template<typename Tkey, typename Tdata> int Graphic_in_width_travels<Tkey, Tdata>::height_of_node(Graphic_Node<Tkey, Tdata>* node)
{
if (node == 0)
return 0;
int left, right;
if (node->pLeft != NULL) {
left = height_of_node((Graphic_Node<Tkey, Tdata>*)node->pLeft);
}
else
left = 0;
if (node->pRight != NULL) {
right = height_of_node((Graphic_Node<Tkey, Tdata>*)node->pRight);
}
else
right = 0;
int max = left > right ? left : right;
return max + 1;
}
template<typename Tkey, typename Tdata> int Graphic_in_width_travels<Tkey, Tdata>::middle_width(Graphic_Node<Tkey, Tdata>* node)
{
if (this->m_pRoot == nullptr)
{
return 0;
}
else
{
Graphic_Node<Tkey, Tdata>* current = this->m_pRoot;
int middleWidth = 0;
if constexpr (std::is_same_v<Tkey, string>)
{
Graphic_Node<Tkey, Tdata>* current = m_pRoot;
while (current) {
int index = 0;
// is newNode->m_Key < current->m_Key? first(left)(-1), second(right)(1), Equal(0)
if (node->m_Key.size() == current->m_Key.size()) {
for (size_t i = 0; i < node->m_Key.size(); i++)
{
if (node->m_Key[i] < current->m_Key[i]) {
index = -1;
break;
}
else if (node->m_Key[i] > current->m_Key[i]) {
index = -1;
break;
}
else continue;
}
}
else if (node->m_Key.size() < current->m_Key.size()) index = -1;
else if (node->m_Key.size() > current->m_Key.size()) index = 1;
middleWidth += pow(2, height_of_node(current) - 2);
if (index == -1) {
current = current->pLeft;
}
else if (index == 1) {
current = current->pRight;
}
else if (index == 0) {
break;
}
}
}
else
{
while (current) {
if (node->m_Key < current->m_Key)
{
middleWidth += pow(2, height_of_node(current) - 2);
current = (Graphic_Node<Tkey, Tdata>*)current->pLeft;
}
else if (node->m_Key > current->m_Key)
{
middleWidth -= pow(2, height_of_node(current) - 2);
current = (Graphic_Node<Tkey, Tdata>*)current->pRight;
}
else if (node->m_Key == current->m_Key)
{
break;
}
}
}
return abs(middleWidth);
}
}
template<typename Tkey, typename Tdata> void Graphic_in_width_travels<Tkey, Tdata>::RecurAreaFilling(vector<Graphic_Node<Tkey, Tdata>*> roots)
{
if (this->m_pRoot == nullptr) return;
if (roots.back() == this->m_pRoot)
{
((Graphic_Node<Tkey, Tdata>*)(this->m_pRoot))->m_NumStr = this->m_Width / 2;
if (((Graphic_Node<Tkey, Tdata>*)(this->m_pRoot))->pLeft)
{
((Graphic_Node<Tkey, Tdata>*)(this->m_pRoot))->m_Facets = middle_width((Graphic_Node<Tkey, Tdata>*)((this->m_pRoot)->pLeft));
}
else if (((Graphic_Node<Tkey, Tdata>*)(this->m_pRoot))->pRight)
{
((Graphic_Node<Tkey, Tdata>*)(this->m_pRoot))->m_Facets = middle_width((Graphic_Node<Tkey, Tdata>*)(this->m_pRoot->pLeft));
}
else
{
((Graphic_Node<Tkey, Tdata>*)(this->m_pRoot))->m_Facets = 0;
}
m_Area[((Graphic_Node<Tkey, Tdata>*)(this->m_pRoot))->m_NumStr] += get_type_dependence_str((Graphic_Node<Tkey, Tdata>*)(this->m_pRoot));
}
vector<Graphic_Node<Tkey, Tdata>*> newLevel;
for (size_t i = 0; i < roots.size(); i++)
{
if (roots[i]->pLeft)
{
((Graphic_Node<Tkey, Tdata>*)roots[i]->pLeft)->m_NumStr = ((Graphic_Node<Tkey, Tdata>*)roots[i])->m_NumStr + ((Graphic_Node<Tkey, Tdata>*)roots[i])->m_Facets;
for (size_t j = 0; j < ((((Graphic_Node<Tkey, Tdata>*)(roots[i]->pLeft))->m_NumStr - ((Graphic_Node<Tkey, Tdata>*)roots[i])->m_NumStr) + m_Area[roots[i]->m_NumStr].size() - 1); j++)
{
m_Area[((Graphic_Node<Tkey, Tdata>*)(roots[i]->pLeft))->m_NumStr].push_back(' ');
}
m_Area[((Graphic_Node<Tkey, Tdata>*)(roots[i]->pLeft))->m_NumStr] += get_type_dependence_str((Graphic_Node<Tkey, Tdata>*)(roots[i]->pLeft));
if ((Graphic_Node<Tkey, Tdata>*)(roots[i]->pLeft)->pLeft)
{
((Graphic_Node<Tkey, Tdata>*)(roots[i]->pLeft))->m_Facets = ((Graphic_Node<Tkey, Tdata>*)(roots[i]))->m_Facets / 2;
}
else if ((Graphic_Node<Tkey, Tdata>*)(roots[i]->pLeft)->pRight)
{
((Graphic_Node<Tkey, Tdata>*)(roots[i]->pLeft))->m_Facets = ((Graphic_Node<Tkey, Tdata>*)(roots[i]))->m_Facets / 2;
}
else
{
((Graphic_Node<Tkey, Tdata>*)(roots[i]->pLeft))->m_Facets = 0;
}
newLevel.push_back((Graphic_Node<Tkey, Tdata>*)(roots[i]->pLeft));
}
if (roots[i]->pRight)
{
((Graphic_Node<Tkey, Tdata>*)(roots[i]->pRight))->m_NumStr = ((Graphic_Node<Tkey, Tdata>*)roots[i])->m_NumStr - ((Graphic_Node<Tkey, Tdata>*)roots[i])->m_Facets;
for (size_t j = 0; j < ((((Graphic_Node<Tkey, Tdata>*)roots[i])->m_NumStr - ((Graphic_Node<Tkey, Tdata>*)(roots[i]->pRight))->m_NumStr) + m_Area[roots[i]->m_NumStr].size() - 1); j++)
{
m_Area[((Graphic_Node<Tkey, Tdata>*)(roots[i]->pRight))->m_NumStr].push_back(' ');
}
m_Area[((Graphic_Node<Tkey, Tdata>*)(roots[i]->pRight))->m_NumStr] += get_type_dependence_str((Graphic_Node<Tkey, Tdata>*)roots[i]->pRight);
if ((Graphic_Node<Tkey, Tdata>*)((roots[i]->pRight)->pLeft))
{
((Graphic_Node<Tkey, Tdata>*)(roots[i]->pRight))->m_Facets = ((Graphic_Node<Tkey, Tdata>*)(roots[i]))->m_Facets / 2;
}
else if ((Graphic_Node<Tkey, Tdata>*)((roots[i]->pRight)->pRight))
{
((Graphic_Node<Tkey, Tdata>*)(roots[i]->pRight))->m_Facets = ((Graphic_Node<Tkey, Tdata>*)(roots[i]))->m_Facets / 2;
}
else
{
((Graphic_Node<Tkey, Tdata>*)(roots[i]->pRight))->m_Facets = 0;
}
newLevel.push_back((Graphic_Node<Tkey, Tdata>*)(roots[i]->pRight));
}
}
if (newLevel.size() == 0) return;
RecurAreaFilling(newLevel);
}
template<typename Tkey, typename Tdata> string Graphic_in_width_travels<Tkey, Tdata>::get_type_dependence_str(Graphic_Node<Tkey, Tdata>* node)
{
string str;
//if constexpr (std::is_same_v<Tkey, complexType>) { str += node->m_Key.get_sComplex(); }
//else if constexpr (std::is_same_v<Tkey, pointType>) { str += node->m_Key.get_sPoint(); }
//else if constexpr (std::is_same_v<Tkey, vectorType>) { str += node->m_Key.get_sVector(); }
str += to_string(node->m_Key);
//----------------------------------------------------------------------------------
//if constexpr (std::is_same_v<Tdata, complexType>) { str += ("(" + node->m_Data.get_sComplex() + ")"); }
//else if constexpr (std::is_same_v<Tdata, pointType>) { str += ("(" + node->m_Data.get_sPoint() + ")"); }
//else if constexpr (std::is_same_v<Tdata, vectorType>) { str += ("(" + node->m_Data.get_sVector() + ")"); }
str += "("; str += to_string(node->m_Data); str += ")";
return str;
}
//Print
template<typename Tkey, typename Tdata> void Graphic_in_width_travels<Tkey, Tdata>::print_console()
{
for (size_t i = 0; i < this->m_Width; i++)
{
if (this->m_Area[i].empty())
{
cout << endl;
}
else
{
cout << this->m_Area[i] << endl;
}
}
}
template<typename Tkey, typename Tdata> void Graphic_in_width_travels<Tkey, Tdata>::print_ncfile(string nameFile)
{
}
template<typename Tkey, typename Tdata> void Graphic_in_width_travels<Tkey, Tdata>::print_cfile(ofstream& OUT)
{
}
Graphic_Node.h
#pragma once
#include "Node.h"
template<typename Tkey, typename Tdata> class Graphic_in_width_travels;
template<typename Tkey, typename Tdata> class Graphic_Node : public Node<Tkey, Tdata>
{
friend class Graphic_in_width_travels<Tkey, Tdata>;
public:
private:
int m_NumStr;
int m_Facets;
};