Colas

Árboles
Organización Jerárquica con Árboles
Un árbol es un grupo finito de nodos, donde uno de esos nodos sirve como raíz y el resto de los nodos se organizan debajo de la raíz de una formajerárquica. Un nodo que referencia un nodo debajo suyo es un nodo padre. De forma similar, un nodo referenciado por un nodo encima de él, es un nodo hijo. Los nodos sin hijos, son nodos hoja. Un nodopodría ser un padre e hijo, o un nodo hijo y un nodo hoja.

Un nodo padre podría referenciar tantos hijos como sea necesario. En muchas situaciones, los nodos padre sólo referencian un máximo de dosnodos hijos. Los árboles basados en dichos nodos son conocidos como arboles binarios. La siguiente figura representa un árbol binario que almacena siete palabras en orden alfabético.

Insertar nodos,borrar nodos, y atravesar los nodos en árboles binarios o de otros tipos se realiza mediante la recursión (vea el capítulo siguiente). Por brevedad, no entraremos en los algoritmos recursisvos deinserción, borrado y movimiento por los nodos. En su lugar, presentaré el código fuente de una aplicación de contaje de palabras para demostrar la inserción y el movimiento por los nodos. Este códigoutiliza inserción de nodos para crear un árbol binario, donde cada nodo contiene una palabra y un contador de ocurrencias de esa palabra, y muestra estas palabras y contadores en orden alfabéticomediante una variante del algoritmo de movimiento por árboles move-left-examine-node-move-right:

// WC.java

import java.io.*;

class TreeNode {
String word; // Word beingstored.
int count = 1; // Count of words seen in text.
TreeNode left; // Left subtree reference.
TreeNode right; // Right subtree reference.public TreeNode (String word) {
this.word = word;
left = right = null;
}

public void insert (String word) {
int status =...