explicar:
La profundidad del árbol binario: una ruta hacia el árbol se forma desde el nodo raíz hasta el nodo (incluido el nodo raíz y hoja) que pasa por el nodo de la hoja a su vez. La longitud del camino más largo es la profundidad del árbol.
Ancho de un árbol binario: cada capa de un árbol binario tiene un cierto número de nodos. El número de nodos en la capa con el mayor número de nodos se llama el ancho del árbol binario.
Idea: implementación recursiva.
1. Cada nodo puede considerarse como un nodo raíz
2. La profundidad del nodo raíz (cualquier nodo) es igual a la profundidad del subárbol izquierda o derecha máxima +1
3. Comience a atravesar desde el nodo raíz. Si atraviesa el nodo de la hoja, la profundidad es 0
// La profundidad del árbol binario public static int profundidad (raíz de nodo) {if (root == null) {return 0; } int dl = profundidad (root.leftchild); int dr = profundidad (root.rightchild); devolver dl> dr? DL+1: DR+1; }2. El ancho del árbol binario
Idea: Agregue un contador durante la secuencia de capa transversal para registrar el número de nodos en cada capa
1. Cuando cada capa está fuera de la cola, el número de nodos en la siguiente capa es en realidad el tamaño () de la cola.
2. Al final de cada capa de transversal, compare el ancho máximo con el número actual de nodos y registre el valor máximo.
public static int width (node root) {if (root == null) return 0; queue <node> q = new LinkedList <Node> (); Q.add (root); int width = 1; // width ints int len = 1; // el número actual de nodos en la capa while (q.size ()> 0) {while (len-> 0) {NEOED = {NEOED = = NOOED = q.poll (); if (node.leftchild! = null) {q.add (node.leftchild);} if (node.rightchild! = null) {q.add (node.rightchild);}} len = q.size (); // después de que el bucle de cada capa termine, registre el número de nodos en la siguiente capa widthm. ancho: q.size ();} return width;}Resumir
Lo anterior se trata de la descripción del lenguaje Java de la profundidad y el ancho del árbol binario. Espero que sea útil para todos. Si hay alguna deficiencia, deje un mensaje para señalarlo. ¡Gracias amigos por su apoyo para este sitio!