Dados dos valores n1 y n2 (donde n1 < n2) y un puntero raíz a un árbol de búsqueda binario. Imprime todas las claves del árbol en el rango n1 a n2. es decir, imprime todos los Nodes n tales que n1<=n<=n2 yn es una clave de BST dada. Imprime todas las claves en orden creciente.
Requisitos previos: recorrido de Morris | Árboles binarios enhebrados
El recorrido en orden utiliza recursividad o pila/cola que consume espacio O(n). Pero hay una manera eficiente de hacer un recorrido de árbol en orden utilizando Morris Traversal que se basa en árboles binarios enhebrados. El recorrido de Morris no usa recursividad ni pila/cola y simplemente almacena información importante en los punteros NULL desperdiciados. El recorrido de Morris consume memoria extra constante O(1) ya que no usa recursividad ni pila/cola. Por lo tanto, utilizaremos el recorrido de Morris para realizar un recorrido en orden en el algoritmo presentado en este tutorial para imprimir claves de un BST en un rango determinado, lo cual es eficiente en términos de memoria.
El concepto de árboles binarios subprocesos es simple en el sentido de que almacenan información útil en los punteros NULL desperdiciados. En un árbol binario normal con n Nodes, n+1 punteros NULL desperdician memoria.
Acercarse:Morris Traversal es una muy buena técnica eficiente en memoria para hacer un recorrido de árbol sin usar pila o recursividad en memoria constante O(1) basada en árboles binarios enhebrados. El recorrido de Morris se puede utilizar para resolver problemas en los que se utilizan recorridos de árboles en orden, especialmente en estadísticas de orden, por ejemplo , K- ésimo elemento más grande en BST , K-ésimo elemento más pequeño en BST , etc. Por lo tanto, aquí es donde el recorrido de Morris sería útil como un método más eficiente para hacer en orden recorrido en el espacio constante O (1) sin usar ninguna pila o recursividad.
Algoritmo
1) Initialize Current as root.
2) While current is not NULL :
2.1) If current has no left child
a) Check if current lies between n1 and n2.
1)If so, then visit the current node.
b)Otherwise, Move to the right child of current.
3) Else, here we have 2 cases:
a) Find the inorder predecessor of current node.
Inorder predecessor is the right most node
in the left subtree or left child itself.
b) If the right child of the inorder predecessor is NULL:
1) Set current as the right child of its inorder predecessor.
2) Move current node to its left child.
c) Else, if the threaded link between the current node
and it's inorder predecessor already exists :
1) Set right pointer of the inorder predecessor as NULL.
2) Again check if current node lies between n1 and n2.
a)If so, then visit the current node.
3)Now move current to it's right child.
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP code to print BST keys in given Range in
// constant space using Morris traversal.
#include <bits/stdc++.h>
using namespace std;
struct node {
int data;
struct node *left, *right;
};
// Function to print the keys in range
void RangeTraversal(node* root,
int n1, int n2)
{
if (!root)
return;
node* curr = root;
while (curr) {
if (curr->left == NULL)
{
// check if current node
// lies between n1 and n2
if (curr->data <= n2 &&
curr->data >= n1)
{
cout << curr->data << " ";
}
curr = curr->right;
}
else {
node* pre = curr->left;
// finding the inorder predecessor-
// inorder predecessor is the right
// most in left subtree or the left
// child, i.e in BST it is the
// maximum(right most) in left subtree.
while (pre->right != NULL &&
pre->right != curr)
pre = pre->right;
if (pre->right == NULL)
{
pre->right = curr;
curr = curr->left;
}
else {
pre->right = NULL;
// check if current node lies
// between n1 and n2
if (curr->data <= n2 &&
curr->data >= n1)
{
cout << curr->data << " ";
}
curr = curr->right;
}
}
}
}
// Helper function to create a new node
node* newNode(int data)
{
node* temp = new node;
temp->data = data;
temp->right = temp->left = NULL;
return temp;
}
// Driver Code
int main()
{
/* Constructed binary tree is
4
/ \
2 7
/ \ / \
1 3 6 10
*/
node* root = newNode(4);
root->left = newNode(2);
root->right = newNode(7);
root->left->left = newNode(1);
root->left->right = newNode(3);
root->right->left = newNode(6);
root->right->right = newNode(10);
RangeTraversal(root, 4, 12);
return 0;
}
Java
// Java code to print BST keys in given Range in
// constant space using Morris traversal.
class GfG {
static class node {
int data;
node left, right;
}
// Function to print the keys in range
static void RangeTraversal(node root, int n1, int n2)
{
if (root == null)
return;
node curr = root;
while (curr != null) {
if (curr.left == null)
{
// check if current node
// lies between n1 and n2
if (curr.data <= n2 && curr.data >= n1)
{
System.out.print(curr.data + " ");
}
curr = curr.right;
}
else {
node pre = curr.left;
// finding the inorder predecessor-
// inorder predecessor is the right
// most in left subtree or the left
// child, i.e in BST it is the
// maximum(right most) in left subtree.
while (pre.right != null && pre.right != curr)
pre = pre.right;
if (pre.right == null)
{
pre.right = curr;
curr = curr.left;
}
else {
pre.right = null;
// check if current node lies
// between n1 and n2
if (curr.data <= n2 && curr.data >= n1)
{
System.out.print(curr.data + " ");
}
curr = curr.right;
}
}
}
}
// Helper function to create a new node
static node newNode(int data)
{
node temp = new node();
temp.data = data;
temp.right = null;
temp.left = null;
return temp;
}
// Driver Code
public static void main(String[] args)
{
/* Constructed binary tree is
4
/ \
2 7
/ \ / \
1 3 6 10
*/
node root = newNode(4);
root.left = newNode(2);
root.right = newNode(7);
root.left.left = newNode(1);
root.left.right = newNode(3);
root.right.left = newNode(6);
root.right.right = newNode(10);
RangeTraversal(root, 4, 12);
}
}
Python3
# Python3 code to print BST keys in given Range # in constant space using Morris traversal. # Helper function to create a new node class newNode: # Constructor to create a new node def __init__(self, data): self.data = data self.left = None self.right = None # Function to print the keys in range def RangeTraversal(root, n1, n2): if root == None: return curr = root while curr: if curr.left == None: # check if current node lies # between n1 and n2 if curr.data <= n2 and curr.data >= n1: print(curr.data, end = " ") curr = curr.right else: pre = curr.left # finding the inorder predecessor- # inorder predecessor is the right # most in left subtree or the left # child, i.e in BST it is the # maximum(right most) in left subtree. while (pre.right != None and pre.right != curr): pre = pre.right if pre.right == None: pre.right = curr; curr = curr.left else: pre.right = None # check if current node lies # between n1 and n2 if curr.data <= n2 and curr.data >= n1: print(curr.data, end = " ") curr = curr.right # Driver Code if __name__ == '__main__': # Constructed binary tree is # 4 # / \ # 2 7 # / \ / \ # 1 3 6 10 root = newNode(4) root.left = newNode(2) root.right = newNode(7) root.left.left = newNode(1) root.left.right = newNode(3) root.right.left = newNode(6) root.right.right = newNode(10) RangeTraversal(root, 4, 12) # This code is contributed by PranchalK
C#
// C# code to print BST keys in given Range in
// constant space using Morris traversal.
using System;
public class GfG
{
public class node
{
public int data;
public node left, right;
}
// Function to print the keys in range
static void RangeTraversal(node root, int n1, int n2)
{
if (root == null)
return;
node curr = root;
while (curr != null)
{
if (curr.left == null)
{
// check if current node
// lies between n1 and n2
if (curr.data <= n2 && curr.data >= n1)
{
Console.Write(curr.data + " ");
}
curr = curr.right;
}
else
{
node pre = curr.left;
// finding the inorder predecessor-
// inorder predecessor is the right
// most in left subtree or the left
// child, i.e in BST it is the
// maximum(right most) in left subtree.
while (pre.right != null && pre.right != curr)
pre = pre.right;
if (pre.right == null)
{
pre.right = curr;
curr = curr.left;
}
else
{
pre.right = null;
// check if current node lies
// between n1 and n2
if (curr.data <= n2 && curr.data >= n1)
{
Console.Write(curr.data + " ");
}
curr = curr.right;
}
}
}
}
// Helper function to create a new node
static node newNode(int data)
{
node temp = new node();
temp.data = data;
temp.right = null;
temp.left = null;
return temp;
}
// Driver Code
public static void Main(String[] args)
{
/* Constructed binary tree is
4
/ \
2 7
/ \ / \
1 3 6 10
*/
node root = newNode(4);
root.left = newNode(2);
root.right = newNode(7);
root.left.left = newNode(1);
root.left.right = newNode(3);
root.right.left = newNode(6);
root.right.right = newNode(10);
RangeTraversal(root, 4, 12);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// JavaScript code to print
// BST keys in given Range in
// constant space using Morris traversal.
class node {
constructor() {
this.data = 0;
this.left = null;
this.right = null;
}
}
// Function to print the keys in range
function RangeTraversal( root , n1 , n2)
{
if (root == null)
return;
var curr = root;
while (curr != null) {
if (curr.left == null)
{
// check if current node
// lies between n1 and n2
if (curr.data <= n2 && curr.data >= n1)
{
document.write(curr.data + " ");
}
curr = curr.right;
}
else {
var pre = curr.left;
// finding the inorder predecessor-
// inorder predecessor is the right
// most in left subtree or the left
// child, i.e in BST it is the
// maximum(right most) in left subtree.
while (pre.right != null && pre.right != curr)
pre = pre.right;
if (pre.right == null)
{
pre.right = curr;
curr = curr.left;
}
else {
pre.right = null;
// check if current node lies
// between n1 and n2
if (curr.data <= n2 && curr.data >= n1)
{
document.write(curr.data + " ");
}
curr = curr.right;
}
}
}
}
// Helper function to create a new node
function newNode(data)
{
temp = new node();
temp.data = data;
temp.right = null;
temp.left = null;
return temp;
}
// Driver Code
/* Constructed binary tree is
4
/ \
2 7
/ \ / \
1 3 6 10
*/
root = newNode(4);
root.left = newNode(2);
root.right = newNode(7);
root.left.left = newNode(1);
root.left.right = newNode(3);
root.right.left = newNode(6);
root.right.right = newNode(10);
RangeTraversal(root, 4, 12);
// This code is contributed by todaysgaurav
</script>
4 6 7 10
Complejidad de Tiempo: O(n)
Espacio Auxiliar: O(1), ya que no se ha tomado ningún espacio extra.
Publicación traducida automáticamente
Artículo escrito por AnishSinghWalia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA