Dado un árbol de búsqueda binario y un Node objetivo K. La tarea es encontrar el Node con la diferencia mínima absoluta con el valor objetivo dado K.
C++
// Recursive C++ program to find key closest to k
// in given Binary Search Tree.
#include<bits/stdc++.h>
using namespace std;
/* A binary tree node has key, pointer to left child
and a pointer to right child */
struct Node
{
int key;
struct Node* left, *right;
};
/* Utility that allocates a new node with the
given key and NULL left and right pointers. */
struct Node* newnode(int key)
{
struct Node* node = new (struct Node);
node->key = key;
node->left = node->right = NULL;
return (node);
}
// Function to find node with minimum absolute
// difference with given K
// min_diff --> minimum difference till now
// min_diff_key --> node having minimum absolute
// difference with K
void maxDiffUtil(struct Node *ptr, int k, int &min_diff,
int &min_diff_key)
{
if (ptr == NULL)
return ;
// If k itself is present
if (ptr->key == k)
{
min_diff_key = k;
return;
}
// update min_diff and min_diff_key by checking
// current node value
if (min_diff > abs(ptr->key - k))
{
min_diff = abs(ptr->key - k);
min_diff_key = ptr->key;
}
// if k is less than ptr->key then move in
// left subtree else in right subtree
if (k < ptr->key)
maxDiffUtil(ptr->left, k, min_diff, min_diff_key);
else
maxDiffUtil(ptr->right, k, min_diff, min_diff_key);
}
// Wrapper over maxDiffUtil()
int maxDiff(Node *root, int k)
{
// Initialize minimum difference
int min_diff = INT_MAX, min_diff_key = -1;
// Find value of min_diff_key (Closest key
// in tree with k)
maxDiffUtil(root, k, min_diff, min_diff_key);
return min_diff_key;
}
// Driver program to run the case
int main()
{
struct Node *root = newnode(9);
root->left = newnode(4);
root->right = newnode(17);
root->left->left = newnode(3);
root->left->right = newnode(6);
root->left->right->left = newnode(5);
root->left->right->right = newnode(7);
root->right->right = newnode(22);
root->right->right->left = newnode(20);
int k = 18;
cout << maxDiff(root, k);
return 0;
}
Java
// Recursive Java program to find key closest to k
// in given Binary Search Tree.
class solution
{
static int min_diff, min_diff_key;
/* A binary tree node has key, pointer to left child
and a pointer to right child */
static class Node
{
int key;
Node left, right;
};
/* Utility that allocates a new node with the
given key and null left and right pointers. */
static Node newnode(int key)
{
Node node = new Node();
node.key = key;
node.left = node.right = null;
return (node);
}
// Function to find node with minimum absolute
// difference with given K
// min_diff -. minimum difference till now
// min_diff_key -. node having minimum absolute
// difference with K
static void maxDiffUtil(Node ptr, int k)
{
if (ptr == null)
return ;
// If k itself is present
if (ptr.key == k)
{
min_diff_key = k;
return;
}
// update min_diff and min_diff_key by checking
// current node value
if (min_diff > Math.abs(ptr.key - k))
{
min_diff = Math.abs(ptr.key - k);
min_diff_key = ptr.key;
}
// if k is less than ptr.key then move in
// left subtree else in right subtree
if (k < ptr.key)
maxDiffUtil(ptr.left, k);
else
maxDiffUtil(ptr.right, k);
}
// Wrapper over maxDiffUtil()
static int maxDiff(Node root, int k)
{
// Initialize minimum difference
min_diff = 999999999; min_diff_key = -1;
// Find value of min_diff_key (Closest key
// in tree with k)
maxDiffUtil(root, k);
return min_diff_key;
}
// Driver program to run the case
public static void main(String args[])
{
Node root = newnode(9);
root.left = newnode(4);
root.right = newnode(17);
root.left.left = newnode(3);
root.left.right = newnode(6);
root.left.right.left = newnode(5);
root.left.right.right = newnode(7);
root.right.right = newnode(22);
root.right.right.left = newnode(20);
int k = 18;
System.out.println( maxDiff(root, k));
}
}
//contributed by Arnab Kundu
Python3
# Recursive Python program to find key # closest to k in given Binary Search Tree. # Utility that allocates a new node with the # given key and NULL left and right pointers. class newnode: # Constructor to create a new node def __init__(self, data): self.key = data self.left = None self.right = None # Function to find node with minimum # absolute difference with given K # min_diff --> minimum difference till now # min_diff_key --> node having minimum absolute # difference with K def maxDiffUtil(ptr, k, min_diff, min_diff_key): if ptr == None: return # If k itself is present if ptr.key == k: min_diff_key[0] = k return # update min_diff and min_diff_key by # checking current node value if min_diff > abs(ptr.key - k): min_diff = abs(ptr.key - k) min_diff_key[0] = ptr.key # if k is less than ptr->key then move # in left subtree else in right subtree if k < ptr.key: maxDiffUtil(ptr.left, k, min_diff, min_diff_key) else: maxDiffUtil(ptr.right, k, min_diff, min_diff_key) # Wrapper over maxDiffUtil() def maxDiff(root, k): # Initialize minimum difference min_diff, min_diff_key = 999999999999, [-1] # Find value of min_diff_key (Closest # key in tree with k) maxDiffUtil(root, k, min_diff, min_diff_key) return min_diff_key[0] # Driver Code if __name__ == '__main__': root = newnode(9) root.left = newnode(4) root.right = newnode(17) root.left.left = newnode(3) root.left.right = newnode(6) root.left.right.left = newnode(5) root.left.right.right = newnode(7) root.right.right = newnode(22) root.right.right.left = newnode(20) k = 18 print(maxDiff(root, k)) # This code is contributed by PranchalK
C#
using System;
// Recursive C# program to find key closest to k
// in given Binary Search Tree.
public class solution
{
public static int min_diff, min_diff_key;
/* A binary tree node has key, pointer to left child
and a pointer to right child */
public class Node
{
public int key;
public Node left, right;
}
/* Utility that allocates a new node with the
given key and null left and right pointers. */
public static Node newnode(int key)
{
Node node = new Node();
node.key = key;
node.left = node.right = null;
return (node);
}
// Function to find node with minimum absolute
// difference with given K
// min_diff -. minimum difference till now
// min_diff_key -. node having minimum absolute
// difference with K
public static void maxDiffUtil(Node ptr, int k)
{
if (ptr == null)
{
return;
}
// If k itself is present
if (ptr.key == k)
{
min_diff_key = k;
return;
}
// update min_diff and min_diff_key by checking
// current node value
if (min_diff > Math.Abs(ptr.key - k))
{
min_diff = Math.Abs(ptr.key - k);
min_diff_key = ptr.key;
}
// if k is less than ptr.key then move in
// left subtree else in right subtree
if (k < ptr.key)
{
maxDiffUtil(ptr.left, k);
}
else
{
maxDiffUtil(ptr.right, k);
}
}
// Wrapper over maxDiffUtil()
public static int maxDiff(Node root, int k)
{
// Initialize minimum difference
min_diff = 999999999;
min_diff_key = -1;
// Find value of min_diff_key (Closest key
// in tree with k)
maxDiffUtil(root, k);
return min_diff_key;
}
// Driver program to run the case
public static void Main(string[] args)
{
Node root = newnode(9);
root.left = newnode(4);
root.right = newnode(17);
root.left.left = newnode(3);
root.left.right = newnode(6);
root.left.right.left = newnode(5);
root.left.right.right = newnode(7);
root.right.right = newnode(22);
root.right.right.left = newnode(20);
int k = 18;
Console.WriteLine(maxDiff(root, k));
}
}
// This code is contributed by Shrikant13
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