Arbre - Axiomes

import java.util.Scanner;

public class tas
{
	public static affarbre aff = new affarbre();
	public static int[] entasser(int tab[], int ip, int indiceFin) // ip pour indice p�re
	{
		int ifg; // indice fils gauche
		int ifd; // indice fils droit
		int inter; // entier intermédiaire pour échanger éventuellement deux valeurs
		int max=ip; // indice du plus grand noeud, au début on suppose que c'est le père
		if ((ip >= 1) && (ip <= indiceFin)) // l'indice du pèe p doit impérativement appartenir au tableau
			{
				ifg=2*ip;
				ifd=2*ip+1;
				if (ifg > indiceFin) // si pas de fils gauche, alors il ne peut pas y avoir de fils droit donc on est sur une feuille
				{
					return tab; // fin de la récursivité, on retourne le tableau
				}
				if (ifd > indiceFin) // si on est en dessous, il y a nécessairement un fils gauche donc il faut tester le fils droit
				{ // seul le fils gauche est présent :
					if (tab[ifg] > tab[ip]) // si l'indice fils gauche est plus grand il va falloir le faire remonter
					{ // il faut faire monter le fils gauche et descendre le père
						inter=tab[ip];
						tab[ip]=tab[ifg];
						tab[ifg]=inter;						
						// comme il n'y a que le fils gauche, la récursivitïé s'arrête là et il est inutile d'enregistrer dans max l'indice du plus grand
						return tab;
					}
					// tout va bien, le père est plus grand que le fils gauche, on renvoie juste le tableau et pas besoin d'enregistrer l'indice du plus grand dans max.
					return tab;
				} // les deux fils sont présents :
				if (tab[ifg] > tab[ifd])
				{
					max=ifg;
				}
				else {
					max=ifd;
				}
				// on compare les deux fils et on met l'indice du noeud qui a la plus grande valeur dans max puis on va comparer avec le père.
				if (tab[ip] < tab[max]) 
				{
					inter=tab[ip];
					tab[ip]=tab[max];
					tab[max]=inter;						
					return entasser(tab,max,indiceFin);	
				}
				return tab;
			} // si on est en dessous alors le père n'appartient pas au tableau alors on renvoit le tableau :
			return tab;
	}
	public static int[] construiretas(int tab[],int indiceFin)
	{
		int i;
		for (i=(indiceFin)/2;i>=1;i--) // on appelle entasser du dernier noeud qui n'est pas une feuille jusqu'� la racine.
		{
			entasser(tab,i,indiceFin);
			aff.setTab(tab);
		}
		return tab;
	}
	public static int[] triertas(int tab[],int indiceFin)
	{
		if (indiceFin == 1) {
			return tab; // si l'indice est de 1 ou si la racine est plus grande que le dernier élément alors on arrête.
		}
		int inter;
		inter=tab[1];
		tab[1]=tab[indiceFin];
		tab[indiceFin]=inter;
		entasser(tab,1,indiceFin-1);
		aff.setTab(tab);
		return triertas(tab,indiceFin-1); // sinon on recommence en décrémentant la taille.
	}
	public static void main(String args[])
	{
		int tab[];
		int i;
		int indiceFin;
		System.out.print('\n');
		System.out.println("Nombre de noeuds de l'arbre ?");
		System.out.println("AVERTISSEMENT : POUR UN AFFICHAGE OPTIMAL, NE PAS METTRE PLUS DE 53 NOEUDS");
		indiceFin = (new Scanner(System.in)).nextInt();
		tab = new int[indiceFin+1];
		for(i=1;i<=indiceFin;i++)
		{ // On saisie toutes les valeurs et on remplit.
			System.out.println("Noeud num " + i);
			tab[i]=(new Scanner(System.in)).nextInt();
		}
		System.out.print('\n');
		System.out.println("Lancement du tri avec construire tas dans 10 secondes...");
		System.out.println("Veuillez patienter. Merci.");
		System.out.print('\n');
		try { Thread.sleep(10000); } catch (InterruptedException e) { }
		System.out.println("TRI AVEC CONSTRUIRE-TAS :");
		tab = construiretas(tab,indiceFin);
		for(i=1;i<=indiceFin;i++)
		{
			System.out.print(tab[i] + " ");
		}
		System.out.print('\n');
		System.out.print('\n');
		System.out.println("Lancement du tri par tas dans 10 secondes...");
		System.out.println("Veuillez patienter. Merci.");
		System.out.print('\n');
		try { Thread.sleep(10000); } catch (InterruptedException e) { }
		System.out.println("TRI PAR TAS :");
		tab = triertas(tab,indiceFin); // on exécute construiretas et on inverse tab[A] avec tab[indiceFin].
		for(i=1;i<=indiceFin;i++)
		{
			System.out.print(tab[i] + " ");
		}
		System.out.print('\n');
	}
}

