Dado un árbol binario y una array de entrada. La tarea es crear un iterador que utilice las funciones next() y hasNext() para realizar un recorrido en orden en el árbol binario.
Ejemplos:
Entrada: 8 Array de entrada = [siguiente(), tieneSiguiente(), siguiente(), siguiente(), siguiente(), tieneSiguiente(), siguiente(), siguiente(), tieneSiguiente()]
/ \
3 9
/ \
2 4
\
5Salida: [2, verdadero, 3, 4, 5, verdadero, 8, 9, falso]
Explicación: De acuerdo con el orden de recorrido, se calcula la respuesta a la array de entrada.
Recorrido en orden = {2, 3, 4, 5, 8, 9}Entrada: 4 Array de entrada = [hasNext(), next(), next(), hasNext()]
/ \
3 2
\
1Salida: [verdadero, 3, 4 verdadero]
Enfoque ingenuo: se necesita una forma de volver al ancestro una vez que llegamos al Node hoja del árbol binario. Se puede usar una estructura de datos Stack para esto.
Algoritmo:
La clase es instanciada
- inicializar la pila
- establecer el Node actual = root
- mientras que actual! = NULL
- agregar corriente a la pila
- actual = actual.izquierda
función hasNext()
SI la pila no está vacía
volver verdadero
MÁS
falso retorno
función siguiente()
- SI la pila está vacía (o hasNext() devuelve falso)
- Lanzar una excepción
- MÁS
- Inicializar actual = stack.top
- Extrae el elemento de la pila
- Si actual.correcto != NULL
- Inicializar siguiente = actual->derecha
- ¡mientras sigue! = NULL
- añadir al lado de la pila
- siguiente = siguiente.izquierda
- corriente de retorno
A continuación se muestra la implementación del enfoque anterior.
Java
// Java Program for above approach import java.util.*; // Structure of a Node class Node { int data; Node left; Node right; Node(int data) { this.data = data; left = right = null; } } // Inorder Iterator class class InorderIterator { private Stack<Node> traversal; InorderIterator(Node root) { traversal = new Stack<Node>(); moveLeft(root); } private void moveLeft(Node current) { while (current != null) { traversal.push(current); current = current.left; } } public boolean hasNext() { return !traversal.isEmpty(); } public Node next() { if (!hasNext()) throw new NoSuchElementException(); Node current = traversal.pop(); if (current.right != null) moveLeft(current.right); return current; } } // Class to Test given set of inputs class Test { // Driver Code public static void main(String args[]) { Node root = new Node(8); root.right = new Node(9); root.left = new Node(3); root.left.left = new Node(2); root.left.right = new Node(4); root.left.right.right = new Node(5); InorderIterator itr = new InorderIterator(root); try { System.out.print(itr.next().data + " "); System.out.print(itr.hasNext() + " "); System.out.print(itr.next().data + " "); System.out.print(itr.next().data + " "); System.out.print(itr.next().data + " "); System.out.print(itr.hasNext() + " "); System.out.print(itr.next().data + " "); System.out.print(itr.next().data + " "); System.out.print(itr.hasNext() + " "); } catch (NoSuchElementException e) { System.out.print("No such element Exists"); } } }
2 true 3 4 5 true 8 9 false
Complejidad de tiempo: O(N), donde N es el número de Nodes en el árbol binario.
Espacio auxiliar: O (N), la pila contendrá todos los elementos N en el peor de los casos.
Enfoque eficiente: Morris Traversal se puede usar para resolver esta pregunta usando un espacio constante. La idea detrás de morris traversal es crear un enlace temporal entre un Node y el Node más a la derecha en su subárbol izquierdo para que el Node antepasado pueda retroceder. Una referencia del Node antepasado se establece en el hijo derecho del Node más a la derecha en su subárbol izquierdo.
Algoritmo:
La clase es instanciada
Inicializar actual = root y rightMost = NULL
función hasNext()
SI actual != NULL
volver verdadero
MÁS
falso retorno
función siguiente()
- IF actual = NULL (o hasNext() devuelve falso)
- Lanzar una excepción
- MÁS
- IF actual.izquierda = NULL
- Inicializar temp = actual
- actual = actual.derecho
- temperatura de retorno
- MÁS
- Inicializar rightMost = actual->izquierda
- while rightMost.right != NULL && rightMost.right != actual
- más a la derecha = más a la derecha. a la derecha
- IF más a la derecha.derecha == NULL
- rightMost.right = actual
- actual = actual.izquierda
- MÁS
- temperatura = corriente
- más a la derecha.derecha = nulo
- actual = actual.derecho
- corriente de retorno
- Vuelve a llamar a la función
A continuación se muestra la implementación del enfoque anterior.
Java
// Java Program for above approach import java.util.*; // Structure of a Node class Node { int data; Node left; Node right; Node(int data) { this.data = data; left = right = null; } } // Inorder Iterator class class InorderIterator { private Node current, rightMost; InorderIterator(Node root) { current = root; rightMost = null; } public boolean hasNext() { return current != null; } public Node next() { if (!hasNext()) throw new NoSuchElementException(); if (current.left == null) { Node temp = current; current = current.right; return temp; } rightMost = current.left; while (rightMost.right != null && rightMost.right != current) rightMost = rightMost.right; if (rightMost.right == null) { rightMost.right = current; current = current.left; } else { rightMost.right = null; Node temp = current; current = current.right; return temp; } return next(); } } class Test { // Driver Code public static void main(String args[]) { Node root = new Node(8); root.right = new Node(9); root.left = new Node(3); root.left.left = new Node(2); root.left.right = new Node(4); root.left.right.right = new Node(5); InorderIterator itr = new InorderIterator(root); try { System.out.print(itr.next().data + " "); System.out.print(itr.hasNext() + " "); System.out.print(itr.next().data + " "); System.out.print(itr.next().data + " "); System.out.print(itr.next().data + " "); System.out.print(itr.hasNext() + " "); System.out.print(itr.next().data + " "); System.out.print(itr.next().data + " "); System.out.print(itr.hasNext() + " "); } catch (NoSuchElementException e) { System.out.print("No such element Exists"); } } }
2 true 3 4 5 true 8 9 false
Complejidad temporal: O(N), donde N es el número de Nodes del árbol binario. Aunque estamos creando enlaces temporales y los Nodes se recorren varias veces (como máximo 3 veces), la complejidad del tiempo sigue siendo lineal.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por gursimar04 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA