Algoritmo Basico

Algoritmo Basico

• Tamaño (número de nodos)
• Profundidad de un nodo
• Altura
• Recorridos
• Euler
• Pre-, in- y post-orden
• Suponemos árboles binarios para simplifica

Clase Nodo binario

Class NodoB {
Object d;
NodoB izq;
NodoB der;
NodoB() {this(null);}
NodoB(Object o) {this(o,null,null);}
NodoB(Object o, NodoB i, NodoB d)
{d=o; izq=i; der=d;}
static int size ( NodoB a){...;}
static int height (NodoB a){...;}
void preorder (NodoB a){...;}
void inorder (NodoB a){...;}
void postorder (NodoB a){...;}
}

Clase Árbol binario

protected NodoB raiz;
ArbolB() {raiz=null;}
ArbolB(Object o){raiz=new NodoB(o);}
public int size()
{return NodoB.size(raiz);}
public int height()
{return NodoB.height(raiz);}
public void preorder ()
p p {if (raiz!=null) raiz.preorder();}
public void inorder ()
{if (raiz!=null) raiz.inorder();}
public void postorder ()
{if (raiz!=null) raiz.postorder();}
}

 Tamaño

static int size (NodoB a){
if (a==null)
return 0;
else
return 1+size(a.izq)+size(a.der);
}

Altura

 
static int height (NodoB a){
if (a==null)
return (-1);
else
return 1+Math.max(height(a.izq),
height(a.der));
}