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}, прежде чем переходить к решению.

В предыдущем посте обсуждалось рекурсивное решение. Проблему можно решить с помощью итеративного подхода. Чтобы решить эту проблему, при поиске ключа необходимо рассмотреть три случая, которые описаны ниже:

  1. Корень - это заданный ключ : в этом случае, если левое поддерево не равно NULL, то предшественником является крайний правый узел в левом поддереве, а если правое поддерево не равно NULL, то преемником является крайний левый узел в правом поддереве.
  2. Корень больше ключа : в этом случае ключ присутствует в левом поддереве корня. Поэтому найдите ключ в левом поддереве, установив root = root-> left. Обратите внимание, что root может быть неупорядоченным преемником данного ключа. Если у ключа нет правого поддерева, его преемником будет корень.
  3. Корень меньше ключа : в этом случае ключ присутствует в правом поддереве корня. Поэтому найдите ключ в правом поддереве, установив 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;
Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023
Введение в связанный список — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Введение в массивы — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Как подготовиться к ICFP или Международной конференции по функциональному программированию?
12 Декабря, 2022