Dado un recorrido de preorden de un árbol de búsqueda binario. La tarea es imprimir los Nodes de hoja del árbol de búsqueda binaria del pedido previo dado.
Ejemplos:
Input : preorder[] = {890, 325, 290, 530, 965};
Output : 290 530 965
Explanation : Tree represented is,
890
/ \
325 965
/ \
290 530
Input : preorder[] = { 3, 2, 4 };
Output : 2 4
Método 1: (Simple):
La idea es encontrar Iorder, luego recorrer el árbol en orden previo (utilizando recorridos tanto en orden como en orden posterior) y mientras se atraviesan los Nodes de hoja de impresión.
¿Cómo atravesar en orden anticipado usando dos arrays que representan recorridos en orden y preorden?
Iteramos la array de preorden y para cada elemento encontramos ese elemento en la array en orden. Para la búsqueda, podemos usar la búsqueda binaria, ya que el recorrido en orden del árbol de búsqueda binaria siempre está ordenado. Ahora, para cada elemento de la array de preorden, en la búsqueda binaria, establecemos el rango [L, R].
Y cuando L == R, se encuentra el Node hoja. Entonces, inicialmente, L = 0 y R = n – 1 para el primer elemento (es decir, la raíz) de la array de preorden. Ahora, para buscar el elemento en el subárbol izquierdo de la raíz, establezca L = 0 y R = índice de raíz – 1. Además, para todos los elementos del subárbol derecho establezca L = índice de raíz + 1 y R = n -1 .
Recursivamente, sigue esto, hasta que L == R.
A continuación se muestra la implementación de este enfoque:
C++
// C++ program to print leaf node from
// preorder of binary search tree.
#include<bits/stdc++.h>
using namespace std;
// Binary Search
int binarySearch(int inorder[], int l, int r, int d)
{
int mid = (l + r)>>1;
if (inorder[mid] == d)
return mid;
else if (inorder[mid] > d)
return binarySearch(inorder, l, mid - 1, d);
else
return binarySearch(inorder, mid + 1, r, d);
}
// Function to print Leaf Nodes by doing preorder
// traversal of tree using preorder and inorder arrays.
void leafNodesRec(int preorder[], int inorder[],
int l, int r, int *ind, int n)
{
// If l == r, therefore no right or left subtree.
// So, it must be leaf Node, print it.
if(l == r)
{
printf("%d ", inorder[l]);
*ind = *ind + 1;
return;
}
// If array is out of bound, return.
if (l < 0 || l > r || r >= n)
return;
// Finding the index of preorder element
// in inorder array using binary search.
int loc = binarySearch(inorder, l, r, preorder[*ind]);
// Incrementing the index.
*ind = *ind + 1;
// Finding on the left subtree.
leafNodesRec(preorder, inorder, l, loc - 1, ind, n);
// Finding on the right subtree.
leafNodesRec(preorder, inorder, loc + 1, r, ind, n);
}
// Finds leaf nodes from given preorder traversal.
void leafNodes(int preorder[], int n)
{
int inorder[n]; // To store inorder traversal
// Copy the preorder into another array.
for (int i = 0; i < n; i++)
inorder[i] = preorder[i];
// Finding the inorder by sorting the array.
sort(inorder, inorder + n);
// Point to the index in preorder.
int ind = 0;
// Print the Leaf Nodes.
leafNodesRec(preorder, inorder, 0, n - 1, &ind, n);
}
// Driven Program
int main()
{
int preorder[] = { 890, 325, 290, 530, 965 };
int n = sizeof(preorder)/sizeof(preorder[0]);
leafNodes(preorder, n);
return 0;
}
Java
// Java program to print leaf node from
// preorder of binary search tree.
import java.util.*;
class GFG
{
// Binary Search
static int binarySearch(int inorder[], int l,
int r, int d)
{
int mid = (l + r) >> 1;
if (inorder[mid] == d)
return mid;
else if (inorder[mid] > d)
return binarySearch(inorder, l,
mid - 1, d);
else
return binarySearch(inorder,
mid + 1, r, d);
}
// Point to the index in preorder.
static int ind;
// Function to print Leaf Nodes by
// doing preorder traversal of tree
// using preorder and inorder arrays.
static void leafNodesRec(int preorder[],
int inorder[],
int l, int r, int n)
{
// If l == r, therefore no right or left subtree.
// So, it must be leaf Node, print it.
if(l == r)
{
System.out.printf("%d ", inorder[l]);
ind = ind + 1;
return;
}
// If array is out of bound, return.
if (l < 0 || l > r || r >= n)
return;
// Finding the index of preorder element
// in inorder array using binary search.
int loc = binarySearch(inorder, l, r,
preorder[ind]);
// Incrementing the index.
ind = ind + 1;
// Finding on the left subtree.
leafNodesRec(preorder, inorder,
l, loc - 1, n);
// Finding on the right subtree.
leafNodesRec(preorder, inorder,
loc + 1, r, n);
}
// Finds leaf nodes from given preorder traversal.
static void leafNodes(int preorder[], int n)
{
// To store inorder traversal
int inorder[] = new int[n];
// Copy the preorder into another array.
for (int i = 0; i < n; i++)
inorder[i] = preorder[i];
// Finding the inorder by sorting the array.
Arrays.sort(inorder);
// Print the Leaf Nodes.
leafNodesRec(preorder, inorder, 0, n - 1, n);
}
// Driver Code
public static void main(String args[])
{
int preorder[] = { 890, 325, 290, 530, 965 };
int n = preorder.length;
leafNodes(preorder, n);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to print leaf node from # preorder of binary search tree. # Binary Search def binarySearch(inorder, l, r, d): mid = (l + r) >> 1 if (inorder[mid] == d): return mid elif (inorder[mid] > d): return binarySearch(inorder, l, mid - 1, d) else: return binarySearch(inorder, mid + 1, r, d) # Function to print Leaf Nodes by doing # preorder traversal of tree using # preorder and inorder arrays. def leafNodesRec(preorder, inorder, l, r, ind, n): # If l == r, therefore no right or left subtree. # So, it must be leaf Node, print it. if(l == r): print(inorder[l], end = " ") ind[0] = ind[0] + 1 return # If array is out of bound, return. if (l < 0 or l > r or r >= n): return # Finding the index of preorder element # in inorder array using binary search. loc = binarySearch(inorder, l, r, preorder[ind[0]]) # Incrementing the index. ind[0] = ind[0] + 1 # Finding on the left subtree. leafNodesRec(preorder, inorder, l, loc - 1, ind, n) # Finding on the right subtree. leafNodesRec(preorder, inorder, loc + 1, r, ind, n) # Finds leaf nodes from # given preorder traversal. def leafNodes(preorder, n): # To store inorder traversal inorder = [0] * n # Copy the preorder into another array. for i in range(n): inorder[i] = preorder[i] # Finding the inorder by sorting the array. inorder.sort() # Point to the index in preorder. ind = [0] # Print the Leaf Nodes. leafNodesRec(preorder, inorder, 0, n - 1, ind, n) # Driver Code preorder = [890, 325, 290, 530, 965] n = len(preorder) leafNodes(preorder, n) # This code is contributed # by SHUBHAMSINGH10
C#
// C# program to print leaf node from
// preorder of binary search tree.
using System;
class GFG
{
// Binary Search
static int binarySearch(int []inorder, int l,
int r, int d)
{
int mid = (l + r) >> 1;
if (inorder[mid] == d)
return mid;
else if (inorder[mid] > d)
return binarySearch(inorder, l,
mid - 1, d);
else
return binarySearch(inorder,
mid + 1, r, d);
}
// Point to the index in preorder.
static int ind;
// Function to print Leaf Nodes by
// doing preorder traversal of tree
// using preorder and inorder arrays.
static void leafNodesRec(int []preorder,
int []inorder,
int l, int r, int n)
{
// If l == r, therefore no right or left subtree.
// So, it must be leaf Node, print it.
if(l == r)
{
Console.Write("{0} ", inorder[l]);
ind = ind + 1;
return;
}
// If array is out of bound, return.
if (l < 0 || l > r || r >= n)
return;
// Finding the index of preorder element
// in inorder array using binary search.
int loc = binarySearch(inorder, l, r,
preorder[ind]);
// Incrementing the index.
ind = ind + 1;
// Finding on the left subtree.
leafNodesRec(preorder, inorder,
l, loc - 1, n);
// Finding on the right subtree.
leafNodesRec(preorder, inorder,
loc + 1, r, n);
}
// Finds leaf nodes from given preorder traversal.
static void leafNodes(int []preorder, int n)
{
// To store inorder traversal
int []inorder = new int[n];
// Copy the preorder into another array.
for (int i = 0; i < n; i++)
inorder[i] = preorder[i];
// Finding the inorder by sorting the array.
Array.Sort(inorder);
// Print the Leaf Nodes.
leafNodesRec(preorder, inorder, 0, n - 1, n);
}
// Driver Code
public static void Main(String []args)
{
int []preorder = { 890, 325, 290, 530, 965 };
int n = preorder.Length;
leafNodes(preorder, n);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to print leaf node from
// preorder of binary search tree.
// Binary Search
function binarySearch(inorder, l, r, d) {
var mid = parseInt((l + r) / 2);
if (inorder[mid] == d) return mid;
else if (inorder[mid] > d)
return binarySearch(inorder, l, mid - 1, d);
else
return binarySearch(inorder, mid + 1, r, d);
}
// Point to the index in preorder.
var ind = 0;
// Function to print Leaf Nodes by
// doing preorder traversal of tree
// using preorder and inorder arrays.
function leafNodesRec(preorder, inorder, l, r, n) {
// If l == r, therefore no right or left subtree.
// So, it must be leaf Node, print it.
if (l == r) {
document.write(inorder[l] + " ");
ind = ind + 1;
return;
}
// If array is out of bound, return.
if (l < 0 || l > r || r >= n) return;
// Finding the index of preorder element
// in inorder array using binary search.
var loc = binarySearch(inorder, l, r, preorder[ind]);
// Incrementing the index.
ind = ind + 1;
// Finding on the left subtree.
leafNodesRec(preorder, inorder, l, loc - 1, n);
// Finding on the right subtree.
leafNodesRec(preorder, inorder, loc + 1, r, n);
}
// Finds leaf nodes from given preorder traversal.
function leafNodes(preorder, n) {
// To store inorder traversal
var inorder = new Array(n).fill(0);
// Copy the preorder into another array.
for (var i = 0; i < n; i++) inorder[i] = preorder[i];
// Finding the inorder by sorting the array.
inorder.sort();
// Print the Leaf Nodes.
leafNodesRec(preorder, inorder, 0, n - 1, n);
}
// Driver Code
var preorder = [890, 325, 290, 530, 965];
var n = preorder.length;
leafNodes(preorder, n);
</script>
290 530 965
Complejidad de Tiempo: O(n log n)
Espacio Auxiliar: O(n)
Método 2: (usando Stack):
La idea es utilizar la propiedad del árbol de búsqueda binaria y la pila.
Atraviese el arreglo usando dos punteros i y j al arreglo, inicialmente i = 0 y j = 1. Siempre que a[i] > a[j], podemos decir que a[j] es parte de a[i], ya que El recorrido de preorden sigue a Visita -> Izquierda -> Derecha. Entonces, metemos a[i] en la pila.
Para aquellos puntos que violan la regla, comenzamos a extraer elementos de la pila hasta un [i]> elemento superior de la pila y rompemos cuando no lo hace e imprimimos el j -ésimo valor correspondiente.
Algoritmo:
1. Set i = 0, j = 1.
2. Traverse the preorder array.
3. If a[i] > a[j], push a[i] to the stack.
4. Else
While (stack is not empty)
if (a[j] > top of stack)
pop element from the stack;
set found = true;
else
break;
5. if (found == true)
print a[i];
¿Cómo funciona este algoritmo?
Preordenar recorrido transversal en el orden: Visita, Izquierda, Derecha.
Y sabemos que el Node izquierdo de cualquier Node en BST siempre es menor que el Node. Por lo tanto, el recorrido de pedido previo primero atravesará desde la raíz hasta el Node más a la izquierda. Por lo tanto, el pedido anticipado será primero en orden decreciente. Ahora, después del orden decreciente, puede haber un Node que sea mayor o que rompa el orden decreciente. Entonces, puede haber un caso como este:
En el caso 1, 20 es un Node hoja mientras que en el caso 2, 20 no es el Node hoja.
Entonces, nuestro problema es cómo identificar si tenemos que imprimir 20 como un Node hoja o no.
Esto se resuelve usando stack.
Mientras se ejecuta el algoritmo anterior en el caso 1 y el caso 2, cuando i = 2 y j = 3, el estado de una pila será el mismo en ambos casos:
Entonces, el Node 65 sacará 20 y 50 de la pila. Esto se debe a que 65 es el hijo derecho de un Node anterior a 20. Esta información la almacenamos usando la variable encontrada. Entonces, 20 es un Node raíz.
Mientras que en el caso 2, 40 no podrá sacar ningún elemento de la pila. Porque 40 es el Node derecho de un Node que está después de 20. Entonces, 20 no es un Node hoja.
Nota: En el algoritmo, no podremos verificar la condición del Node hoja del Node más a la derecha o el elemento más a la derecha del pedido previo. Entonces, simplemente imprima el Node más a la derecha porque sabemos que siempre será un Node de hoja en el recorrido de preorden.
A continuación se muestra la implementación de este enfoque:
C++
// Stack based C++ program to print leaf nodes
// from preorder traversal.
#include<bits/stdc++.h>
using namespace std;
// Print the leaf node from the given preorder of BST.
void leafNode(int preorder[], int n)
{
stack<int> s;
for (int i = 0, j = 1; j < n; i++, j++)
{
bool found = false;
if (preorder[i] > preorder[j])
s.push(preorder[i]);
else
{
while (!s.empty())
{
if (preorder[j] > s.top())
{
s.pop();
found = true;
}
else
break;
}
}
if (found)
cout << preorder[i] << " ";
}
// Since rightmost element is always leaf node.
cout << preorder[n - 1];
}
// Driver code
int main()
{
int preorder[] = { 890, 325, 290, 530, 965 };
int n = sizeof(preorder)/sizeof(preorder[0]);
leafNode(preorder, n);
return 0;
}
Java
// Stack based Java program to print leaf nodes
// from preorder traversal.
import java.util.*;
class GfG {
// Print the leaf node from the given preorder of BST.
static void leafNode(int preorder[], int n)
{
Stack<Integer> s = new Stack<Integer> ();
for (int i = 0, j = 1; j < n; i++, j++)
{
boolean found = false;
if (preorder[i] > preorder[j])
s.push(preorder[i]);
else
{
while (!s.isEmpty())
{
if (preorder[j] > s.peek())
{
s.pop();
found = true;
}
else
break;
}
}
if (found)
System.out.print(preorder[i] + " ");
}
// Since rightmost element is always leaf node.
System.out.println(preorder[n - 1]);
}
// Driver code
public static void main(String[] args)
{
int preorder[] = { 890, 325, 290, 530, 965 };
int n = preorder.length;
leafNode(preorder, n);
}
}
Python3
# Stack based Python program to print # leaf nodes from preorder traversal. # Print the leaf node from the given # preorder of BST. def leafNode(preorder, n): s = [] i = 0 for j in range(1, n): found = False if preorder[i] > preorder[j]: s.append(preorder[i]) else: while len(s) != 0: if preorder[j] > s[-1]: s.pop(-1) found = True else: break if found: print(preorder[i], end = " ") i += 1 # Since rightmost element is # always leaf node. print(preorder[n - 1]) # Driver code if __name__ == '__main__': preorder = [890, 325, 290, 530, 965] n = len(preorder) leafNode(preorder, n) # This code is contributed by PranchalK
C#
using System;
using System.Collections.Generic;
// Stack based C# program to print leaf nodes
// from preorder traversal.
public class GfG
{
// Print the leaf node from the given preorder of BST.
public static void leafNode(int[] preorder, int n)
{
Stack<int> s = new Stack<int> ();
for (int i = 0, j = 1; j < n; i++, j++)
{
bool found = false;
if (preorder[i] > preorder[j])
{
s.Push(preorder[i]);
}
else
{
while (s.Count > 0)
{
if (preorder[j] > s.Peek())
{
s.Pop();
found = true;
}
else
{
break;
}
}
}
if (found)
{
Console.Write(preorder[i] + " ");
}
}
// Since rightmost element is always leaf node.
Console.WriteLine(preorder[n - 1]);
}
// Driver code
public static void Main(string[] args)
{
int[] preorder = new int[] {890, 325, 290, 530, 965};
int n = preorder.Length;
leafNode(preorder, n);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Stack based Javascript program to print leaf nodes
// from preorder traversal.
// Print the leaf node from the given preorder of BST.
function leafNode(preorder, n)
{
let s = [];
for (let i = 0, j = 1; j < n; i++, j++)
{
let found = false;
if (preorder[i] > preorder[j])
s.push(preorder[i]);
else
{
while (s.length > 0)
{
if (preorder[j] > s[s.length - 1])
{
s.pop();
found = true;
}
else
break;
}
}
if (found)
document.write(preorder[i] + " ");
}
// Since rightmost element is always leaf node.
document.write(preorder[n - 1]);
}
let preorder = [ 890, 325, 290, 530, 965 ];
let n = preorder.length;
leafNode(preorder, n);
// This code is contributed by mukesh07.
</script>
290 530 965
Complejidad de tiempo: O(n)
Nodes de hoja del pedido anticipado de un árbol de búsqueda binario (usando recursividad)
Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA