Implementación del iterador de avance en BST

Dado un árbol de búsqueda binario, la tarea es implementar un iterador hacia adelante con las siguientes funciones. 

1. curr(): devuelve el puntero al elemento actual.
2. next(): itera hasta el siguiente elemento más pequeño en el árbol de búsqueda binaria.
3. isEnd(): devuelve verdadero si no queda ningún Node para atravesar, de lo contrario, es falso.

El iterador atraviesa el BST en orden ordenado (creciente). Implementaremos el iterador utilizando una estructura de datos de pila .
Inicialización: 

• Crearemos una pila llamada «q» para almacenar los Nodes de BST.
• Cree una variable «curr» e inicialícela con el puntero a la raíz.
• Mientras que «curr» no es NULL 
  • Presione «curr» en la pila ‘q’.
  • Establecer curr = curr -> izquierda

corriente() 

Devuelve el valor en la parte superior de la pila ‘q’. 
Nota: podría arrojar un error de segmentación si la pila está vacía. 
 

Complejidad de tiempo: O(1)

Siguiente() 

• Declare la variable de puntero «curr» que apunta al Node.
• Establecer curr = q.arriba()->derecha.
• Haga estallar el elemento más alto de la pila.
• Mientras que «curr» no es NULL 
  • Presione «curr» en la pila ‘q’.
  • Establezca curr = curr -> izquierda.

Complejidad de tiempo: O(1) en promedio de todas las llamadas. Puede ser O(h) para una sola llamada en el peor de los casos.

envío() 

Devuelve verdadero si la pila «q» está vacía; de lo contrario, devuelve falso. 
 

Complejidad de tiempo: O(1) 
La complejidad del espacio en el peor de los casos para esta implementación de iteradores es O(h). Debe notarse que el 
iterador apunta al elemento superior de la pila.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Node of the binary tree
struct node {
    int data;
    node* left;
    node* right;
    node(int data)
    {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};
 
// Iterator for BST
class bstit {
private:
    // Stack to store the nodes
    // of BST
    stack<node*> q;
 
public:
    // Constructor for the class
    bstit(node* root)
    {
        // Initializing stack
        node* curr = root;
        while (curr != NULL)
            q.push(curr), curr = curr->left;
    }
 
    // Function to return
    // current element iterator
    // is pointing to
    node* curr()
    {
        return q.top();
    }
 
    // Function to iterate to next
    // element of BST
    void next()
    {
        node* curr = q.top()->right;
        q.pop();
        while (curr != NULL)
            q.push(curr), curr = curr->left;
    }
 
    // Function to check if
    // stack is empty
    bool isEnd()
    {
        return !(q.size());
    }
};
 
// Function to iterator to every element
// using iterator
void iterate(bstit it)
{
    while (!it.isEnd())
        cout << it.curr()->data << " ", it.next();
}
 
// Driver code
int main()
{
    node* root = new node(5);
    root->left = new node(3);
    root->right = new node(7);
    root->left->left = new node(2);
    root->left->right = new node(4);
    root->right->left = new node(6);
    root->right->right = new node(8);
 
    // Iterator to BST
    bstit it(root);
 
    // Function to test iterator
    iterate(it);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
// Node of the binary tree
class TreeNode
{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x)
    {
        val = x;
    }
}
 
// Iterator for BST
class BSTIterator{
 
// Stack to store the nodes
// of BST
Stack<TreeNode> s;
 
// Constructor for the class
public BSTIterator(TreeNode root)
{
     
    // Initializing stack
    s = new Stack<>();
    TreeNode curr = root;
     
    while (curr != null)
    {
        s.push(curr);
        curr = curr.left;
    }
}
 
// Function to return
// current element iterator
// is pointing to
TreeNode curr()
{
    return s.peek();
}
 
// Function to iterate to next
// element of BST
public void next()
{
    TreeNode temp = s.peek().right;
    s.pop();
     
    while (temp != null)
    {
        s.push(temp);
        temp = temp.left;
    }
}
 
// Function to check if
// stack is empty
public boolean isEnd()
{
    return !s.isEmpty();
}
 
// Function to iterator to every element
// using iterator
void iterate()
{
    while (isEnd())
    {
        System.out.print(curr().val + " ");
        next();
    }
}
}
 
class BinaryTree{
     
TreeNode root;
 
// Driver code
public static void main(String args[])
{
     
    // Let us construct a tree shown in
    // the above figure
    BinaryTree tree = new BinaryTree();
    tree.root = new TreeNode(5);
    tree.root.left = new TreeNode(3);
    tree.root.right = new TreeNode(7);
    tree.root.left.left = new TreeNode(2);
    tree.root.left.right = new TreeNode(4);
    tree.root.right.left = new TreeNode(6);
    tree.root.right.right = new TreeNode(8);
 
    // Iterator to BST
    BSTIterator it = new BSTIterator(tree.root);
 
    // Function to test iterator
    it.iterate();
}
}
 
// This code is contributed by nobody_cares

# Python 3 implementation of the approach
# Node of the binary tree
class node:
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None
 
# Iterator for BST
class bstit:
    # Stack to store the nodes
    # of BST
    __stack = []
    # Constructor for the class
 
