Programación de estructuras de datos: cuente el número de nodos hoja en un árbol binario.
Nodo hoja: un nodo sin nodos secundarios
Es decir, después de comprender la definición de nodo hoja, solo necesitamos atravesar el árbol binario una vez y cumplir esta condición. (El nodo hijo izquierdo y el nodo hijo derecho son NULL) y los nodos se pueden contar.
Entonces, de hecho, este problema se transforma en ¿cómo atravesar un árbol binario? Obviamente, hay muchas formas de atravesar un árbol binario, como: recorrido de preorden (recursivo/no recursivo), recorrido de orden (recursivo/no recursivo), recorrido de postorden (recursivo/no recursivo) , recorrido jerárquico, etc.
A continuación, daré un código de ejemplo para resolver nodos hoja usando dos ideas: recorrido recursivo de preorden y recorrido jerárquico, solo como referencia. Varios otros métodos de implementación tienen ideas similares y usted puede probarlos usted mismo.
El código de muestra es el siguiente: paquete?cn.zifangsky.tree.questions;
import?org.junit.Test;
import?cn.zifangsky.queue.LinkQueue;
import?cn.zifangsky.tree.BinaryTreeNode;
/** *?Encontrar el número de nodos hoja en el árbol binario*?@author?Administrator * */
public ?class?Question2?{
/**
?*?Obtenga el número de nodos hoja mediante un recorrido recursivo de preorden
?*?@param?root
?*?@return
?*/
public?int?getNumberOfLeavesByPreOrder(BinaryTreeNode?root){
if(root ?==?null){
return?0;
}else{
if(root.getLeft()? ==?null?&&? root.getRight()?==?null){?//Nodo hoja
return?1;
}else{
return?getNumberOfLeavesByPreOrder(root .getLeft())?+?getNumberOfLeavesByPreOrder(root.getRight());
}
}
}
/* *
?*?Utilice el recorrido jerárquico para obtener el número de nodos hoja de un árbol binario
?*?
? *?@Complejidad del tiempo?O(n)
?*?@param?root
?*/
public?int?getNumberOfLeavesByQueue(BinaryTreeNode?root ){
int? count?=?0;?//Número total de nodos hoja
LinkQueue
if(root?!=? null){
queue.enQueue(root);
}
while?(!queue .isEmpty())?{
BinaryTreeNode?temp?=?(BinaryTreeNode)?queue.deQueue();
//Nodo hoja: un nodo donde se encuentran el nodo secundario izquierdo y el nodo secundario derecho son NULL
if( temp.getLeft()?==?null?&&?temp.getRight()?==?null){
count++;
}else{
if(temp.getLeft()?!=?null){
queue.enQueue(temp.getLeft());
}
if( temp.getRight()?=?null){
queue.enQueue(temp.getRight());
}
}
}
return?count;
}
/**
?*?Caso de prueba
?*/
@Test
public?void?testMethods(){
/**
?*?Utilice una cola para construir un árbol binario para realizar pruebas
?*?1
?*23
?*?4?5?6 ? 7
?*8?9?
?*/
LinkQueue
BinaryTreeNode?root?=?new?BinaryTreeNode(1);?//Nodo raíz
queue.enQueue(root);
BinaryTreeNode?temp? = ?null;
for(int?i=2;i<10;i=i+2){
BinaryTreeNode?tmpNode1?=?new?BinaryTreeNode(i);
BinaryTreeNode?tmpNode2?=?new?BinaryTreeNode(i+1);
temp?=?(BinaryTreeNode)?queue.deQueue();
temp .setLeft(tmpNode1);
temp.setRight(tmpNode2);
if(i?!=?4)
queue.enQueue(tmpNode1) ;
queue.enQueue(tmpNode2);
}
System.out.println("El número de nodos hoja es: "?+?getNumberOfLeavesByPreOrder( root) );
System.out.println("El número de nodos hoja es: "?+?getNumberOfLeavesByQueue(root));
}
}
La salida del código de prueba es la siguiente: el número de nodos hoja es: 5
El número de nodos hoja es: 5
Adjunto:
Nodo de árbol binario BinaryTreeNode Definición: paquete?cn.zifangsky.tree;
público?clase?BinaryTreeNode?{
privado?int?data;?/ /?data
private?BinaryTreeNode?left;?//Nodo secundario izquierdo
private?BinaryTreeNode?right;?//Nodo secundario derecho
public? BinaryTreeNode(int?data)?{
this.data?=?data;
}
public?BinaryTreeNode(int?data,?BinaryTreeNode?left ,?BinaryTreeNode?right)?{
this.data?=?data;
this.left?=?left;
this.right?= ?correcto;
}
public?int?getData()?{
return?data;
}
public?void?setData(int? datos)?{
this.data?=?data;
}
public?BinaryTreeNode?getLeft()?{
return?left;
}
public?void?setLeft(BinaryTreeNode?left)?{
this.left?=?left;
}
¿público?BinaryTreeNode?getRight()?{
return?right;
}
¿público?void? setRight(BinaryTreeNode?right)?{
this.right?=?right;
}
}
La definición de cola LinkQueue ：paquete?cn.zifangsky.queue;
import?cn.zifangsky.linkedlist.SinglyNode;
/** *?Cola basada en lista enlazada individualmente*?@autor? zifangsky *?@param?
public?class?LinkQueue
private?SinglyNode?frontNode;?// Equipo Primer nodo
private?SinglyNode?rearNode;?//nodo de cola de cola
public?LinkQueue()?{
frontNode?=? null ;
rearNode?=?null;
}
/**
?*? ¿La cola de retorno está vacía
?*?@Complejidad del tiempo?O(1)
?*?@return
?*/
public?boolean?isEmpty (){
retorno?(frontNode?==?null);
}
/**
?*?Retorno Número de elementos almacenados en la cola
?*?@Complejidad del tiempo?O(n)
?*?@return
?*/
public?int?size(){
int?length?=?0;
SinglyNode?currentNode?=?frontNode;
while?(currentNode?!=?null)?{
length++;
currentNode?=?currentNode.getNext();
}< / p>
return?length;
}
/**
?*?Enqueue: inserta datos al final de la lista enlazada
?*?@Complejidad del tiempo?O(1)
?*?@param?data
?*/
public?void ?enQueue(K?datos){
SinglyNode
if(rearNode?!=?null){
rearNode.setNext(newNode);
}
rearNode?=?newNode;
if(frontNode?==?null){
frontNode?=?rearNode ;
}
}
/**
?*?Dequeue: elimina el nodo de encabezado
?*?@Complejidad del tiempo?O(1)
?*?@return
?*/
public?Object?deQueue(){
if(isEmpty()){
throw?new?RuntimeException("¿Cola? ¡Vacía!");
}else{
Objeto?resultado?=?frontNode.getData();
if(frontNode?==?rearNode){
frontNode?=?null;
rearNode ?=?null;
}else{
frontNode?=?frontNode.getNext();
}
devolver ?resultado ;
}
}
}
La definición de nodo singleNode: paquete?cn.zifangsky.linkedlist;
/** *?Definición de lista enlazada individualmente*?@author?zifangsky *?@param?
public?class?SinglyNode
private?K?data;?//?data
private?SinglyNode?next;?//?El siguiente nodo de este nodo
public?SinglyNode(K?data)?{
this.data?=?data;
}
public?SinglyNode(K?data ,? SinglyNode?next)?{
this.data?=?data;
this.next?=?next;
}
public?K?getData()?{
return?data;
}
public?void?setData(K?data )? {
this.data?=?data;
}
public?SinglyNode?getNext()?{
return?next;
}
public?void?setNext(SinglyNode?next)?{
this.next?=?next ;
}
@Override
público?String?toSt
anillo()?{
return?"SinglyNode?[data="?+?data?+?"]";
}
}p>