2
J'essaie vraiment de comprendre le bogue dans mon code que j'ai écrit pour AVL tree mais il semble y avoir un bug.Bug dans le code arborescence AVL, structures de données C++
Il appelle les fonctions de rotation, mais quand il se termine rotation il y a plusieurs problèmes:
- racine ne change pas
- seule valeur racine est affichée lorsque traversal est fait dans l'ordre, d'autres valeurs semblent disparaître
J'ai essayé de corriger ce bug depuis 2-3 jours mais je n'arrive pas à le résoudre.
J'adorerais avoir de l'aide de votre part. Je vais attacher le code avec ceci.
/*
insertion
rotations all DONE
level order DONE
deletion
*/
#include <iostream>
#include <queue>
using namespace std;
struct node
{
int data;
int height;
node *left;
node *right;
node()
{
height = 0;
left = right = NULL;
}
};
class AVL
{
public:
node *root;
AVL()
{
root = NULL;
}
// search function
bool search(int num)
{
node *nodePtr = root;
if (root->data == num)
{
cout << "FOUND " << endl;
return true;
}
else
{
while (nodePtr != NULL)
{
if (nodePtr->data < num)
{
nodePtr = nodePtr->right;
}
else if (nodePtr->data > num)
{
nodePtr = nodePtr->left;
}
else
{
cout << "FOUND " << endl;
return true;
}
}
cout << "NOT FOUND " << endl;
return false;
}
}
// inorder
void inorder()
{
inorder(root);
}
// postorder
void postorder()
{
postorder(root);
}
// preorder
void preorder()
{
preorder(root);
}
// inorder utility function
void inorder(node *&nodePtr)
{
if (nodePtr)
{
inorder(nodePtr->left);
cout << nodePtr->data << ", ";
inorder(nodePtr->right);
}
}
// preorder utility function
void preorder(node *&nodePtr)
{
if (nodePtr)
{
cout << nodePtr->data << ", ";
preorder(nodePtr->left);
preorder(nodePtr->right);
}
}
// postorder utility function
void postorder(node *&nodePtr)
{
if (nodePtr)
{
postorder(nodePtr->left);
postorder(nodePtr->right);
cout << nodePtr->data << ", ";
}
}
// returns the number of nodes in the tree
int size(node *&nodePtr)
{
if (!nodePtr)
{
return 0;
}
else
{
return (size(nodePtr->left) + size(nodePtr->right)) + 1;
}
}
// function to check if tree is empty or not
bool isempty()
{
if (root == NULL)
{
return true;
}
else
{
return false;
}
}
// max function to calculate height and also the balance factor
int maximum(int x, int y)
{
if (x>y)
{
return x;
}
else
{
return y;
}
}
// returns the level of the tree
int returnHeight(node *&nodePtr)
{
if (nodePtr == NULL)
{
return 0;
}
else
{
return nodePtr->height;
}
}
// assigning the height to the node
void assignHeightToNode(node *&nodePtr)
{
int left = returnHeight(nodePtr->left);
int right = returnHeight(nodePtr->right);
nodePtr->height = maximum(left, right) + 1;
}
// single left rotate
node *singleLeftRotate(node *&nodePtr)
{
// if (nodePtr==NULL)
// {
// return;
// }
node * b = nodePtr->right;
nodePtr->right = b->left;
b->left = nodePtr;
return b;
}
// single right rotate
node *singleRightRotate(node *&nodePtr)
{
// if (nodePtr==NULL)
// {
// return ;
// }
node * b = nodePtr->left;
nodePtr->left = b->right;
b->right = nodePtr;
assignHeightToNode(nodePtr);
assignHeightToNode(b);
return b;
}
// double left rotate
node *doubleLeft(node *&nodePtr)
{
nodePtr->right = singleRightRotate(nodePtr->right);
return singleLeftRotate(nodePtr);
}
// double right rotate
node *doubleRight(node *&nodePtr)
{
nodePtr->left = singleLeftRotate(nodePtr->left);
return singleRightRotate(nodePtr);
}
// insert function
void insert1(int x)
{
cout << "NOW INSERTING " << x << endl;
insert2(x, root);
}
// insert utility function
void insert2(int &x, node *&nodePtr)
{
if (nodePtr == NULL)
{
node *newNode = new node;
newNode->data = x;
newNode->height = 0;
nodePtr = newNode;
checkRotations(nodePtr, x);
return;
}
else
{
if (x < nodePtr->data)
{
cout << endl << "GOING LEFT " << endl;
insert2(x, nodePtr->left);
}
else if (x > nodePtr->data)
{
cout << endl << "GOING RIGHT " << endl;
insert2(x, nodePtr->right);
}
else if (nodePtr->data == x)
{
cout << "DUPLICATE VALUES NOT ALLOWED " << endl;
return;
}
}
checkRotations(nodePtr, x);
}
// checking if rotations needed
void checkRotations(node *&nodePtr, int &x)
{
assignHeightToNode(nodePtr);
cout << endl << endl << "HEIGHT OF " << nodePtr->data << " IS " << nodePtr->height << endl;
int bf = returnHeight(nodePtr->left) - returnHeight(nodePtr->right);
cout << endl << endl << "BALANCE FACTOR AT NODE " << nodePtr->data << " IS " << bf << endl;
if (bf < -1 || bf > 1)
{
cout << endl << endl << "ROTATION IS HAPPEENING " << endl << endl;
if (x > nodePtr->data)
{
singleLeftRotate(nodePtr);
cout << endl << "ROTATION DONE SINGLE LEFT " << endl;
return;
}
else if (x < nodePtr->data)
{
singleRightRotate(nodePtr);
cout << endl << "ROTATION DONE SINGLE RIGHT " << endl;
return;
}
else if (x < root->data && x > root->left->data)
{
doubleRight(nodePtr);
cout << endl << "ROTATION DONE DOUBLE LEFT " << endl;
return;
}
else if (x > root->data && x < root->right->data)
{
doubleLeft(nodePtr);
cout << endl << "ROTATION DONE DOUBLE LEFT " << endl;
return;
}
}
}
// level order display code
void levelOrderDisplay()
{
levelOrderDisplay2(root);
}
// level order display utility function
void levelOrderDisplay2(node *&nodePtr)
{
if (nodePtr == NULL)
{
cout << "THE TREE IS EMPTY" << endl;
return;
}
queue <node *> displayer;
displayer.push(nodePtr);
while (!displayer.empty())
{
node *currentNode = displayer.front();
cout << currentNode->data << ", ";
if (currentNode->left != NULL)
{
displayer.push(currentNode->left);
}
else if (currentNode->right != NULL)
{
displayer.push(currentNode->right);
}
displayer.pop();
}
}
void rootD()
{
cout << "root is " << root->data << endl;
}
};
int main()
{
AVL tree;
tree.insert1(3);
tree.insert1(2);
tree.insert1(1);
tree.insert1(4);
tree.insert1(5);
tree.insert1(6);
tree.insert1(7);
tree.inorder();
// tree.rootD();
// tree.levelOrderDisplay();
// tree.rootD();
return 0;
}
merci bro: D ... –