import java.awt.Color;
import java.awt.Graphics;
import java.lang.Math.*;
import javax.swing.JFrame;

public class affarbre extends JFrame
{
    private static final long serialVersionUID = 1;
    private int[] tab; // le tableau pour dessiner l'arbre
    public void setTab(int...val) // cette petite fonction permet de mettre à jour l'arbre, on change le tableau et on dessine à nouveau
    {
    	    tab = val;
    	    repaint();
    	    try { Thread.sleep(3000); } catch (InterruptedException e) { } // Temps d'attente pour avoir le temps de voir l'arbre évoluer.
    }
    public affarbre(int...arbre) // création de la fenêtre pour dessiner
    {
        tab = arbre;
        setTitle("Arbre"); // Titre de la fenêtre
        setSize(1024,768); // Taille de la fenêtre
        setLocationRelativeTo(null);
        setVisible(true); // Pour rendre visible la fenêtre.
        setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE); // Pour pouvoir fermer la fenêtre.  
    }
    public void paint(Graphics g) // l'algorithme qui dessine un arbre en partant d'un tableau
    {
        super.paint(g);
        int hauteur = (int)(( Math.log((double) tab.length-1))/(Math.log((double) 2)));
        int n=(int) (tab.length - Math.pow(2,hauteur)); // Correspond au nombre de noeuds sur la hauteur h.
        int i=0;
        int y=0;
        int indicetab=tab.length-1;
        int pas=(int) ((1024)/(Math.pow(2,hauteur)+1));
        int x=pas;
        int bordgauche=pas; // Correspond au bord gauche (l'espace entre le bord gauche et le premier noeud)
        while (hauteur >= 0) // on part du bas et on remonte dans la hauteur
        {
        	if (y != 0) { // tout le temps sauf dans le cas où c'est la première fois car pour la hauteur la plus haute on partage l'espace disponible en parties égales
        		n = (int) Math.pow(2,hauteur); // Nombre de noeuds sur la hauteur h.
        		x = bordgauche;
        	}
        	y = (hauteur+2)*33;// on calcule le y par rapport à la hauteur
        	indicetab=indicetab-n+1; // permet de venir sur la première case du tableau qui correpond à la vzleur du premier noeud
        	for (i=1;i<=n;i++) {
        		g.fillOval(x-11,y-7,23,23); // On dessine un noeud
        		if (hauteur > 0) { // Dans toutes les hauteurs sauf la racine on dessine les lignes entre les noeuds
        			if ((i % 2) == 0) {
        				g.drawLine(x,y,(int)(x-(pas/2)),y-33); // i est pair donc la ligne penche à gauche
        			} 
        			else {
        				g.drawLine(x,y,(int)(x+(pas/2)),y-33); // i est impair donc la ligne penche à droite
        			}
        		}
        		g.drawString(tab[indicetab] + "",x,y-7); // On écrit la valeur du noeud, -7 permet d'ajuster correctement l'écriture pour la mettre plus haute sinon elle est cachée par le noeud
        		indicetab=indicetab+1; // On parcout les cases du tableau sur la hauteur donnée
        		x = x+pas; // On n'oublie pas aussi de déplacer les coordonnées x.
        	}
        	indicetab = indicetab-n-1; // On n'oublie pas de mettre l'indicetab en place pour la prochaine hauteur.
        	bordgauche = (int) (bordgauche+(pas/2)); // On augmente le bord.
        	pas = 2*pas; // Le pas suivant sera deux fois plus grand.
        	hauteur = hauteur-1; // On diminue bien sûr la hauteur.
        }
    }
}