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
|
import java.util.*;
class scout
{
public static boolean Test(noeud n, int v, String c)
{
LinkedList s;
noeud m;
boolean res=false;
if (n.listeid.size() == 0)
System.out.println("Noeud "+n.id+" : "+n.val+""+c+""+v);
if (n.type == "MAX")
{
s=n.listeid;
ListIterator it = s.listIterator();
for (int i=1;i<s.size();i++)
{
m = (noeud)it.next();
if (Test(m,v,c))
res= true;
else
res= false;
}
}
else
{
s=n.listeid;
ListIterator it = s.listIterator();
for (int i=1;i<s.size();i++)
{
m = (noeud)it.next();
if (!(Test(m,v,c)))
res= false;
else
res= true;
}
}
return res;
}
public static int Eval(noeud n)
{
LinkedList s;
noeud m;
int v;
if (n.listeid.size() == 0)
{System.out.println("Noeud "+n.id+" : "+n.val); return n.val;}
s=n.listeid;
ListIterator it = s.listIterator();
m = (noeud)it.next();
v = Eval(m);
for (int i=1;i<s.size();i++)
{
m = (noeud)it.next();
if (m.type == "MAX")
{
if (Test(m,v,">"))
v = Eval(m);
}
else
{
if (!(Test(m,v,"=>")))
v = Eval(m);
}
}
return v;
}
public static noeud inputnoeud(int n,int nbne,String typen)
{
int num,val,nbf;
String type;
LinkedList l = new LinkedList();
System.out.println("Noeud "+nbne);
num = nbne;
if (typen=="MAX")
type="MIN";
else
type="MAX";
System.out.println("Type du noeud "+type);
System.out.println("Valeur du noeud");
val = Clavier.lireInt();
System.out.println("Nombre de fils ?");
nbf = Clavier.lireInt();
if (nbf != 0)
{
num = num*10;
for(int i=1;i<nbf+1;i++)
{
num = num+1;
l.add(inputnoeud(nbf,num,type));
}
}
noeud f = new noeud(num,type,val,l);
return f;
}
public static void main (String args[])
{
System.out.println("Racine de l'arbre");
System.out.println("Nombre de fils");
int nb,nbf;
nb = Clavier.lireInt();
LinkedList lc = new LinkedList();
for(int j=1;j<nb+1;j++)
{
lc.add(inputnoeud(1,j,"MAX"));
}
noeud r = new noeud(0,"MAX",0,lc);
System.out.println("Resultat Finale : "+Eval(r));
}
} |
Partager