#include
#include
#include
#include
#include
#include
#include
en utilisant l’espace de noms std ;
#définir pow2(n) (1 << (n))
const entier x = 600 ;
const entier y = 100 ;
struct avl_node {
données int;
int hauteur;
struct avl_node* gauche ;
struct avl_node* à droite ;
} * racine, *temp1;
classe avlTree {
Publique:
int hauteur(avl_node*);
int diff(avl_node*);
avl_node* rr_rotation(avl_node*);
avl_node* ll_rotation(avl_node*);
avl_node* lr_rotation(avl_node*);
avl_node* rl_rotation(avl_node*);
avl_node* balance(avl_node*);
avl_node* balanceTree(avl_node*);
avl_node* insert(avl_node*, int);
void display(avl_node*, int);
void drawNode(avl_node*, int, int, int);
void drawTree(avl_node*, int, int);
void inorder(avl_node*);
void preorder(avl_node*);
void postorder(avl_node*);
int valider(chaîne s);
bool checkInput(chaîne s);
avlArbre()
{
racine = NULL ;
temp1 = NULL ;
}
} ;
int main()
{
int choix, élément, bf;
int c;
chaîne str;
avlArbre avl;
int gd = DETECTER;
int gm;
initwindow(1200, 700, « AVL Tree Graphics »,
0, 0, faux, vrai);
cout << "n----------------------"
<< finl;
cout << "Implémentation de l'arbre AVL"
<< finl;
cout << "n----------------------"
<< finl;
cout << "1.Insérer l'élément dans l'arborescence"
<< finl;
cout << "3.Arbre d'équilibre"
<< finl;
cout << "4. Parcours pré-commande"
<< finl;
cout << "5. Parcours dans l'ordre"
<< finl;
cout << " 6. Traversée PostOrder "
<< finl;
cout << "7.Sortie" << endl;
tandis que (1) {
cout << "nEntrez votre choix : " ;
cin >> choix;
commutateur (choix) {
cas 1:
cout << "Entrez la valeur"
<< "à insérer : " ;
cin >> str;
c = avl.validate(str);
si (c == 100) {
item = std::stoi(
str);
racine = avl.insert(racine, élément);
cleardevice();
settextstyle(10, HORIZ_DIR, 3);
if (racine == NULL) {
cout << "L'arbre est vide"
<< finl;
outtextxy(400, 10,
« L’arbre est vide »);
}
outtextxy(10, 50,
« Avant Rotation : « );
avl.drawTree(racine, x, y);
}
autre
cout << "nttEntrée invalide !"
<< finl;
Pause;
cas 2 :
if (racine == NULL) {
cout << "L'arbre est vide"
<< finl;
}
avl.display(racine, 1);
cleardevice();
avl.drawTree(racine, x, y);
Pause;
cas 3 :
racine = avl.balanceTree(racine);
cleardevice();
settextstyle(
10, HORIZ_DIR, 3);
outtextxy(10, 50,
« Après Rotation : « );
avl.drawTree(racine, x, y);
Pause;
cas 4:
cout << "Précommande Traversée : ";
avl.preorder(root);
cout << endl;
Pause;
cas 5:
cout << "Traversée dans l'ordre :"
<< finl;
avl.inorder(racine);
cout << endl;
Pause;
cas 6 :
cout << "Postorder Traversal :"
<< finl;
avl.postorder(racine);
cout << endl;
Pause;
cas 7 :
sortie(1);
Pause;
défaut:
cout << "Mauvais choix"
<< finl;
}
}
getch();
closegraph();
renvoie 0 ;
}
int avlTree::height(avl_node* temp)
{
entier h = 0;
if (temp != NULL) {
int l_height = hauteur(temp->gauche);
int r_height = hauteur(temp->right);
int max_height = max(l_height, r_height);
h = hauteur_max + 1 ;
}
retourner h;
}
int avlTree::diff(avl_node* temp)
{
int l_height = hauteur(temp->gauche);
int r_height = hauteur(temp->right);
int b_factor = l_height – r_height ;
renvoie b_facteur ;
}
avl_node* avlTree::rr_rotation(
avl_node* parent)
{
avl_node* temp;
temp = parent->droit ;
parent->droit = temp->gauche ;
temp->gauche = parent;
température de retour ;
}
avl_node* avlTree::ll_rotation(
avl_node* parent)
{
avl_node* temp;
temp = parent->gauche ;
parent->gauche = temp->droite ;
temp->droit = parent;
température de retour ;
}
avl_node* avlTree::lr_rotation(
avl_node* parent)
{
avl_node* temp;
temp = parent->gauche ;
parent->gauche = rr_rotation(temp);
return ll_rotation(parent);
}
avl_node* avlTree::rl_rotation(
avl_node* parent)
{
avl_node* temp;
temp = parent->droit ;
parent->droit = ll_rotation(temp);
return rr_rotation(parent);
}
avl_node* avlTree::balance(avl_node* temp)
{
int bal_factor = diff(temp);
si (facteur_bal > 1) {
if (diff(temp->gauche) > 0) {
temp = ll_rotation(temp);
}
autre {
temp = lr_rotation(temp);
}
}
else if (bal_factor < -1) {
if (diff(temp->right) > 0) {
temp = rl_rotation(temp);
}
autre
{
temp = rr_rotation(temp);
}
}
température de retour ;
}
void avlTree::display(avl_node* ptr, niveau int)
{
int je;
if (ptr != NULL) {
display(ptr->right, level + 1);
printf(« n »);
si (ptr == racine)
cout << "Racine -> » ;
pour (i = 0; i < niveau && ptr != racine; i++) {
cout << " ";
}
entier j;
cout << ptr->données ;
display(ptr->gauche, niveau + 1);
}
}
avl_node* avlTree::balanceTree(avl_node* racine)
{
choix int;
if (racine == NULL) {
renvoie NULL ;
}
racine->gauche = balanceTree(racine->gauche);
root->right = balanceTree(root->right);
racine = équilibre(racine);
retour racine;
}
void avlTree::drawNode(avl_node* racine,
entier x, entier y,
int noderatio)
{
int bf = diff(racine);
si (bf > 1 || bf < -1) {
setcolor(12);
outtextxy(600, 10, « Déséquilibré ! »);
cercle(x, y, 25);
setfillstyle(SOLID_FILL, 12);
}
else if (bf == 1 || bf == -1) {
setcolor(14);
cercle(x, y, 25);
setfillstyle(SOLID_FILL, 14);
remplissage(x, y, JAUNE);
}
autre {
setcolor(15);
cercle(x, y, 25);
setfillstyle(SOLID_FILL, 15);
remplissage(x, y, BLANC);
}
char arr[5];
itoa(racine->données, arr, 10);
outtextxy(x, y, arr);
if (root->left != NULL) {
line(x, y, x – 20 * rapport de nœud, y + 70);
drawNode(root->left, x – 20 * noderatio, y + 70,
rapport de nœud – 2);
}
if (root->right != NULL) {
line(x, y, x + 20 * ratio de nœud, y + 70);
drawNode(root->right, x + 20 * noderatio, y + 70,
rapport de nœud – 2);
}
}
void avlTree::drawTree(avl_node* racine, int x, int y)
{
settextstyle(10, HORIZ_DIR, 3);
outtextxy(10, 10, « Arbre »);
outtextxy(20, 600, « Équilibré : « );
cercle(190, 605, 10);
outtextxy(520, 600, « L/R Lourd : « );
setcolor(14);
cercle (700, 605, 10);
setcolor(15);
outtextxy(950, 600, « Critique : « );
setcolor(12);
cercle (1115, 605, 10);
settextstyle(10, HORIZ_DIR, 2);
drawNode(racine, x, y, 8);
}
avl_node* avlTree::insert(
avl_node* racine, valeur int)
{
if (racine == NULL) {
racine = nouveau nœud_avl;
racine->données = valeur ;
racine->gauche = NULL;
root->right = NULL;
retour racine;
}
if (valeur < racine->données) {
racine->gauche = insérer(
racine->gauche, valeur);
}
else if (valeur > racine-> données) {
root->right = insert(
racine->droit,…