    def __init__(self, root):
 
        # Initializing stack
        curr = root
        while (curr is not None):
            self.__stack.append(curr)
            curr = curr.left
 
    # Function to return
    # current element iterator
    # is pointing to
    def curr(self):
        return self.__stack[-1]
 
    # Function to iterate to next
    # element of BST
    def next(self):
 
        curr = self.__stack[-1].right
        self.__stack.pop()
        while (curr is not None):
            self.__stack.append(curr)
            curr = curr.left
 
    # Function to check if
    # stack is empty
    def isEnd(self):
        return not len(self.__stack)
 
# Function to iterator to every element
# using iterator
def iterate(it):
 
    while (not it.isEnd()):
        print(it.curr().data,end=" ")
        it.next()
 
# Driver code
if __name__ == '__main__':
 
    root = node(5)
    root.left = node(3)
    root.right = node(7)
    root.left.left = node(2)
    root.left.right = node(4)
    root.right.left = node(6)
    root.right.right = node(8)
 
    # Iterator to BST
    it = bstit(root)
 
    # Function to test iterator
    iterate(it)
    print()
# This code is added by Amartya Ghosh

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
// Node of the binary tree
public class TreeNode
{
  public int val;
  public TreeNode left;
  public TreeNode right;
  public TreeNode(int x)
  {
    val = x;
  }
}
 
// Iterator for BST
public class BSTIterator{
 
  // Stack to store the nodes
  // of BST
  Stack<TreeNode> s;
 
  // Constructor for the class
  public BSTIterator(TreeNode root)
  {
 
    // Initializing stack
    s = new Stack<TreeNode>();
    TreeNode curr = root;
 
    while (curr != null)
    {
      s.Push(curr);
      curr = curr.left;
    }
  }
 
  // Function to return
  // current element iterator
  // is pointing to
  TreeNode curr()
  {
    return s.Peek();
  }
 
  // Function to iterate to next
  // element of BST
  public void next()
  {
    TreeNode temp = s.Peek().right;
    s.Pop();
 
    while (temp != null)
    {
      s.Push(temp);
      temp = temp.left;
    }
  }
 
  // Function to check if
  // stack is empty
  public bool isEnd()
  {
    return s.Count!=0;
  }
 
  // Function to iterator to every element
  // using iterator
  public void iterate()
  {
    while (isEnd())
    {
      Console.Write(curr().val + " ");
      next();
    }
  }
}
 
public class BinaryTree{
 
  TreeNode root;
 
  // Driver code
  public static void Main(String []args)
  {
 
    // Let us construct a tree shown in
    // the above figure
    BinaryTree tree = new BinaryTree();
    tree.root = new TreeNode(5);
    tree.root.left = new TreeNode(3);
    tree.root.right = new TreeNode(7);
    tree.root.left.left = new TreeNode(2);
    tree.root.left.right = new TreeNode(4);
    tree.root.right.left = new TreeNode(6);
    tree.root.right.right = new TreeNode(8);
 
    // Iterator to BST
    BSTIterator it = new BSTIterator(tree.root);
 
    // Function to test iterator
    it.iterate();
  }
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Javascript implementation of the approach
 
// Node of the binary tree
class node
{
    constructor(data)
    {
        this.left = null;
        this.right = null;
        this.data = data;
    }
}
 
// Stack to store the nodes
// of BST
let q = [];
 
// Constructor for the class
function bstit(root)
{
     
    // Initializing stack
    let curr = root;
     
    while (curr != null)
    {
        q.push(curr);
        curr = curr.left;
    }
}
 
// Function to return
// current element iterator
// is pointing to
function curr()
{
    return q[q.length - 1];
}
 
// Function to iterate to previous
// element of BST
function next()
{
    let curr = q[q.length - 1].right;
    q.pop();
     
    while (curr != null)
    {
        q.push(curr);
        curr = curr.left;
    }
}
 
// Function to check if
// stack is empty
function isEnd()
{
    return (q.length == 0);
}
 
// Function to test the iterator
function iterate()
{
    while (!isEnd())
    {
        document.write(curr().data + " ");
        next();
    }
}
 
// Driver code
let root = new node(5);
root.left = new node(3);
root.right = new node(7);
root.left.left = new node(2);
root.left.right = new node(4);
root.right.left = new node(6);
root.right.right = new node(8);
 
// Iterator to BST
bstit(root);
 
// Function call to test the iterator
iterate();
 
// This code is contributed by Rajput-Ji
 
</script>

2 3 4 5 6 7 8