Dado un árbol binario y un valor clave (Node), encuentre el valor mínimo y máximo para ese valor clave en particular.
- Node de valor mínimo : Node con el mayor dato menor o igual que el valor clave.
- Node de valor límite : Node con los datos más pequeños mayores o iguales que el valor clave.
Por ejemplo, consideremos el árbol binario a continuación:
C++
// Program to find ceil of a given value in BST
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has key, left child and right child */
class node {
public:
int key;
node* left;
node* right;
};
/* Helper function that allocates a new node with the given key and
NULL left and right pointers.*/
node* newNode(int key)
{
node* Node = new node();
Node->key = key;
Node->left = NULL;
Node->right = NULL;
return (Node);
}
// Function to find ceil of a given input in BST. If input is more
// than the max key in BST, return -1
int Ceil(node* root, int input)
{
// Base case
if (root == NULL)
return -1;
// We found equal key
if (root->key == input)
return root->key;
// If root's key is smaller, ceil must be in right subtree
if (root->key < input)
return Ceil(root->right, input);
// Else, either left subtree or root has the ceil value
int ceil = Ceil(root->left, input);
return (ceil >= input) ? ceil : root->key;
}
// Driver program to test above function
int main()
{
node* root = newNode(8);
root->left = newNode(4);
root->right = newNode(12);
root->left->left = newNode(2);
root->left->right = newNode(6);
root->right->left = newNode(10);
root->right->right = newNode(14);
for (int i = 0; i < 16; i++)
cout << i << " " << Ceil(root, i) << endl;
return 0;
}
// This code is contributed by rathbhupendra
C
// Program to find ceil of a given value in BST
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has key, left child and right child */
struct node {
int key;
struct node* left;
struct node* right;
};
/* Helper function that allocates a new node with the given key and
NULL left and right pointers.*/
struct node* newNode(int key)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->key = key;
node->left = NULL;
node->right = NULL;
return (node);
}
// Function to find ceil of a given input in BST. If input is more
// than the max key in BST, return -1
int Ceil(struct node* root, int input)
{
// Base case
if (root == NULL)
return -1;
// We found equal key
if (root->key == input)
return root->key;
// If root's key is smaller, ceil must be in right subtree
if (root->key < input)
return Ceil(root->right, input);
// Else, either left subtree or root has the ceil value
int ceil = Ceil(root->left, input);
return (ceil >= input) ? ceil : root->key;
}
// Driver program to test above function
int main()
{
struct node* root = newNode(8);
root->left = newNode(4);
root->right = newNode(12);
root->left->left = newNode(2);
root->left->right = newNode(6);
root->right->left = newNode(10);
root->right->right = newNode(14);
for (int i = 0; i < 16; i++)
printf("%d %d\n", i, Ceil(root, i));
return 0;
}
Java
// Java program to find ceil of a given value in BST
class Node {
int data;
Node left, right;
Node(int d)
{
data = d;
left = right = null;
}
}
class BinaryTree {
Node root;
// Function to find ceil of a given input in BST.
// If input is more than the max key in BST,
// return -1
int Ceil(Node node, int input)
{
// Base case
if (node == null) {
return -1;
}
// We found equal key
if (node.data == input) {
return node.data;
}
// If root's key is smaller,
// ceil must be in right subtree
if (node.data < input) {
return Ceil(node.right, input);
}
// Else, either left subtree or root
// has the ceil value
int ceil = Ceil(node.left, input);
return (ceil >= input) ? ceil : node.data;
}
// Driver Code
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(8);
tree.root.left = new Node(4);
tree.root.right = new Node(12);
tree.root.left.left = new Node(2);
tree.root.left.right = new Node(6);
tree.root.right.left = new Node(10);
tree.root.right.right = new Node(14);
for (int i = 0; i < 16; i++) {
System.out.println(i + " " + tree.Ceil(tree.root, i));
}
}
}
// This code has been contributed by Mayank Jaiswal
Python
# Python program to find ceil of a given value in BST # A Binary tree node class Node: # Constructor to create a new node def __init__(self, data): self.key = data self.left = None self.right = None # Function to find ceil of a given input in BST. If input # is more than the max key in BST, return -1 def ceil(root, inp): # Base Case if root == None: return -1 # We found equal key if root.key == inp : return root.key # If root's key is smaller, ceil must be in right subtree if root.key < inp: return ceil(root.right, inp) # Else, either left subtree or root has the ceil value val = ceil(root.left, inp) return val if val >= inp else root.key # Driver program to test above function root = Node(8) root.left = Node(4) root.right = Node(12) root.left.left = Node(2) root.left.right = Node(6) root.right.left = Node(10) root.right.right = Node(14) for i in range(16): print "% d % d" %(i, ceil(root, i)) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
using System;
// C# program to find ceil of a given value in BST
public class Node {
public int data;
public Node left, right;
public Node(int d)
{
data = d;
left = right = null;
}
}
public class BinaryTree {
public static Node root;
// Function to find ceil of a given input in BST. If input is more
// than the max key in BST, return -1
public virtual int Ceil(Node node, int input)
{
// Base case
if (node == null) {
return -1;
}
// We found equal key
if (node.data == input) {
return node.data;
}
// If root's key is smaller, ceil must be in right subtree
if (node.data < input) {
return Ceil(node.right, input);
}
// Else, either left subtree or root has the ceil value
int ceil = Ceil(node.left, input);
return (ceil >= input) ? ceil : node.data;
}
// Driver program to test the above functions
public static void Main(string[] args)
{
BinaryTree tree = new BinaryTree();
BinaryTree.root = new Node(8);
BinaryTree.root.left = new Node(4);
BinaryTree.root.right = new Node(12);
BinaryTree.root.left.left = new Node(2);
BinaryTree.root.left.right = new Node(6);
BinaryTree.root.right.left = new Node(10);
BinaryTree.root.right.right = new Node(14);
for (int i = 0; i < 16; i++) {
Console.WriteLine(i + " " + tree.Ceil(root, i));
}
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript program to find ceil
// of a given value in BST
class Node
{
constructor(x) {
this.data = x;
this.left = null;
this.right = null;
}
}
let root;
// Function to find ceil of
// a given input in BST.
// If input is more than the max
// key in BST,
// return -1
function Ceil(node,input)
{
// Base case
if (node == null) {
return -1;
}
// We found equal key
if (node.data == input) {
return node.data;
}
// If root's key is smaller,
// ceil must be in right subtree
if (node.data < input) {
return Ceil(node.right, input);
}
// Else, either left subtree or root
// has the ceil value
let ceil = Ceil(node.left, input);
return (ceil >= input) ? ceil : node.data;
}
// Driver Code
root =new Node(8)
root.left =new Node(4)
root.right =new Node(12)
root.left.left =new Node(2)
root.left.right =new Node(6)
root.right.left =new Node(10)
root.right.right =new Node(14)
for (let i = 0; i < 16; i++) {
document.write(i + " " + Ceil(root, i)+"<br>");
}
// This code is contributed by unknown2108
</script>
C++
// Program to find floor of a given value in BST
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has key, left child and right child */
class node
{
public:
int key;
node *left;
node *right;
};
/* Helper function that allocates a new node with the given key and
NULL left and right pointers.*/
node *newNode(int key)
{
node *Node = new node();
Node->key = key;
Node->left = NULL;
Node->right = NULL;
return (Node);
}
// Function to find floor of a given input in BST. If input is more
// than the min key in BST, return -1
int Floor(node *root, int input)
{
// Base case
if (root == NULL)
return -1;
// We found equal key
if (root->key == input)
return root->key;
// If root's key is larger, floor must be in left subtree
if (root->key > input)
return Floor(root->left, input);
// Else, either right subtree or root has the floor value
else{
int floor = Floor(root->right, input);
// exception for -1 because it is being returned in base case
return (floor<=input && floor!=-1)? floor : root->key;
}
}
// Driver program to test above function
int main()
{
node *root = newNode(8);
root->left = newNode(4);
root->right = newNode(12);
root->left->left = newNode(2);
root->left->right = newNode(6);
root->right->left = newNode(10);
root->right->right = newNode(14);
for (int i = 0; i < 16; i++)
cout << i << " " << Floor(root, i) << endl;
return 0;
}
// This code is contributed by rathbhupendra
C++
// C++ program to find floor and ceil of a given key in BST
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has key, left child and right child */
struct Node {
int data;
Node *left, *right;
Node(int value)
{
data = value;
left = right = NULL;
}
};
// Helper function to find floor and ceil of a given key in BST
void floorCeilBSTHelper(Node* root, int key, int& floor, int& ceil)
{
while (root) {
if (root->data == key) {
ceil = root->data;
floor = root->data;
return;
}
if (key > root->data) {
floor = root->data;
root = root->right;
}
else {
ceil = root->data;
root = root->left;
}
}
return;
}
// Display the floor and ceil of a given key in BST.
// If key is less than the min key in BST, floor will be -1;
// If key is more than the max key in BST, ceil will be -1;
void floorCeilBST(Node* root, int key)
{
// Variables 'floor' and 'ceil' are passed by reference
int floor = -1, ceil = -1;
floorCeilBSTHelper(root, key, floor, ceil);
cout << key << ' ' << floor << ' ' << ceil << '\n';
}
// Driver program to test above function
int main()
{
Node* root = new Node(8);
root->left = new Node(4);
root->right = new Node(12);
root->left->left = new Node(2);
root->left->right = new Node(6);
root->right->left = new Node(10);
root->right->right = new Node(14);
for (int i = 0; i < 16; i++)
floorCeilBST(root, i);
return 0;
}
Java
// Java program to find floor and ceil
// of a given key in BST
import java.io.*;
// A binary tree node has key,
// left child and right child
class Node
{
int data;
Node left, right;
Node(int d)
{
data = d;
left = right = null;
}
}
class BinaryTree{
Node root;
int floor;
int ceil;
// Helper function to find floor and
// ceil of a given key in BST
public void floorCeilBSTHelper(Node root,
int key)
{
while (root != null)
{
if (root.data == key)
{
ceil = root.data;
floor = root.data;
return;
}
if (key > root.data)
{
floor = root.data;
root = root.right;
}
else
{
ceil = root.data;
root = root.left;
}
}
return;
}
// Display the floor and ceil of a
// given key in BST. If key is less
// than the min key in BST, floor
// will be -1; If key is more than
// the max key in BST, ceil will be -1;
public void floorCeilBST(Node root, int key)
{
// Variables 'floor' and 'ceil'
// are passed by reference
floor = -1;
ceil = -1;
floorCeilBSTHelper(root, key);
System.out.println(key + " " +
floor + " " + ceil);
}
// Driver code
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(8);
tree.root.left = new Node(4);
tree.root.right = new Node(12);
tree.root.left.left = new Node(2);
tree.root.left.right = new Node(6);
tree.root.right.left = new Node(10);
tree.root.right.right = new Node(14);
for(int i = 0; i < 16; i++)
{
tree.floorCeilBST(tree.root, i);
}
}
}
// This code is contributed by RohitOberoi
Python3
# Python3 program to find floor and # ceil of a given key in BST # A binary tree node has key, #. left child and right child class Node: def __init__(self, x): self.data = x self.left = None self.right = None # Helper function to find floor and # ceil of a given key in BST def floorCeilBSTHelper(root, key): global floor, ceil while (root): if (root.data == key): ceil = root.data floor = root.data return if (key > root.data): floor = root.data root = root.right else: ceil = root.data root = root.left # Display the floor and ceil of a given # key in BST. If key is less than the min # key in BST, floor will be -1; If key is # more than the max key in BST, ceil will be -1; def floorCeilBST(root, key): global floor, ceil # Variables 'floor' and 'ceil' # are passed by reference floor = -1 ceil = -1 floorCeilBSTHelper(root, key) print(key, floor, ceil) # Driver code if __name__ == '__main__': floor, ceil = -1, -1 root = Node(8) root.left = Node(4) root.right = Node(12) root.left.left = Node(2) root.left.right = Node(6) root.right.left = Node(10) root.right.right = Node(14) for i in range(16): floorCeilBST(root, i) # This code is contributed by mohit kumar 29
C#
// C# program to find floor and ceil
// of a given key in BST
using System;
// A binary tree node has key,
// left child and right child
public class Node
{
public int data;
public Node left, right;
public Node(int d)
{
data = d;
left = right = null;
}
}
public class BinaryTree{
public static Node root;
int floor;
int ceil;
// Helper function to find floor and
// ceil of a given key in BST
public int floorCeilBSTHelper(Node root, int key)
{
while (root != null)
{
if (root.data == key)
{
ceil = root.data;
floor = root.data;
return 0;
}
if (key > root.data)
{
floor = root.data;
root = root.right;
}
else
{
ceil = root.data;
root = root.left;
}
}
return 0;
}
// Display the floor and ceil of a
// given key in BST. If key is less
// than the min key in BST, floor
// will be -1; If key is more than
// the max key in BST, ceil will be -1;
public void floorCeilBST(Node root, int key)
{
// Variables 'floor' and 'ceil'
// are passed by reference
floor = -1;
ceil = -1;
floorCeilBSTHelper(root, key);
Console.WriteLine(key + " " + floor +
" " + ceil);
}
// Driver code
static public void Main()
{
BinaryTree tree = new BinaryTree();
BinaryTree.root = new Node(8);
BinaryTree.root.left = new Node(4);
BinaryTree.root.right = new Node(12);
BinaryTree.root.left.left = new Node(2);
BinaryTree.root.left.right = new Node(6);
BinaryTree.root.right.left = new Node(10);
BinaryTree.root.right.right = new Node(14);
for(int i = 0; i < 16; i++)
{
tree.floorCeilBST(BinaryTree.root, i);
}
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Javascript program to find floor and ceil
// of a given key in BST
// A binary tree node has key,
// left child and right child
class Node
{
constructor(d)
{
this.data = d;
this.left = null;
this.right = null;
}
}
var root = null;
var floor;
var ceil;
// Helper function to find floor and
// ceil of a given key in BST
function floorCeilBSTHelper(root, key)
{
while (root != null)
{
if (root.data == key)
{
ceil = root.data;
floor = root.data;
return 0;
}
if (key > root.data)
{
floor = root.data;
root = root.right;
}
else
{
ceil = root.data;
root = root.left;
}
}
return 0;
}
// Display the floor and ceil of a
// given key in BST. If key is less
// than the min key in BST, floor
// will be -1; If key is more than
// the max key in BST, ceil will be -1;
function floorCeilBST(root, key)
{
// Variables 'floor' and 'ceil'
// are passed by reference
floor = -1;
ceil = -1;
floorCeilBSTHelper(root, key);
document.write(key + " " + floor +
" " + ceil + "<br>");
}
// Driver code
root = new Node(8);
root.left = new Node(4);
root.right = new Node(12);
root.left.left = new Node(2);
root.left.right = new Node(6);
root.right.left = new Node(10);
root.right.right = new Node(14);
for(var i = 0; i < 16; i++)
{
floorCeilBST(root, i);
}
// This code is contributed by rrrtnx.
</script>
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