Dado un árbol de búsqueda binario (BST), la tarea es imprimir el BST de forma mínima-máxima.
¿Qué es la moda min-max?
Una moda min-max significa que debe imprimir primero el Node máximo, luego el mínimo, luego el segundo máximo, luego el segundo mínimo y así sucesivamente.
Ejemplos:
Input:
100
/ \
20 500
/ \
10 30
\
40
Output: 10 500 20 100 30 40
Input:
40
/ \
20 50
/ \ \
10 35 60
/ /
25 55
Output: 10 60 20 55 25 50 35 40
Acercarse:
- Cree una array en orden [] y almacene el recorrido en orden del árbol de búsqueda binario dado.
- Dado que el recorrido en orden del árbol de búsqueda binaria se ordena de forma ascendente, inicialice i = 0 y j = n – 1 .
- Imprime en orden [i] y actualiza i = i + 1 .
- Imprima enorder[j] y actualice j = j – 1 .
- Repita los pasos 3 y 4 hasta que se hayan impreso todos los elementos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
using namespace std;
// Structure of each node of BST
struct node {
int key;
struct node *left, *right;
};
// A utility function to create a new BST node
node* newNode(int item)
{
node* temp = new node();
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
/* A utility function to insert a new
node with given key in BST */
struct node* insert(struct node* node, int key)
{
/* If the tree is empty, return a new node */
if (node == NULL)
return newNode(key);
/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
/* return the (unchanged) node pointer */
return node;
}
// Function to return the size of the tree
int sizeOfTree(node* root)
{
if (root == NULL) {
return 0;
}
// Calculate left size recursively
int left = sizeOfTree(root->left);
// Calculate right size recursively
int right = sizeOfTree(root->right);
// Return total size recursively
return (left + right + 1);
}
// Utility function to print the
// Min max order of BST
void printMinMaxOrderUtil(node* root, int inOrder[],
int& index)
{
// Base condition
if (root == NULL) {
return;
}
// Left recursive call
printMinMaxOrderUtil(root->left, inOrder, index);
// Store elements in inorder array
inOrder[index++] = root->key;
// Right recursive call
printMinMaxOrderUtil(root->right, inOrder, index);
}
// Function to print the
// Min max order of BST
void printMinMaxOrder(node* root)
{
// Store the size of BST
int numNode = sizeOfTree(root);
// Take auxiliary array for storing
// The inorder traversal of BST
int inOrder[numNode + 1];
int index = 0;
// Function call for printing
// element in min max order
printMinMaxOrderUtil(root, inOrder, index);
int i = 0;
index--;
// While loop for printing elements
// In front last order
while (i < index) {
cout << inOrder[i++] << " "
<< inOrder[index--] << " ";
}
if (i == index) {
cout << inOrder[i] << endl;
}
}
// Driver code
int main()
{
struct node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
printMinMaxOrder(root);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Structure of each node of BST
static class node
{
int key;
node left, right;
};
static int index;
// A utility function to create a new BST node
static node newNode(int item)
{
node temp = new node();
temp.key = item;
temp.left = temp.right = null;
return temp;
}
/* A utility function to insert a new
node with given key in BST */
static node insert(node node, int key)
{
/* If the tree is empty,
return a new node */
if (node == null)
return newNode(key);
/* Otherwise, recur down the tree */
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
/* return the (unchanged) node pointer */
return node;
}
// Function to return the size of the tree
static int sizeOfTree(node root)
{
if (root == null)
{
return 0;
}
// Calculate left size recursively
int left = sizeOfTree(root.left);
// Calculate right size recursively
int right = sizeOfTree(root.right);
// Return total size recursively
return (left + right + 1);
}
// Utility function to print the
// Min max order of BST
static void printMinMaxOrderUtil(node root,
int inOrder[])
{
// Base condition
if (root == null)
{
return;
}
// Left recursive call
printMinMaxOrderUtil(root.left, inOrder);
// Store elements in inorder array
inOrder[index++] = root.key;
// Right recursive call
printMinMaxOrderUtil(root.right, inOrder);
}
// Function to print the
// Min max order of BST
static void printMinMaxOrder(node root)
{
// Store the size of BST
int numNode = sizeOfTree(root);
// Take auxiliary array for storing
// The inorder traversal of BST
int []inOrder = new int[numNode + 1];
// Function call for printing
// element in min max order
printMinMaxOrderUtil(root, inOrder);
int i = 0;
index--;
// While loop for printing elements
// In front last order
while (i < index)
{
System.out.print(inOrder[i++] + " " +
inOrder[index--] + " ");
}
if (i == index)
{
System.out.println(inOrder[i]);
}
}
// Driver code
public static void main(String[] args)
{
node root = null;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
printMinMaxOrder(root);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach # Structure of each node of BST class Node: def __init__(self,key): self.left = None self.right = None self.val = key def insert(root,node): if root is None: root = Node(node) else: if root.val < node: if root.right is None: root.right = Node(node) else: insert(root.right, node) else: if root.left is None: root.left = Node(node) else: insert(root.left, node) # Function to return the size of the tree def sizeOfTree(root): if root == None: return 0 # Calculate left size recursively left = sizeOfTree(root.left) # Calculate right size recursively right = sizeOfTree(root.right); # Return total size recursively return (left + right + 1) # Utility function to print the # Min max order of BST def printMinMaxOrderUtil(root, inOrder, index): # Base condition if root == None: return # Left recursive call printMinMaxOrderUtil(root.left, inOrder, index) # Store elements in inorder array inOrder[index[0]] = root.val index[0] += 1 # Right recursive call printMinMaxOrderUtil(root.right, inOrder, index) # Function to print the # Min max order of BST def printMinMaxOrder(root): # Store the size of BST numNode = sizeOfTree(root); # Take auxiliary array for storing # The inorder traversal of BST inOrder = [0] * (numNode + 1) index = 0 # Function call for printing # element in min max order ref = [index] printMinMaxOrderUtil(root, inOrder, ref) index = ref[0] i = 0; index -= 1 # While loop for printing elements # In front last order while (i < index): print (inOrder[i], inOrder[index], end = ' ') i += 1 index -= 1 if i == index: print(inOrder[i]) # Driver Code root = Node(50) insert(root, 30) insert(root, 20) insert(root, 40) insert(root, 70) insert(root, 60) insert(root, 80) printMinMaxOrder(root) # This code is contributed by Sadik Ali
C#
// C# implementation of the approach
using System;
class GFG
{
// Structure of each node of BST
class node
{
public int key;
public node left, right;
};
static int index;
// A utility function to create a new BST node
static node newNode(int item)
{
node temp = new node();
temp.key = item;
temp.left = temp.right = null;
return temp;
}
/* A utility function to insert a new
node with given key in BST */
static node insert(node node, int key)
{
/* If the tree is empty,
return a new node */
if (node == null)
return newNode(key);
/* Otherwise, recur down the tree */
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
/* return the (unchanged) node pointer */
return node;
}
// Function to return the size of the tree
static int sizeOfTree(node root)
{
if (root == null)
{
return 0;
}
// Calculate left size recursively
int left = sizeOfTree(root.left);
// Calculate right size recursively
int right = sizeOfTree(root.right);
// Return total size recursively
return (left + right + 1);
}
// Utility function to print the
// Min max order of BST
static void printMinMaxOrderUtil(node root,
int []inOrder)
{
// Base condition
if (root == null)
{
return;
}
// Left recursive call
printMinMaxOrderUtil(root.left, inOrder);
// Store elements in inorder array
inOrder[index++] = root.key;
// Right recursive call
printMinMaxOrderUtil(root.right, inOrder);
}
// Function to print the
// Min max order of BST
static void printMinMaxOrder(node root)
{
// Store the size of BST
int numNode = sizeOfTree(root);
// Take auxiliary array for storing
// The inorder traversal of BST
int []inOrder = new int[numNode + 1];
// Function call for printing
// element in min max order
printMinMaxOrderUtil(root, inOrder);
int i = 0;
index--;
// While loop for printing elements
// In front last order
while (i < index)
{
Console.Write(inOrder[i++] + " " +
inOrder[index--] + " ");
}
if (i == index)
{
Console.WriteLine(inOrder[i]);
}
}
// Driver code
public static void Main(String[] args)
{
node root = null;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
printMinMaxOrder(root);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the approach
// Structure of each node of BST
class node
{
constructor()
{
this.key = 0;
this.left = null;
this.right = null;
}
};
var index = 0;
// A utility function to create a new BST node
function newNode(item)
{
var temp = new node();
temp.key = item;
temp.left = temp.right = null;
return temp;
}
// A utility function to insert a new
// node with given key in BST
function insert(node, key)
{
/* If the tree is empty,
return a new node */
if (node == null)
return newNode(key);
/* Otherwise, recur down the tree */
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
/* return the (unchanged) node pointer */
return node;
}
// Function to return the size of the tree
function sizeOfTree(root)
{
if (root == null)
{
return 0;
}
// Calculate left size recursively
var left = sizeOfTree(root.left);
// Calculate right size recursively
var right = sizeOfTree(root.right);
// Return total size recursively
return (left + right + 1);
}
// Utility function to print the
// Min max order of BST
function printMinMaxOrderUtil(root, inOrder)
{
// Base condition
if (root == null)
{
return;
}
// Left recursive call
printMinMaxOrderUtil(root.left, inOrder);
// Store elements in inorder array
inOrder[index++] = root.key;
// Right recursive call
printMinMaxOrderUtil(root.right, inOrder);
}
// Function to print the
// Min max order of BST
function printMinMaxOrder(root)
{
// Store the size of BST
var numNode = sizeOfTree(root);
// Take auxiliary array for storing
// The inorder traversal of BST
var inOrder = Array(numNode+1);
// Function call for printing
// element in min max order
printMinMaxOrderUtil(root, inOrder);
var i = 0;
index--;
// While loop for printing elements
// In front last order
while (i < index)
{
document.write(inOrder[i++] + " " +
inOrder[index--] + " ");
}
if (i == index)
{
document.write(inOrder[i]);
}
}
// Driver code
var root = null;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
printMinMaxOrder(root);
// This code is contributed by noob2000
</script>
Producción:
20 80 30 70 40 60 50
Publicación traducida automáticamente
Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA