Hinge node(nodi cardine)

[marshall86]

Salve ho un programma che mi stampa dei nodi di un albero e poi mi dice quale di questi nodi sono nodi cardine.

Un nodo cardine, per chi non lo sapesse, è un nodo la cui profondità e altezza coincidono.

il codice per determinare i nodi cardine è il seguente:

public int cardine(Nodo u, int x)  // crea un nodo u, inizializza l'altezza sx e dx dello stesso,                          dopo aver fatto la ricorsione
    					// sulle due altezze, aggiunge il nodo alla lista cardine e ritorna l'altezza
    {
        NodoBinPF n = (NodoBinPF)u;
        if(n == null)
            return -1;
        int hsx = cardine(((Nodo) (n.sin)), x + 1);
        int hdx = cardine(((Nodo) (n.des)), x + 1);    
        int high;
        if(hsx >= hdx)
            high = hsx + 1;
        else
            high = hdx + 1;
        if(x == high)
            listaCardine.add(n.info);
            
        return high;
    }

public class Info
{
		public char carattere;
		public int intero;
		public Info(int i, char c)
		{
			this.intero=i;
			this.carattere=c;
		}
		
		public String toString()
		{
			if(this!= null) return "("+intero+","+carattere+")";
			else return "null";
		}
}

L'output del mio programma è :

(0,a)
(1,b)
(2,c)
(3,d)
(4,e)
lista riempita
costruisci l'albero
< null (0,a) null >
< null (1,b) null >
< null (1,a) null >
< (0,a) (1,a) (1,b) >
costruisci l'albero
< null (2,c) null >
< null (3,d) null >
< null (5,c) null >
< (2,c) (5,c) (3,d) >
costruisci l'albero
< null (4,e) null >
< (0,a) (1,a) (1,b) >
< null (5,e) null >
< (4,e) (5,e) (1,a) >
costruisci l'albero
< (2,c) (5,c) (3,d) >
< (4,e) (5,e) (1,a) >
< null (10,c) null >
< (5,c) (10,c) (5,e) >
Lista nodi cardine
(5,c)

non riesco a capire se il grafo ricavato da questi nodi è giusto:

                                                 (10,c)
                            (5,c)                                    (5,e)
                  (2,c)            (3,d)                 (1,a)                (4,e)
                                                     (0,a)      (1,b)

Perchè il nodo (5,c) è un nodo cardine? perchè è l'unico?

spero che qualcuno di voi sappia rispondermi

marshall

[lucke84]

cito da http://it.wikipedia.org/wiki/Albero_binario

"Profondità di un albero: La radice r ha profondità 0, i suoi figli sinistro e destro, hanno profondità 1, i nipoti profondità 2 e cosi via. Quindi se la profondità di un nodo è p i suoi figli non vuoti hanno profondità p+1

Per quanto riguarda l'altezza h di un albero binario è data dalla massima profondità raggiunta dalle sue foglie."

mi sembra che questo rispecchi in effetti quanto rappresenta il nodo (5,c) e solo lui.. tutti gli altri hanno altezze diverse [anche se magari la stessa profondità come il nodo (5,e)]

spero di non aver pasticciato con le definizioni, sono ancora rintronato stamattina