Inorder предшественник и преемник для данного ключа в BST | Итерационный подход
Опубликовано: 24 Января, 2022
Учитывая BST и ключ. Задача - найти в порядке преемника и предшественника данного ключа. В случае, если одного из предшественников или последователей нет, выведите -1.
Примеры:
Ввод: 50 / / 30 70 / / / / 20 40 60 80 ключ = 65 Выход: Предшественник: 60 Преемник: 70 Ввод: 50 / / 30 70 / / / / 20 40 60 80 ключ = 100 Выход: предшественник: 80 преемник: -1 Объяснение : Поскольку ни один узел в BST не имеет значения ключа больше чем 100, поэтому -1 печатается для преемника.
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
В предыдущем посте обсуждалось рекурсивное решение. Проблему можно решить с помощью итеративного подхода. Чтобы решить эту проблему, при поиске ключа необходимо рассмотреть три случая, которые описаны ниже:
- Корень - это заданный ключ : в этом случае, если левое поддерево не равно NULL, то предшественником является крайний правый узел в левом поддереве, а если правое поддерево не равно NULL, то преемником является крайний левый узел в правом поддереве.
- Корень больше ключа : в этом случае ключ присутствует в левом поддереве корня. Поэтому найдите ключ в левом поддереве, установив root = root-> left. Обратите внимание, что root может быть неупорядоченным преемником данного ключа. Если у ключа нет правого поддерева, его преемником будет корень.
- Корень меньше ключа : в этом случае ключ присутствует в правом поддереве корня. Поэтому найдите ключ в правом поддереве, установив root = root-> right. Обратите внимание, что root может быть неупорядоченным предшественником данного ключа. Если у ключа нет левого поддерева, корнем будет его предшественник.
Below is the implementation of above approach:
C++
// C++ program to find predecessor // and successor in a BST #include <bits/stdc++.h> using namespace std; // BST Node struct Node { int key; struct Node *left, *right; }; // Function that finds predecessor and successor of key in BST. void findPreSuc(Node* root, Node*& pre, Node*& suc, int key) { if (root == NULL) return ; // Search for given key in BST. while (root != NULL) { // If root is given key. if (root->key == key) { // the minimum value in right subtree // is predecessor. if (root->right) { suc = root->right; while (suc->left) suc = suc->left; } // the maximum value in left subtree // is successor. if (root->left) { pre = root->left; while (pre->right) pre = pre->right; } return ; } // If key is greater than root, then // key lies in right subtree. Root // could be predecessor if left // subtree of key is null. else if (root->key < key) { pre = root; root = root->right; } // If key is smaller than root, then // key lies in left subtree. Root // could be successor if right // subtree of key is null. else { suc = root; root = root->left; } } } // 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 Node* insert(Node* node, int key) { if (node == NULL) return newNode(key); if (key < node->key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; } // Driver program to test above function int main() { int key = 65; // Key to be searched in BST /* Let us create following BST 50 / / 30 70 / / / / 20 40 60 80 */ 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); Node *pre = NULL, *suc = NULL; findPreSuc(root, pre, suc, key); if (pre != NULL) cout << "Predecessor is " << pre->key << endl; else cout << "-1" ; if (suc != NULL) cout << "Successor is " << suc->key; else cout << "-1" ; return 0; } |
Java
// Java program to find predecessor // and successor in a BST import java.util.*; class GFG { // BST Node static class Node { int key; Node left, right; }; static Node pre; static Node suc; // Function that finds predecessor // and successor of key in BST. static void findPreSuc(Node root, int key) { if (root == null ) return ; // Search for given key in BST. while (root != null ) { // If root is given key. if (root.key == key) { // the minimum value in right subtree // is successor. if (root.right != null ) { suc = root.right; while (suc.left != null ) suc = suc.left; } // the maximum value in left subtree // is predecessor. if (root.left != null ) { pre = root.left; while (pre.right != null ) pre = pre.right; } return ; } // If key is greater than root, then // key lies in right subtree. Root // could be predecessor if left // subtree of key is null. else if (root.key < key) { pre = root; root = root.right; } // If key is smaller than root, then // key lies in left subtree. Root // could be successor if right // subtree of key is null. else { suc = root; root = root.left; } } } // 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 (node == null ) return newNode(key); if (key < node.key) node.left = insert(node.left, key); else node.right = insert(node.right, key); return node; } // Driver Code public static void main(String[] args) { int key = 65 ; // Key to be searched in BST /* Let us create following BST 50 / / 30 70 / / / / 20 40 60 80 */ 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 ); findPreSuc(root, key); if (pre != null ) System.out.println( "Predecessor is " + pre.key); else System.out.print( "-1" ); if (suc != null ) System.out.print( "Successor is " + suc.key); else System.out.print( "-1" ); } } // This code is contributed by Princi Singh |
Python3
# Python3 program to find predecessor # and successor in a BST # A utility function to create a # new BST node class newNode: # Constructor to create a new node def __init__( self , data): self .key = data self .left = None self .right = None # Function that finds predecessor and # successor of key in BST. def findPreSuc(root, pre, suc, key): if root = = None : return # Search for given key in BST. while root ! = None : # If root is given key. if root.key = = key: # the minimum value in right # subtree is predecessor. if root.right: suc[ 0 ] = root.right while suc[ 0 ].left: suc[ 0 ] = suc[ 0 ].left # the maximum value in left # subtree is successor. if root.left: pre[ 0 ] = root.left while pre[ 0 ].right: pre[ 0 ] = pre[ 0 ].right return # If key is greater than root, then # key lies in right subtree. Root # could be predecessor if left # subtree of key is null. elif root.key < key: pre[ 0 ] = root root = root.right # If key is smaller than root, then # key lies in left subtree. Root # could be successor if right # subtree of key is null. else : suc[ 0 ] = root root = root.left # A utility function to insert # a new node with given key in BST def insert(node, key): if node = = None : return newNode(key) if key < node.key: node.left = insert(node.left, key) else : node.right = insert(node.right, key) return node # Driver Code if __name__ = = "__main__" : key = 65 # Key to be searched in BST # Let us create following BST # 50 # / # / # 30 70 # / / # / / # 20 40 60 80 root = None root = insert(root, 50 ) insert(root, 30 ) insert(root, 20 ) insert(root, 40 ) insert(root, 70 ) insert(root, 60 ) insert(root, 80 ) pre, suc = [ None ], [ None ] findPreSuc(root, pre, suc, key) if pre[ 0 ] ! = None : print ( "Predecessor is" , pre[ 0 ].key) else : print ( "-1" ) if suc[ 0 ] ! = None : print ( "Successor is" , suc[ 0 ].key) else : print ( "-1" ) # This code is contributed by PranchalK |
C#
// C# program to find predecessor // and successor in a BST using System; class GFG { // BST Node class Node { public int key; public Node left, right; }; static Node pre; static Node suc; РЕКОМЕНДУЕМЫЕ СТАТЬИ |