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