1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136
|
class Arbre {
//
// champs d'une d'une cellule
//
int val ; // étiquette
Arbre left,right; // fils gauche et droit
private int h ; // hauteur
Arbre (int val) { // Constructeur des feuilles
this.val = val ;
this.left = this.right = null ;
this.h = 1;
}
Arbre (Arbre left, int val, Arbre right) {//Constructeur des noeuds internes
this.val = val ;
this.left = left ;
this.right = right ;
// Contrôle de l'ordre
if ((left != null && left.val >= val) ||
(right != null && right.val <= val))
throw new Error("Valeurs mal fichues :\nval : " + val +
"\ngauche :\n" + catchNull(left) +
"et droite :\n" + catchNull(right));
// calcul de la hauteur du nouvel arbre
int hl = hauteur(left) ;
int hr = hauteur(right) ;
int max = Math.max(hl,hr);
int min = Math.min(hl,hr);
this.h = max + 1;
}
private static int hauteur(Arbre a) { // Pratique
if (a == null)
return 0;
else
return a.h;
}
// Le reste sert à l'affichage des arbres, inutile de le lire.
private static String catchNull(Arbre a) {
if (a == null)
return " arbre vide\n";
else
return a.toString();
}
private int pos;
static private String nchars (char c,int n) {
String r = "" ;
while (n > 0) {
r = r + c ;
n--;
}
return r;
}
static private int ecrire (int l,int c, String [] dsp, String s) {
if (c < dsp[l].length())
throw new Error ("Loose majeure");
dsp[l] = dsp[l] + nchars (' ',c- dsp[l].length()) + s;
return dsp[l].length();
}
private int affiche (int l, int c, String [] dsp) {
if (dsp[l] == null)
dsp[l] = "" ;
if (left != null) {
c = left.affiche(l+1,c,dsp) ;
c = ecrire(l,left.pos,dsp,nchars('_',c-left.pos) + val) ;
} else
c = ecrire(l,c,dsp," " + val) ;
pos = c - ("" + val).length() / 2;
if (right != null) {
int save = c;
c = right.affiche(l+1,c,dsp) ;
ecrire(l,save,dsp,nchars('_',right.pos-save-1));
} else
c = ecrire(l,c,dsp," ");
return c;
}
public String toString () {
String [] dsp = new String[h] ;
affiche(0,0,dsp) ;
String r = "" ;
for (int i = 0 ; i < dsp.length ; i++)
r = r + dsp[i] + "\n";
return r;
}
private static int next = 0;
private static int scanInt(String [] args) {
return Integer.parseInt(args[next++]);
}
private static Arbre scanTree (String [] args) {
String s = args[next] ;
if (s.equals("[")) {
next++;
s = args[next];
if (s.equals("]")) {
next++;
return null;
}
Arbre left = scanTree(args);
s = args[next] ;
if (s.equals("]")) {
next++;
return left;
}
int val = scanInt(args);
Arbre right = scanTree(args);
next++;
return new Arbre(left,val,right);
} else if (s.equals("[]")) {
next++;
return null;
} else
return new Arbre (scanInt(args));
}
public static void main (String [] args) {
Arbre a = scanTree(args);
System.out.print(a);
}
} |
Partager