我们有一个二元搜索树和一个数字N。我们的任务是在二元搜索树中找到小于或等于N的最大数字。如果元素存在，打印元素的值，否则打印-1。
null
示例：对于上述给定的二进制搜索树-
Input : N = 24Output :result = 21(searching for 24 will be like-5->12->21)Input : N = 4Output : result = 3(searching for 4 will be like-5->2->3)
我们在下文中讨论了递归方法。 BST中小于或等于N的最大数 这里讨论了一种迭代方法。我们试图找到目标的前身。保留两个指针，一个指向当前节点，另一个用于存储答案。如果当前节点的数据>N，我们将向左移动。在另一种情况下，当当前节点的数据小于N时，当前节点可以是我们的答案（到目前为止），我们向右移动。
C++
// C++ code to find the largest value smaller // than or equal to N #include <bits/stdc++.h> using namespace std; struct Node { int key; Node *left, *right; }; // To create new BST Node Node* newNode( int item) { Node* temp = new Node; temp->key = item; temp->left = temp->right = NULL; return temp; } // To insert a new node in BST Node* insert(Node* node, int key) { // if tree is empty return new node if (node == NULL) return newNode(key); // if key is less then or greater then // node value then 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; } // Returns largest value smaller than or equal to // key. If key is smaller than the smallest, it // returns -1. int findFloor(Node* root, int key) { Node *curr = root, *ans = NULL; while (curr) { if (curr->key <= key) { ans = curr; curr = curr->right; } else curr = curr->left; } if (ans) return ans->key; return -1; } // Driver code int main() { int N = 25; Node* root = insert(root, 19); insert(root, 2); insert(root, 1); insert(root, 3); insert(root, 12); insert(root, 9); insert(root, 21); insert(root, 19); insert(root, 25); printf ( "%d" , findFloor(root, N)); return 0; } |
JAVA
// Java code to find the largest value smaller // than or equal to N class GFG { static class Node { int key; Node left, right; }; // To create new BST Node static Node newNode( int item) { Node temp = new Node(); temp.key = item; temp.left = temp.right = null ; return temp; } // To insert a new node in BST static Node insert(Node node, int key) { // if tree is empty return new node if (node == null ) return newNode(key); // if key is less then or greater then // node value then 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; } // Returns largest value smaller than or equal to // key. If key is smaller than the smallest, it // returns -1. static int findFloor(Node root, int key) { Node curr = root, ans = null ; while (curr != null ) { if (curr.key <= key) { ans = curr; curr = curr.right; } else curr = curr.left; } if (ans != null ) return ans.key; return - 1 ; } // Driver code public static void main(String[] args) { int N = 25 ; Node root = new Node(); insert(root, 19 ); insert(root, 2 ); insert(root, 1 ); insert(root, 3 ); insert(root, 12 ); insert(root, 9 ); insert(root, 21 ); insert(root, 19 ); insert(root, 25 ); System.out.printf( "%d" , findFloor(root, N)); } } /* This code is contributed by PrinciRaj1992 */ |
Python3
# Python3 code to find the largest value # smaller than or equal to N class newNode: def __init__( self , item): self .key = item self .left = None self .right = None # To insert a new node in BST def insert(node, key): # If tree is empty return new node if (node = = None ): return newNode(key) # If key is less then or greater then # node value then recur down the tree if (key < node.key): node.left = insert(node.left, key) elif (key > node.key): node.right = insert(node.right, key) # Return the (unchanged) node pointer return node # Returns largest value smaller than or # equal to key. If key is smaller than # the smallest, it returns -1. def findFloor(root, key): curr = root ans = None while (curr): if (curr.key < = key): ans = curr curr = curr.right else : curr = curr.left if (ans): return ans.key return - 1 # Driver code if __name__ = = '__main__' : N = 25 root = None root = insert(root, 19 ) insert(root, 2 ) insert(root, 1 ) insert(root, 3 ) insert(root, 12 ) insert(root, 9 ) insert(root, 21 ) insert(root, 19 ) insert(root, 25 ) print (findFloor(root, N)) # This code is contributed by bgangwar59 |
C#
// C# code to find the largest value smaller // than or equal to N using System; using System.Collections.Generic; class GFG { public class Node { public int key; public Node left, right; }; // To create new BST Node static Node newNode( int item) { Node temp = new Node(); temp.key = item; temp.left = temp.right = null ; return temp; } // To insert a new node in BST static Node insert(Node node, int key) { // if tree is empty return new node if (node == null ) return newNode(key); // if key is less then or greater then // node value then 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; } // Returns largest value smaller than or equal to // key. If key is smaller than the smallest, it // returns -1. static int findFloor(Node root, int key) { Node curr = root, ans = null ; while (curr != null ) { if (curr.key <= key) { ans = curr; curr = curr.right; } else curr = curr.left; } if (ans != null ) return ans.key; return -1; } // Driver code public static void Main(String[] args) { int N = 25; Node root = new Node(); insert(root, 19); insert(root, 2); insert(root, 1); insert(root, 3); insert(root, 12); insert(root, 9); insert(root, 21); insert(root, 19); insert(root, 25); Console.Write( "{0}" , findFloor(root, N)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript code to find the largest // value smaller than or equal to N class Node { constructor(item) { this .key = item; this .left = null ; this .right = null ; } } // To create new BST Node function newNode(item) { let temp = new Node(item); return temp; } // To insert a new node in BST function insert(node, key) { // If tree is empty return new node if (node == null ) return newNode(key); // If key is less then or greater then // node value then 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; } // Returns largest value smaller than or // equal to key. If key is smaller than // the smallest, it returns -1. function findFloor(root, key) { let curr = root, ans = null ; while (curr != null ) { if (curr.key <= key) { ans = curr; curr = curr.right; } else curr = curr.left; } if (ans != null ) return ans.key; return -1; } // Driver code let N = 25; let root = new Node(N); insert(root, 19); insert(root, 2); insert(root, 1); insert(root, 3); insert(root, 12); insert(root, 9); insert(root, 21); insert(root, 19); insert(root, 25); document.write(findFloor(root, N)); // This code is contributed by divyeshrabadiya07 </script> |
输出：
25
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
