Implementando iterador hacia atrás en BST

Posted on by Rudeus Greyrat

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

  1. curr(): devuelve el puntero al elemento actual.
  2. prev(): itera hasta el elemento más grande anterior 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 decreciente. 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 -> derecho

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)

anterior()  

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

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++

// 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->right;
    }
 
    // Function to return
    // current element iterator
    // is pointing to
    node* curr()
    {
        return q.top();
    }
 
    // Function to iterate to previous
    // element of BST
    void prev()
    {
        node* curr = q.top()->left;
        q.pop();
        while (curr != NULL)
            q.push(curr), curr = curr->right;
    }
 
    // Function to check if
    // stack is empty
    bool isEnd()
    {
        return !(q.size());
    }
};
 
// Function to test the iterator
void iterate(bstit it)
{
    while (!it.isEnd())
        cout << it.curr()->data << " ", it.prev();
}
 
// 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 call to test the iterator
    iterate(it);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
// Node of the binary tree
class node {
  int data;
  node left;
  node right;
  node(int data)
  {
    this.data = data;
    left = null;
    right = null;
  }
}
 
// Iterator for BST
class bstit
{
 
  // Stack to store the nodes
  // of BST
  Stack<node> q;
 
  // Constructor for the class
  public bstit(node root)
  {
 
    // Initializing stack
    q = new Stack<>();
    node curr = root;
    while (curr != null) {
      q.add(curr);
      curr = curr.right;
    }
  }
 
  // Function to return
  // current element iterator
  // is pointing to
  node curr()
  {
    return q.peek();
  }
 
  // Function to iterate to previous
  // element of BST
  void prev()
  {
    node curr = q.peek().left;
    q.pop();
    while (curr != null) {
      q.add(curr);
      curr = curr.right;
    }
  }
 
  // Function to check if
  // stack is empty
  boolean isEnd()
  {
    return (q.size() != 0);
  }
 
  // Function to test the iterator
  void iterate(bstit it)
  {
    while (it.isEnd()) {
      System.out.print(it.curr().data);
      System.out.print(" ");
      prev();
    }
 
  }
}
public class GFG
{
 
  // Driver code
  public static void main(String[] args)
  {
    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 = new bstit(root);
 
    // Function call to test the iterator
    it.iterate(it);
 
  }
}
 
// This code is contributed by Rajput-Ji

Python3

# 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.right
 
    # Function to return
    # current element iterator
    # is pointing to
    def curr(self):
        return self.__stack[-1]
 
    # Function to iterate to previous
    # element of BST
    def prev(self):
     
        curr = self.__stack[-1].left
        self.__stack.pop()
        while (curr != None):
            self.__stack.append(curr)
            curr = curr.right
 
    # Function to check if
    # __stack is empty
    def isEnd(self):
        return not len((self.__stack))
 
# Function to test the iterator
def iterate(it):
    while (not it.isEnd()):
        print(it.curr().data,end=" ")
        it.prev()
 
# 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 call to test the iterator
    iterate(it)
    print()
# This code is contributed by Amartya Ghosh

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
// Node of the binary tree
public class node {
  public int data;
  public node left;
  public node right;
 
  public node(int data) {
    this.data = data;
    left = null;
    right = null;
  }
}
 
// Iterator for BST
public class bstit {
 
  // Stack to store the nodes
  // of BST
  Stack<node> q;
 
  // Constructor for the class
  public bstit(node root) {
 
    // Initializing stack
    q = new Stack<node>();
    node curr = root;
    while (curr != null) {
      q.Push(curr);
      curr = curr.right;
    }
  }
 
  // Function to return
  // current element iterator
  // is pointing to
  public node curr() {
    return q.Peek();
  }
 
  // Function to iterate to previous
  // element of BST
  public void prev() {
    node curr = q.Peek().left;
    q.Pop();
    while (curr != null) {
      q.Push(curr);
      curr = curr.right;
    }
  }
 
  // Function to check if
  // stack is empty
  public bool isEnd() {
    return (q.Count != 0);
  }
 
  // Function to test the iterator
  public void iterate(bstit it) {
    while (it.isEnd()) {
      Console.Write(it.curr().data);
      Console.Write(" ");
      prev();
    }
 
  }
}
 
public class GFG {
 
  // Driver code
  public static void Main(String[] args) {
    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 = new bstit(root);
 
    // Function call to test the iterator
    it.iterate(it);
 
  }
}
 
// This code is contributed by Rajput-Ji

Javascript

<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.right;
    }
}
 
// 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 prev()
{
    let curr = q[q.length - 1].left;
    q.pop();
     
    while (curr != null)
    {
        q.push(curr);
        curr = curr.right;
    }
}
 
// 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 + " ");
        prev();
    }
}
 
// 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 divyeshrabadiya07
 
</script>
Producción: 

8 7 6 5 4 3 2

 

Publicación traducida automáticamente

Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *