Я строю дерево AVL. Когда я даю ввод ниже 10, он работает нормально. но когда я даю больше 10, то коды ломаются и говорят ошибки сегментации и дают неправильный вывод. Это для моего школьного задания.
Ввод этого формата;
D13 D60 D76 D12 A17 D98 A94 D70 D3 A23 A42 D45 A100 D50 A99 A22 A87 A4
A90 D88 A71 A20 D39 D83 A97 A56 D28 A9 D43 A19 D5 A11 A54 A73 D54 A9 A24 A58 D6 D80 A72 A47 A82 A12 A75 D77 D84 D86 A60 D64 D70 D70 A73 A71 A40 D94 D27 A63 D47 A42 A44 A27 A100 A6 D84 A19 D65 A75 A55 A63 A39 D99 A50 D98 A98 D100 D93 A91 A81 D59 D56 D29 D11 D45 D47 D55 D85 D7 D70 A13 A55 A25 D35 D65 A48 D55 A45 D29 A35 A15 IN
и вывод выглядит так:
4 6 9 12 13 15 17 19 20 22 23 24 25 27 35 39 40 42 44 45 48 50 58
60 63 71 72 73 75 81 82 87 90 91 97 98
#include <iostream>
#include <string>
using namespace std;
/* First we are going to design structure for Nodes. */
struct Node {
Node* l = NULL; //r of the node
Node* r = NULL; //l of the node
int h = 0; //Height of the node
int d = 0; //Data Part of the node
};
Node* getNode(int d){
Node* node = new Node();
node->d = d;
node->l = NULL;
node->r = NULL;
node->h = 1;
return (node);
}
int getH(Node* n) { //Getting the Height of Tree
if (n == NULL)
return 0;
return n->h;
}
int getBlnc(Node* n){
if (n == NULL)
return 0;
else {
return getH(n->l) - getH(n->r);
}
}
int havMaxValue(int j, int k){
if (j > k)
return j;
return k;
}
/* AVL Rotatations */
Node* rR(Node* temNode) //Right Rotation{
Node* x = temNode->l;
x->r = temNode;
temNode->l = x->r;
temNode->h = havMaxValue(getH(temNode->l), getH(temNode->r)) + 1;
x->h = havMaxValue(getH(x->l), getH(x->r)) + 1;
return x;
}
Node* lR(Node* TempNode) //LeftRotate
{
Node* tempNode2 = TempNode->r;
Node* TemNode1 = tempNode2->l;
tempNode2->l = TempNode;
TempNode->r = TemNode1;
TempNode->h = (havMaxValue(getH(TempNode->l), getH(TempNode->r)) + 1);
tempNode2->h = (havMaxValue(getH(tempNode2->l), getH(tempNode2->r)) + 1);
return tempNode2;
}
Node* inNode(Node* tempNode, int value) //Insert New Node
{
if (tempNode == NULL)
return (getNode(value));
if (value < tempNode->d)
tempNode->l = inNode(tempNode->l, value);
else if (value > tempNode->d)
tempNode->r = inNode(tempNode->r, value);
else
return tempNode;
tempNode->h = 1 + havMaxValue(getH(tempNode->l), getH(tempNode->r));
int blnc = getBlnc(tempNode); //Balance Variable
if (blnc > 1 && value < tempNode->l->d)
return rR(tempNode);
if (blnc < -1 && value > tempNode->r->d)
return lR(tempNode);
if (blnc > 1 && value > tempNode->l->d) {
tempNode->l = lR(tempNode->l);
return rR(tempNode);
}
if (blnc < -1 && value < tempNode->r->d) {
tempNode->r = rR(tempNode->r);
return lR(tempNode);
}
return tempNode;
}
/* Deletion */
Node* nodeHavingMinVal(Node* temp) //Mininum Value Node
{
Node* tempNode = temp;
while (tempNode->l != NULL)
tempNode = tempNode->l;
return tempNode;
}
Node* extractNode(Node* tempNode, int key) //DeleteNode
{
if (tempNode == NULL)
return tempNode;
if (key < tempNode->d)
tempNode->l = extractNode(tempNode->l, key);
else if (key > tempNode->d)
tempNode->r = extractNode(tempNode->r, key);
else {
if ((tempNode->l == NULL) || (tempNode->r == NULL)) {
Node* TempNode = tempNode->l ? tempNode->l : tempNode->r;
if (TempNode == NULL) {
TempNode = tempNode;
tempNode = NULL;
}
else
*tempNode = *TempNode;
}
else {
Node* TempNode = nodeHavingMinVal(tempNode->r);
tempNode->d = TempNode->d;
tempNode->r = extractNode(tempNode->r, TempNode->d);
}
}
if (tempNode == NULL)
return tempNode;
tempNode->h = 1 + max(getH(tempNode->l), getH(tempNode->r));
int blnc = getBlnc(tempNode);
if (blnc > 1 && getBlnc(tempNode->l) >= 0)
return rR(tempNode);
if (blnc > 1 && getBlnc(tempNode->l) < 0) {
tempNode->l = lR(tempNode->l);
return rR(tempNode);
}
if (blnc < -1 && getBlnc(tempNode->r) <= 0)
return lR(tempNode);
if (blnc < -1 && getBlnc(tempNode->r) > 0) {
tempNode->r = rR(tempNode->r);
return lR(tempNode);
}
return tempNode;
}
/* Graph Traversal */
void POST(Node* node)
{
if (node == NULL)
return;
POST(node->l);
POST(node->r);
cout << node->d << " ";
}
void IN(Node* node)
{
if (node == NULL)
return;
IN(node->l);
cout << node->d << " ";
IN(node->r);
}
void PRE(Node* node)
{
if (node == NULL)
return;
cout << node->d << " ";
PRE(node->l);
PRE(node->r);
}
int main()
{
Node* root = NULL;
char ch[5];
int num;
int i = 1;
top:
for (; i > 0;) {
cin >> ch[0];
if (ch[0] == 'A') {
int num;
cin >> num;
root = inNode(root, num);
goto top;
}
if (ch[0] == 'D') {
int num;
cin >> num;
root = extractNode(root, num); //Delete Node
if (root == NULL) {
cout << "EMPTY";
break;
}
goto top;
}
cin >> ch[1];
if (ch[0] == 'I' and ch[1] == 'N') {
IN(root);
break;
}
cin >> ch[2];
if (ch[0] == 'P' and ch[1] == 'R' and ch[2] == 'E') {
PRE(root);
break;
}
cin >> ch[3];
if (ch[0] == 'P' and ch[1] == 'O' and ch[2] == 'S' and ch[3] == 'T')
{
POST(root);
break;
}
}
return 0;
}