Árbol binario

Solo disponible en BuenasTareas
  • Páginas : 2 (463 palabras )
  • Descarga(s) : 0
  • Publicado : 13 de marzo de 2012
Leer documento completo
Vista previa del texto
ARBOL BINARIO CONCEPTO…

un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre"binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno.



Losárboles de expresión…

Los árboles de expresión representan el código en una estructura de datos similar a un árbol, donde cada nodo es una expresión; por ejemplo, una llamada a un método o unaoperación binaria como x < y.

El código representado en árboles de expresión se puede compilar y ejecutar. Esto permite realizar cambios dinámicos en código ejecutable, ejecutar consultas LINQ en variasbases de datos y crear consultas dinámicas.



Construir un árbol de expresión
En esta sección, vamos a analizar expresiones infijas y a construir sus correspondientes árboles de expresión. Porejemplo, la expresión (3+7)*9 da como resultado el árbol siguiente:
[pic]
Ten en cuenta que hemos simplificado el diagrama eliminando los nombres de los atributos.
El analizador que vamos a escribirtrabaja con expresiones que incluyen números, paréntesis y los operadores + y *. Damos por hecho que la cadena de entrada ya se ha introducido en una lista de Python. La lista de elementospara (3+7)*9 es la siguiente:
['(', 3, '+', 7, ')', '*', 9, 'end'] 


Recorrido de un árbol
Podemos recorrer un árbol de expresión y mostrar los resultados de la siguiente manera:
Def mostrarArbol(arbol):   if arbol == None: return 
  print arbol.datos, 
  mostrarArbol(arbol.izquierdo) 
  mostrarArbol(arbol.derecho) 
En otras palabras, para mostrar un árbol primero hay que mostrar el contenido dela raíz, después el subárbol izquierdo entero y seguidamente el subárbol derecho entero. Esta forma de recorrer un árbol se denomina preorden, porque el contenido de la raíz aparece antes que el...
tracking img