Dado un árbol binario. La tarea es encontrar el elemento máximo y mínimo en un árbol binario sin usar recursividad, pila o cola, es decir, la complejidad del espacio debe ser O(1).
Ejemplos:
Input : 12 / \ 13 10 / \ 14 15 / \ / \ 21 24 22 23 Output : Max element : 24 Min element : 10 Input : 12 / \ 19 82 / / \ 41 15 95 \ / / \ 2 21 7 16 Output : Max element : 95 Min element : 2
Requisito previo: Recorrido de árbol en orden sin recursividad y sin pila
Enfoque:
1. Inicialice la corriente como raíz
2. Lleve a la variable max y min
3. Mientras que la corriente no es NULL
- Si el actual no tiene hijo izquierdo
- Actualice la variable max y min con los datos actuales si es necesario
- Ir a la derecha, es decir, actual = actual->derecha
- Más
- Hacer actual como el hijo derecho del
Node más a la derecha en el subárbol izquierdo actual - Ir a este hijo izquierdo, es decir, actual = actual->izquierda
- Hacer actual como el hijo derecho del
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program find maximum and minimum element #include <bits/stdc++.h> using namespace std; // A Tree node struct Node { int key; struct Node *left, *right; }; // Utility function to create a new node Node* newNode(int key) { Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return (temp); } // Function to print a maximum and minimum element // in a tree without recursion without stack void printMinMax(Node* root) { if (root == NULL) { cout << "Tree is empty"; return; } Node* current = root; Node* pre; // Max variable for storing maximum value int max_value = INT_MIN; // Min variable for storing minimum value int min_value = INT_MAX; while (current != NULL) { // If left child does nor exists if (current->left == NULL) { max_value = max(max_value, current->key); min_value = min(min_value, current->key); current = current->right; } else { // Find the inorder predecessor of current pre = current->left; while (pre->right != NULL && pre->right != current) pre = pre->right; // Make current as the right child // of its inorder predecessor if (pre->right == NULL) { pre->right = current; current = current->left; } // Revert the changes made in the 'if' part to // restore the original tree i.e., fix the // right child of predecessor else { pre->right = NULL; max_value = max(max_value, current->key); min_value = min(min_value, current->key); current = current->right; } // End of if condition pre->right == NULL } // End of if condition current->left == NULL } // End of while // Finally print max and min value cout << "Max Value is : " << max_value << endl; cout << "Min Value is : " << min_value << endl; } // Driver Code int main() { /* 15 / \ 19 11 / \ 25 5 / \ / \ 17 3 23 24 Let us create Binary Tree as shown above */ Node* root = newNode(15); root->left = newNode(19); root->right = newNode(11); root->right->left = newNode(25); root->right->right = newNode(5); root->right->left->left = newNode(17); root->right->left->right = newNode(3); root->right->right->left = newNode(23); root->right->right->right = newNode(24); // Function call for printing a max // and min element in a tree printMinMax(root); return 0; }
Java
// Java program find maximum and minimum element class GFG { // A Tree node static class Node { int key; Node left, right; }; // Utility function to create a new node static Node newNode(int key) { Node temp = new Node(); temp.key = key; temp.left = temp.right = null; return (temp); } // Function to print a maximum and minimum element // in a tree without recursion without stack static void printMinMax(Node root) { if (root == null) { System.out.print("Tree is empty"); return; } Node current = root; Node pre; // Max variable for storing maximum value int max_value = Integer.MIN_VALUE; // Min variable for storing minimum value int min_value = Integer.MAX_VALUE; while (current != null) { // If left child does nor exists if (current.left == null) { max_value = Math.max(max_value, current.key); min_value = Math.min(min_value, current.key); current = current.right; } else { // Find the inorder predecessor of current pre = current.left; while (pre.right != null && pre.right != current) pre = pre.right; // Make current as the right child // of its inorder predecessor if (pre.right == null) { pre.right = current; current = current.left; } // Revert the changes made in the 'if' part to // restore the original tree i.e., fix the // right child of predecessor else { pre.right = null; max_value = Math.max(max_value, current.key); min_value = Math.min(min_value, current.key); current = current.right; } // End of if condition pre.right == null } // End of if condition current.left == null } // End of while // Finally print max and min value System.out.print("Max Value is : " + max_value + "\n"); System.out.print("Min Value is : " + min_value + "\n"); } // Driver Code public static void main(String[] args) { /* 15 / \ 19 11 / \ 25 5 / \ / \ 17 3 23 24 Let us create Binary Tree as shown above */ Node root = newNode(15); root.left = newNode(19); root.right = newNode(11); root.right.left = newNode(25); root.right.right = newNode(5); root.right.left.left = newNode(17); root.right.left.right = newNode(3); root.right.right.left = newNode(23); root.right.right.right = newNode(24); // Function call for printing a max // and min element in a tree printMinMax(root); } } // This code is contributed by Rajput-Ji
Python3
# Python program find maximum and minimum element from sys import maxsize INT_MAX = maxsize INT_MIN = -maxsize # A Tree node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Function to print a maximum and minimum element # in a tree without recursion without stack def printMinMax(root: Node): if root is None: print("Tree is empty") return current = root pre = Node(0) # Max variable for storing maximum value max_value = INT_MIN # Min variable for storing minimum value min_value = INT_MAX while current is not None: # If left child does nor exists if current.left is None: max_value = max(max_value, current.key) min_value = min(min_value, current.key) current = current.right else: # Find the inorder predecessor of current pre = current.left while pre.right is not None and pre.right != current: pre = pre.right # Make current as the right child # of its inorder predecessor if pre.right is None: pre.right = current current = current.left # Revert the changes made in the 'if' part to # restore the original tree i.e., fix the # right child of predecessor else: pre.right = None max_value = max(max_value, current.key) min_value = min(min_value, current.key) current = current.right # End of if condition pre->right == NULL # End of if condition current->left == NULL # End of while # Finally print max and min value print("Max value is :", max_value) print("Min value is :", min_value) # Driver Code if __name__ == "__main__": # /* 15 # / \ # 19 11 # / \ # 25 5 # / \ / \ # 17 3 23 24 # Let us create Binary Tree as shown # above */ root = Node(15) root.left = Node(19) root.right = Node(11) root.right.left = Node(25) root.right.right = Node(5) root.right.left.left = Node(17) root.right.left.right = Node(3) root.right.right.left = Node(23) root.right.right.right = Node(24) # Function call for printing a max # and min element in a tree printMinMax(root) # This code is contributed by # sanjeev2552
C#
// C# program find maximum and minimum element using System; class GFG { // A Tree node class Node { public int key; public Node left, right; }; // Utility function to create a new node static Node newNode(int key) { Node temp = new Node(); temp.key = key; temp.left = temp.right = null; return (temp); } // Function to print a maximum and minimum element // in a tree without recursion without stack static void printMinMax(Node root) { if (root == null) { Console.Write("Tree is empty"); return; } Node current = root; Node pre; // Max variable for storing maximum value int max_value = int.MinValue; // Min variable for storing minimum value int min_value = int.MaxValue; while (current != null) { // If left child does nor exists if (current.left == null) { max_value = Math.Max(max_value, current.key); min_value = Math.Min(min_value, current.key); current = current.right; } else { // Find the inorder predecessor of current pre = current.left; while (pre.right != null && pre.right != current) pre = pre.right; // Make current as the right child // of its inorder predecessor if (pre.right == null) { pre.right = current; current = current.left; } // Revert the changes made in the 'if' part to // restore the original tree i.e., fix the // right child of predecessor else { pre.right = null; max_value = Math.Max(max_value, current.key); min_value = Math.Min(min_value, current.key); current = current.right; } // End of if condition pre.right == null } // End of if condition current.left == null } // End of while // Finally print max and min value Console.Write("Max Value is : " + max_value + "\n"); Console.Write("Min Value is : " + min_value + "\n"); } // Driver Code public static void Main(String[] args) { /* 15 / \ 19 11 / \ 25 5 / \ / \ 17 3 23 24 Let us create Binary Tree as shown above */ Node root = newNode(15); root.left = newNode(19); root.right = newNode(11); root.right.left = newNode(25); root.right.right = newNode(5); root.right.left.left = newNode(17); root.right.left.right = newNode(3); root.right.right.left = newNode(23); root.right.right.right = newNode(24); // Function call for printing a max // and min element in a tree printMinMax(root); } } // This code is contributed by PrinciRaj1992
Javascript
<script> // Javascript program find maximum // and minimum element // A Tree node class Node { constructor() { this.key = 0; this.left = null; this.right = null; } }; // Utility function to create a new node function newNode(key) { var temp = new Node(); temp.key = key; temp.left = temp.right = null; return (temp); } // Function to print a maximum and minimum // element in a tree without recursion // without stack function printMinMax(root) { if (root == null) { document.write("Tree is empty"); return; } var current = root; var pre; // Max variable for storing maximum value var max_value = -1000000000; // Min variable for storing minimum value var min_value = 1000000000; while (current != null) { // If left child does nor exists if (current.left == null) { max_value = Math.max(max_value, current.key); min_value = Math.min(min_value, current.key); current = current.right; } else { // Find the inorder predecessor of current pre = current.left; while (pre.right != null && pre.right != current) pre = pre.right; // Make current as the right child // of its inorder predecessor if (pre.right == null) { pre.right = current; current = current.left; } // Revert the changes made in the 'if' // part to restore the original tree // i.e., fix the right child of predecessor else { pre.right = null; max_value = Math.max(max_value, current.key); min_value = Math.min(min_value, current.key); current = current.right; } // End of if condition pre.right == null } // End of if condition current.left == null } // End of while // Finally print max and min value document.write("Max Value is : " + max_value + "<br>"); document.write("Min Value is : " + min_value + "<br>"); } // Driver Code /* 15 / \ 19 11 / \ 25 5 / \ / \ 17 3 23 24 Let us create Binary Tree as shown above */ var root = newNode(15); root.left = newNode(19); root.right = newNode(11); root.right.left = newNode(25); root.right.right = newNode(5); root.right.left.left = newNode(17); root.right.left.right = newNode(3); root.right.right.left = newNode(23); root.right.right.right = newNode(24); // Function call for printing a max // and min element in a tree printMinMax(root); // This code is contributed by noob2000 </script>
Producción :
Max Value is : 25 Min Value is : 3
Complejidad de tiempo: O(N)
Complejidad de espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA