Considere un BST (Árbol de búsqueda binaria) donde no se permiten duplicados.
Dada una clave presente en el BST. La tarea es encontrar su sucesor de pedido anticipado en este BST, es decir, la tarea es encontrar una clave que viene junto a la clave dada si aplicamos un recorrido de pedido anticipado en BST dado.
Ejemplo:
inserte las siguientes claves en un BST en el mismo orden: 51, 39, 31, 54, 92, 42, 21, 10, 26, 52, 36, 47, 82, 5, 62. Terminará con
un BST como se muestra a continuación:
Reserva transversal : 51 39 31 21 10 5 26 36 42 47 54 52 92 82 62
===================================== Key Pre-Order Successor ===================================== 51 39 39 31 31 21 21 10 10 5 5 26 26 36 36 42 42 47 47 54 52 92 92 82 82 62 62 Do Not Exist.
Enfoque simple: una manera simple y fácil de resolver este problema es aplicar un recorrido de pedido anticipado en BST dado y almacenar las claves de BST en una array. A continuación, busque la clave dada en la array. Si existe, entonces su siguiente clave (que puede no existir necesariamente) es su sucesor de pre-pedido. Si la clave dada no existe en la array, eso significa que la clave dada no existe en BST y, por lo tanto, no puede haber ningún sucesor de pedido anticipado para esta clave.
Pero este algoritmo tiene una complejidad temporal de O(n) . Y la complejidad espacial de O (n) y, por lo tanto, no es una buena forma de abordar este problema.
Enfoque eficiente : una forma eficiente de abordar este problema se basa en las siguientes observaciones:
- Busque un Node en BST que contenga la clave dada.
- Si no existe en BST, entonces no puede haber ningún sucesor de pedido anticipado para esta clave.
- Si existe en BST, entonces puede haber un sucesor de pedido anticipado para esta clave. Tenga en cuenta que no es necesario que si existe una clave, tenga un sucesor de pedido anticipado. Depende de la posición de una clave dada en BST
- Si el Node que contiene la clave dada tiene un hijo izquierdo, entonces su hijo izquierdo es su sucesor de pedido previo.
- Si el Node que contiene lo dado tiene un hijo derecho pero no izquierdo, entonces su hijo derecho es su sucesor de preorden.
- Si el Node que contiene la clave dada es una hoja, entonces debe buscar su antepasado más cercano que tenga un hijo derecho y la clave de este antepasado es mayor que la clave dada, es decir, debe buscar su antepasado más cercano en el subárbol izquierdo del cual el dado clave existe. Hay otros dos casos:
- Tal ancestro existe, si es así, entonces el hijo derecho de este ancestro es el sucesor de preorden de la clave dada.
- Tal ancestro no existe, si es así, entonces no hay un sucesor de pedido anticipado para la clave dada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find pre-Order successor
// of a node in Binary Search Tree
#include <iostream>
using namespace std;
// Declare a structure
struct Node
{
// Key to be stored in BST
int key;
// Pointer to left child
struct Node *left;
// Pointer to the right child
struct Node *right;
// Pointer to parent
struct Node *parent;
};
// This function inserts node in BST
struct Node* insert(int key, struct Node *root,
struct Node *parent)
{
// If root is NULL, insert key here
if (!root)
{
// Allocate memory dynamically
struct Node *node = (struct Node*)malloc(
sizeof(struct Node));
// Validate malloc call
if (node)
{
// Populate the object pointer to by
// pointer named node
node->key = key;
node->left = node->right = NULL;
node->parent = parent;
// Return newly created node
return node;
}
else
// Malloc was not successful to satisfy
// our request, given an appropriate
// message to the user
cout << "Could not allocate memory.";
}
// If this is a duplicate key then give
// a message to user
else if (key == root->key)
cout <<"Duplicates are not allowed in BST.";
// If the key to be inserted is greater than the
// root's key then it will go to the right subtree of
// the tree with current root
else if (key > root->key)
root->right = insert(key, root->right,root);
// If the key to be inserted is smaller than the
// root's key then it will go to a left subtree of
// the tree with current root
else
root->left = insert(key, root->left, root);
// Return the root
return root;
}
// This function searched for a given key in BST
struct Node* search(int key, struct Node *root)
{
// Since the root is empty and hence key
// does not exist in BST
if (!root)
return NULL;
// Current root contains the given key,
// so return current root
else if (key == root->key)
return root;
// Key is greater than the root's key and
// therefore we will search for this key in
// the right subtree of tree with root as
// current root because of all of the keys
// which are greater than the root's key
// exist in the right subtree
else if (key > root->key)
return search(key, root->right);
// Key is smaller than the root's key and
// therefore we will search for this key
// in the left subtree of the tree with
// root as the current root because of
// all of the keys which are smaller
// than the root's key exists in the
// left subtree search tree in the left subtree
else
return search(key, root->left);
}
// This function returns the node that contains the
// pre-order successor for the given key
struct Node* preOrderSuccessor(int key, struct Node *root)
{
// Search for a node in BST that contains
// the given key
struct Node *node = search(key, root);
// There is no node in BST that contains
// the given key, give an appropriate message to user
if (!node)
{
cout << " do not exists in BST.\n" << key;
return NULL;
}
// There exist a node in BST that contains
// the given key Apply our observations
if (node->left)
// If left child of the node that contains the
// given key exist then it is the pre-order
// successor for the given key
return node->left;
else if (node->right)
// If right but not left child of node that
// contains the given key exist then it is
// the pre-order successor for the given key
return node->right;
else
{
// Node containing the key has neither left
// nor right child which means that it is
// leaf node. In this case we will search
// for its nearest ancestor with right
// child which has a key greater than
// the given key
// Since node is a leaf node so its
// parent is guaranteed to exist
struct Node *temp = node->parent;
// Search for nearest ancestor with right
// child that has key greater than the given key
while (temp)
{
if (key < temp->key && temp->right)
break;
temp = temp->parent;
}
// If such an ancestor exist then right child
// of this ancestor is the pre-order successor
// for the given otherwise there do not exist
// any pre-order successor for the given key
return temp ? temp->right : NULL;
}
}
// This function traverse the BST in
// pre-order fashion
void preOrder(struct Node *root)
{
if (root)
{
// First visit the root
cout << " " << root->key;
// Next visit its left subtree
preOrder(root->left);
// Finally visit its right subtree
preOrder(root->right);
}
}
// Driver code
int main()
{
// Declares a root for our BST
struct Node *ROOT = NULL;
// We will create 15 random integers in
// range 0-99 to populate our BST
int a[] = { 51, 39, 31, 54, 92, 42, 21, 10,
26, 52, 36, 47, 82, 5, 62 };
int n = sizeof(a) / sizeof(a[0]);
// Insert all elements into BST
for(int i = 0 ; i < n; i++)
{
// Insert the generated number in BST
cout << "Inserting " << a[i] << " ....." ;
ROOT = insert(a[i], ROOT, NULL);
cout << "Finished Insertion.\n";
}
// Apply pre-order traversal on BST
cout << "\nPre-Order Traversal : ";
preOrder(ROOT);
// Display pre-order Successors for
// all of the keys in BST
cout <<"\n=====================================";
cout <<"\n\n" << "Key" <<" " << "Pre-Order Successor" << endl;
cout <<"=====================================\n";
// This stores the pre-order successor
// for a given key
struct Node *successor = NULL;
// Iterate through all of the elements inserted
// in BST to get their pre-order successor
for(int i = 0 ; i < n; ++i)
{
// Get the pre-order successor for the given key
successor = preOrderSuccessor(a[i], ROOT);
if (successor)
// Successor is not NULL and hence it contains
// the pre-order successor for given key
cout << "\n" << a[i] << " "
<< successor->key;
else
// Successor is NULL and hence given key do
// not have a pre-order successor
cout << " " << "Do Not Exist.\n" << a[i];
}
return 0;
}
// This code is contributed by shivanisinghss2110
C
// C program to find pre-Order successor
// of a node in Binary Search Tree
#include<stdio.h>
#include<stdlib.h>
// Declare a structure
struct Node{
// Key to be stored in BST
int key;
// Pointer to left child
struct Node *left;
// Pointer to the right child
struct Node *right;
// Pointer to parent
struct Node *parent;
};
// This function inserts node in BST
struct Node* insert(int key, struct Node *root,
struct Node *parent)
{
// If root is NULL, insert key here
if(!root)
{
// Allocate memory dynamically
struct Node *node = (struct Node*)malloc(sizeof(struct Node));
// Validate malloc call
if(node)
{
// Populate the object pointer to by
// pointer named node
node->key = key;
node->left = node->right = NULL;
node->parent = parent;
// Return newly created node
return node;
}
else
// Malloc was not successful to satisfy our request,
// given an appropriate message to the user
printf("Could not allocate memory.");
}
// If this is a duplicate key then give a message to user
else if(key == root->key)
printf("Duplicates are not allowed in BST.");
// If the key to be inserted is greater than the root's
// key then it will go to the right subtree of
// the tree with current root
else if(key > root->key)
root->right = insert(key, root->right,root);
// If the key to be inserted is smaller than the
// root's key then it will go to a left subtree of
// the tree with current root
else
root->left = insert(key, root->left, root);
// Return the root
return root;
}
// This function searched for a given key in BST
struct Node* search(int key, struct Node *root)
{
// Since the root is empty and hence key
// does not exist in BST
if(!root)
return NULL;
// Current root contains the given key,
// so return current root
else if( key == root->key)
return root;
// Key is greater than the root's key and therefore
// we will search for this key in the right subtree of
// tree with root as current root because of all of the keys
// which are greater than the root's key exist in the right subtree
else if(key > root->key)
return search(key, root->right);
// Key is smaller than the root's key and therefore we will
// search for this key in the left subtree of the tree with
// root as the current root because of all of the keys which are
// smaller than the root's key exists in the left subtree
// search tree in the left subtree
else
return search(key, root->left);
}
// This function returns the node that contains the
// pre-order successor for the given key
struct Node* preOrderSuccessor(int key, struct Node *root){
// Search for a node in BST that contains the given key
struct Node *node = search(key, root);
// There is no node in BST that contains the given key,
// give an appropriate message to user
if(!node){
printf("%d do not exists in BST.\n", key);
return NULL;
}
// There exist a node in BST that contains the given key
// Apply our observations
if(node->left)
// If left child of the node that contains the
// given key exist then it is the pre-order
// successor for the given key
return node->left;
else if(node->right)
// If right but not left child of node that contains
// the given key exist then it is the pre-order
// successor for the given key
return node->right;
else
{
// Node containing the key has neither left nor right child
// which means that it is leaf node. In this case we will search
// for its nearest ancestor with right child which has a key
// greater than the given key
// Since node is a leaf node so its parent is guaranteed to exist
struct Node *temp = node->parent;
// Search for nearest ancestor with right child that has
// key greater than the given key
while(temp){
if(key < temp->key && temp->right)
break;
temp = temp->parent;
}
// If such an ancestor exist then right child of this ancestor
// is the pre-order successor for the given otherwise there
// do not exist any pre-order successor for the given key
return temp ? temp->right : NULL;
}
}
// This function traverse the BST in pre-order fashion
void preOrder(struct Node *root)
{
if(root)
{
// First visit the root
printf("%d ", root->key);
// Next visit its left subtree
preOrder(root->left);
// Finally visit its right subtree
preOrder(root->right);
}
}
// Driver code
int main()
{
// Declares a root for our BST
struct Node *ROOT = NULL;
// We will create 15 random integers in
// range 0-99 to populate our BST
int a[] = {51, 39, 31, 54, 92, 42, 21, 10,
26, 52, 36, 47, 82, 5, 62};
int n = sizeof(a) / sizeof(a[0]);
// Insert all elements into BST
for(int i = 0 ; i < n; i++)
{
// Insert the generated number in BST
printf("Inserting %2d.....", a[i]);
ROOT = insert(a[i], ROOT, NULL);
printf("Finished Insertion.\n");
}
// Apply pre-order traversal on BST
printf("\nPre-Order Traversal : ");
preOrder(ROOT);
// Display pre-order Successors for all of the keys in BST
printf("\n=====================================");
printf("\n%-10s%s\n", "Key", "Pre-Order Successor");
printf("=====================================\n");
// This stores the pre-order successor for a given key
struct Node *successor = NULL;
// Iterate through all of the elements inserted
// in BST to get their pre-order successor
for(int i = 0 ; i < n; ++i)
{
// Get the pre-order successor for the given key
successor = preOrderSuccessor(a[i], ROOT);
if(successor)
// Successor is not NULL and hence it contains
// the pre-order successor for given key
printf("%-10d%d\n", a[i], successor->key);
else
// Successor is NULL and hence given key do
// not have a pre-order successor
printf("%-10dDo Not Exist.\n", a[i]);
}
return 0;
}
Java
// Java program to find pre-Order successor
// of a node in Binary Search Tree
import java.util.*;
class GFG
{
// Declare a structure
static class Node
{
// Key to be stored in BST
int key;
// Pointer to left child
Node left;
// Pointer to the right child
Node right;
// Pointer to parent
Node parent;
};
// This function inserts node in BST
static Node insert(int key, Node root,
Node parent)
{
// If root is null, insert key here
if(root == null)
{
// Allocate memory dynamically
Node node = new Node();
// Validate malloc call
if(node != null)
{
// Populate the object pointer to by
// pointer named node
node.key = key;
node.left = node.right = null;
node.parent = parent;
// Return newly created node
return node;
}
else
// Malloc was not successful to
// satisfy our request, given
// an appropriate message to the user
System.out.printf("Could not allocate memory.");
}
// If this is a duplicate key then
// give a message to user
else if(key == root.key)
System.out.printf("Duplicates are not" +
" allowed in BST.");
// If the key to be inserted is greater than
// the root's key then it will go to the
// right subtree of the tree with current root
else if(key > root.key)
root.right = insert(key, root.right, root);
// If the key to be inserted is smaller than the
// root's key then it will go to a left subtree
// of the tree with current root
else
root.left = insert(key, root.left, root);
// Return the root
return root;
}
// This function searched for a given key in BST
static Node search(int key, Node root)
{
// Since the root is empty and hence
// key does not exist in BST
if(root == null)
return null;
// Current root contains the given key,
// so return current root
else if( key == root.key)
return root;
// Key is greater than the root's key and
// therefore we will search for this key
// in the right subtree of tree with root
// as current root because of all of the keys
// which are greater than the root's key
// exist in the right subtree
else if(key > root.key)
return search(key, root.right);
// Key is smaller than the root's key and
// therefore we will search for this key
// in the left subtree of the tree with root
// as the current root because of all of the keys
// which are smaller than the root's key exists in
// the left subtree search tree in the left subtree
else
return search(key, root.left);
}
// This function returns the node
// that contains the pre-order successor
// for the given key
static Node preOrderSuccessor(int key,
Node root)
{
// Search for a node in BST
// that contains the given key
Node node = search(key, root);
// There is no node in BST
// that contains the given key,
// give an appropriate message to user
if(node == null)
{
System.out.printf("%d do not exists" +
" in BST.\n", key);
return null;
}
// There exist a node in BST that contains
// the given key. Apply our observations
if(node.left != null)
// If left child of the node that
// contains the given key exist
// then it is the pre-order successor
// for the given key
return node.left;
else if(node.right != null)
// If right but not left child of node
// that contains the given key exist
// then it is the pre-order successor
// for the given key
return node.right;
else
{
// Node containing the key has neither left
// nor right child which means that it is
// leaf node. In this case we will search
// for its nearest ancestor with right child
// which has a key greater than the given key
// Since node is a leaf node
// so its parent is guaranteed to exist
Node temp = node.parent;
// Search for nearest ancestor with right child
// that has key greater than the given key
while(temp != null)
{
if(key < temp.key && temp.right != null)
break;
temp = temp.parent;
}
// If such an ancestor exist then right child
// of this ancestor is the pre-order successor
// for the given otherwise there do not exist
// any pre-order successor for the given key
return temp != null ? temp.right : null;
}
}
// This function traverse the BST
// in pre-order fashion
static void preOrder(Node root)
{
if(root != null)
{
// First visit the root
System.out.printf("%d ", root.key);
// Next visit its left subtree
preOrder(root.left);
// Finally visit its right subtree
preOrder(root.right);
}
}
// Driver code
public static void main(String args[])
{
// Declares a root for our BST
Node ROOT = null;
// We will create 15 random integers in
// range 0-99 to populate our BST
int a[] = {51, 39, 31, 54, 92, 42, 21, 10,
26, 52, 36, 47, 82, 5, 62};
int n = a.length;
// Insert all elements into BST
for(int i = 0 ; i < n; i++)
{
// Insert the generated number in BST
System.out.printf("Inserting %2d.....", a[i]);
ROOT = insert(a[i], ROOT, null);
System.out.printf("Finished Insertion.\n");
}
// Apply pre-order traversal on BST
System.out.printf("\nPre-Order Traversal : ");
preOrder(ROOT);
// Display pre-order Successors
// for all of the keys in BST
System.out.printf("\n=====================================");
System.out.printf("\n%-10s%s\n", "Key",
"Pre-Order Successor");
System.out.printf("=====================================\n");
// This stores the pre-order successor
// for a given key
Node successor = null;
// Iterate through all of the elements inserted
// in BST to get their pre-order successor
for(int i = 0 ; i < n; ++i)
{
// Get the pre-order successor
// for the given key
successor = preOrderSuccessor(a[i], ROOT);
if(successor != null)
// Successor is not null and hence
// it contains the pre-order
// successor for given key
System.out.printf("%-10d%d\n", a[i],
successor.key);
else
// Successor is null and hence given key do
// not have a pre-order successor
System.out.printf("%-10dDo Not Exist.\n", a[i]);
}
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to find pre-Order successor
# of a node in Binary Search Tree
# Declare a structure
class Node:
def __init__(self):
# Key to be stored in BST
self.key = 0
# Pointer to left child
self.left = None
# Pointer to the right child
self.right = None
# Pointer to parent
self.parent = None
# This function inserts node in BST
def insert(key: int, root: Node, parent: Node):
# If root is None, insert key here
if not root:
# Allocate memory dynamically
node = Node()
# Validate malloc call
if (node):
# Populate the object pointer to by
# pointer named node
node.key = key
node.left = node.right = None
node.parent = parent
# Return newly created node
return node
else:
# Malloc was not successful to satisfy our request,
# given an appropriate message to the user
print("Could not allocate memory.")
# If this is a duplicate key then give a message to user
elif (key == root.key):
print("Duplicates are not allowed in BST.")
# If the key to be inserted is greater than the root's
# key then it will go to the right subtree of
# the tree with current root
elif (key > root.key):
root.right = insert(key, root.right, root)
# If the key to be inserted is smaller than the
# root's key then it will go to a left subtree of
# the tree with current root
else:
root.left = insert(key, root.left, root)
# Return the root
return root
# This function searched for a given key in BST
def search(key: int, root: Node):
# Since the root is empty and hence key
# does not exist in BST
if not root:
return None
# Current root contains the given key,
# so return current root
elif (key == root.key):
return root
# Key is greater than the root's key and therefore
# we will search for this key in the right subtree
# of tree with root as current root because of all
# of the keys which are greater than the root's key
# exist in the right subtree
elif (key > root.key):
return search(key, root.right)
# Key is smaller than the root's key and therefore
# we will search for this key in the left subtree
# of the tree with root as the current root because
# of all of the keys which are smaller than the
# root's key exists in the left subtree search
# tree in the left subtree
else:
return search(key, root.left)
# This function returns the node that contains the
# pre-order successor for the given key
def preOrderSuccessor(key: int, root: Node):
# Search for a node in BST that
# contains the given key
node = search(key, root)
# There is no node in BST that contains
# the given key, give an appropriate
# message to user
if not node:
print("%d do not exists in BST.\n" % key, end = "")
return None
# There exist a node in BST that contains the
# given key. Apply our observations
if (node.left):
# If left child of the node that contains the
# given key exist then it is the pre-order
# successor for the given key
return node.left
elif (node.right):
# If right but not left child of node that
# contains the given key exist then it is
# the pre-order successor for the given key
return node.right
else:
# Node containing the key has neither left
# nor right child which means that it is
# leaf node. In this case we will search
# for its nearest ancestor with right
# child which has a key greater than
# the given key
# Since node is a leaf node so its parent
# is guaranteed to exist
temp = node.parent
# Search for nearest ancestor with right
# child that has key greater than the
# given key
while (temp):
if (key < temp.key and temp.right):
break
temp = temp.parent
# If such an ancestor exist then right child
# of this ancestor is the pre-order successor
# for the given otherwise there do not exist
# any pre-order successor for the given key
return temp.right if temp != None else None
# This function traverse the BST in
# pre-order fashion
def preOrder(root: Node):
if (root):
# First visit the root
print("%d " % root.key, end = "")
# Next visit its left subtree
preOrder(root.left)
# Finally visit its right subtree
preOrder(root.right)
# Driver code
if __name__ == "__main__":
# Declares a root for our BST
ROOT = None
# We will create 15 random integers in
# range 0-99 to populate our BST
a = [ 51, 39, 31, 54, 92, 42, 21,
10, 26, 52, 36, 47, 82, 5, 62 ]
n = len(a)
# Insert all elements into BST
for i in range(n):
# Insert the generated number in BST
print("Inserting %2d....." % a[i], end = "")
ROOT = insert(a[i], ROOT, None)
print("Finished Insertion.")
# Apply pre-order traversal on BST
print("\nPre-Order Traversal : ", end = "")
preOrder(ROOT)
# Display pre-order Successors for all of the keys in BST
print("\n=====================================", end = "")
print("\n%-10s%s\n" % ("Key", "Pre-Order Successor"), end = "")
print("=====================================")
# This stores the pre-order successor for a given key
successor = None
# Iterate through all of the elements inserted
# in BST to get their pre-order successor
for i in range(n):
# Get the pre-order successor for the given key
successor = preOrderSuccessor(a[i], ROOT)
if (successor):
# Successor is not None and hence it contains
# the pre-order successor for given key
print("%-10d%d" % (a[i], successor.key))
else:
# Successor is None and hence given key do
# not have a pre-order successor
print("%-10dDo Not Exist." % a[i])
# This code is contributed by sanjeev2552
C#
// C# program to find pre-Order successor
// of a node in Binary Search Tree
using System;
public class GFG {
// Declare a structure
public class Node
{
// Key to be stored in BST
public int key;
// Pointer to left child
public Node left;
// Pointer to the right child
public Node right;
// Pointer to parent
public Node parent;
};
// This function inserts node in BST
static Node insert(int key, Node root, Node parent) {
// If root is null, insert key here
if (root == null) {
// Allocate memory dynamically
Node node = new Node();
// Validate malloc call
if (node != null) {
// Populate the object pointer to by
// pointer named node
node.key = key;
node.left = node.right = null;
node.parent = parent;
// Return newly created node
return node;
} else
// Malloc was not successful to
// satisfy our request, given
// an appropriate message to the user
Console.Write("Could not allocate memory.");
}
// If this is a duplicate key then
// give a message to user
else if (key == root.key)
Console.Write("Duplicates are not" + " allowed in BST.");
// If the key to be inserted is greater than
// the root's key then it will go to the
// right subtree of the tree with current root
else if (key > root.key)
root.right = insert(key, root.right, root);
// If the key to be inserted is smaller than the
// root's key then it will go to a left subtree
// of the tree with current root
else
root.left = insert(key, root.left, root);
// Return the root
return root;
}
// This function searched for a given key in BST
static Node search(int key, Node root) {
// Since the root is empty and hence
// key does not exist in BST
if (root == null)
return null;
// Current root contains the given key,
// so return current root
else if (key == root.key)
return root;
// Key is greater than the root's key and
// therefore we will search for this key
// in the right subtree of tree with root
// as current root because of all of the keys
// which are greater than the root's key
// exist in the right subtree
else if (key > root.key)
return search(key, root.right);
// Key is smaller than the root's key and
// therefore we will search for this key
// in the left subtree of the tree with root
// as the current root because of all of the keys
// which are smaller than the root's key exists in
// the left subtree search tree in the left subtree
else
return search(key, root.left);
}
// This function returns the node
// that contains the pre-order successor
// for the given key
static Node preOrderSuccessor(int key, Node root) {
// Search for a node in BST
// that contains the given key
Node node = search(key, root);
// There is no node in BST
// that contains the given key,
// give an appropriate message to user
if (node == null) {
Console.Write("{0} do not exists" + " in BST.\n", key);
return null;
}
// There exist a node in BST that contains
// the given key. Apply our observations
if (node.left != null)
// If left child of the node that
// contains the given key exist
// then it is the pre-order successor
// for the given key
return node.left;
else if (node.right != null)
// If right but not left child of node
// that contains the given key exist
// then it is the pre-order successor
// for the given key
return node.right;
else {
// Node containing the key has neither left
// nor right child which means that it is
// leaf node. In this case we will search
// for its nearest ancestor with right child
// which has a key greater than the given key
// Since node is a leaf node
// so its parent is guaranteed to exist
Node temp = node.parent;
// Search for nearest ancestor with right child
// that has key greater than the given key
while (temp != null) {
if (key < temp.key && temp.right != null)
break;
temp = temp.parent;
}
// If such an ancestor exist then right child
// of this ancestor is the pre-order successor
// for the given otherwise there do not exist
// any pre-order successor for the given key
return temp != null ? temp.right : null;
}
}
// This function traverse the BST
// in pre-order fashion
static void preOrder(Node root) {
if (root != null) {
// First visit the root
Console.Write("{0} ", root.key);
// Next visit its left subtree
preOrder(root.left);
// Finally visit its right subtree
preOrder(root.right);
}
}
// Driver code
public static void Main(String []args) {
// Declares a root for our BST
Node ROOT = null;
// We will create 15 random integers in
// range 0-99 to populate our BST
int []a = { 51, 39, 31, 54, 92, 42, 21, 10, 26, 52, 36, 47, 82, 5, 62 };
int n = a.Length;
// Insert all elements into BST
for (int i = 0; i < n; i++) {
// Insert the generated number in BST
Console.Write("Inserting {0} .....", a[i]);
ROOT = insert(a[i], ROOT, null);
Console.Write("Finished Insertion.\n");
}
// Apply pre-order traversal on BST
Console.Write("\nPre-Order Traversal : ");
preOrder(ROOT);
// Display pre-order Successors
// for all of the keys in BST
Console.Write("\n=====================================");
Console.Write("\nKey Pre-Order Successor\n");
Console.Write("=====================================\n");
// This stores the pre-order successor
// for a given key
Node successor = null;
// Iterate through all of the elements inserted
// in BST to get their pre-order successor
for (int i = 0; i < n; ++i) {
// Get the pre-order successor
// for the given key
successor = preOrderSuccessor(a[i], ROOT);
if (successor != null)
// Successor is not null and hence
// it contains the pre-order
// successor for given key
Console.Write("{0} {1}\n", a[i], successor.key);
else
// Successor is null and hence given key do
// not have a pre-order successor
Console.Write("{0} Do Not Exist.\n", a[i]);
}
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find pre-Order successor
// of a node in Binary Search Tree
// Declare a structure
class Node
{
constructor()
{
this.key=0;
this.left=this.right=this.parent=null;
}
}
// This function inserts node in BST
function insert(key,root,parent)
{
// If root is null, insert key here
if(root == null)
{
// Allocate memory dynamically
let node = new Node();
// Validate malloc call
if(node != null)
{
// Populate the object pointer to by
// pointer named node
node.key = key;
node.left = node.right = null;
node.parent = parent;
// Return newly created node
return node;
}
else
// Malloc was not successful to
// satisfy our request, given
// an appropriate message to the user
document.write("Could not allocate memory.");
}
// If this is a duplicate key then
// give a message to user
else if(key == root.key)
document.write("Duplicates are not" +
" allowed in BST.");
// If the key to be inserted is greater than
// the root's key then it will go to the
// right subtree of the tree with current root
else if(key > root.key)
root.right = insert(key, root.right, root);
// If the key to be inserted is smaller than the
// root's key then it will go to a left subtree
// of the tree with current root
else
root.left = insert(key, root.left, root);
// Return the root
return root;
}
// This function searched for a given key in BST
function search(key,root)
{
// Since the root is empty and hence
// key does not exist in BST
if(root == null)
return null;
// Current root contains the given key,
// so return current root
else if( key == root.key)
return root;
// Key is greater than the root's key and
// therefore we will search for this key
// in the right subtree of tree with root
// as current root because of all of the keys
// which are greater than the root's key
// exist in the right subtree
else if(key > root.key)
return search(key, root.right);
// Key is smaller than the root's key and
// therefore we will search for this key
// in the left subtree of the tree with root
// as the current root because of all of the keys
// which are smaller than the root's key exists in
// the left subtree search tree in the left subtree
else
return search(key, root.left);
}
// This function returns the node
// that contains the pre-order successor
// for the given key
function preOrderSuccessor(key,root)
{
// Search for a node in BST
// that contains the given key
let node = search(key, root);
// There is no node in BST
// that contains the given key,
// give an appropriate message to user
if(node == null)
{
document.write(key + " do not exists" +
" in BST.<br>");
return null;
}
// There exist a node in BST that contains
// the given key. Apply our observations
if(node.left != null)
// If left child of the node that
// contains the given key exist
// then it is the pre-order successor
// for the given key
return node.left;
else if(node.right != null)
// If right but not left child of node
// that contains the given key exist
// then it is the pre-order successor
// for the given key
return node.right;
else
{
// Node containing the key has neither left
// nor right child which means that it is
// leaf node. In this case we will search
// for its nearest ancestor with right child
// which has a key greater than the given key
// Since node is a leaf node
// so its parent is guaranteed to exist
let temp = node.parent;
// Search for nearest ancestor with right child
// that has key greater than the given key
while(temp != null)
{
if(key < temp.key && temp.right != null)
break;
temp = temp.parent;
}
// If such an ancestor exist then right child
// of this ancestor is the pre-order successor
// for the given otherwise there do not exist
// any pre-order successor for the given key
return temp != null ? temp.right : null;
}
}
// This function traverse the BST
// in pre-order fashion
function preOrder(root)
{
if(root != null)
{
// First visit the root
document.write(root.key+" ");
// Next visit its left subtree
preOrder(root.left);
// Finally visit its right subtree
preOrder(root.right);
}
}
// Driver code
// Declares a root for our BST
let ROOT = null;
// We will create 15 random integers in
// range 0-99 to populate our BST
let a = [51, 39, 31, 54, 92, 42, 21, 10,
26, 52, 36, 47, 82, 5, 62];
let n = a.length;
// Insert all elements into BST
for(let i = 0 ; i < n; i++)
{
// Insert the generated number in BST
document.write("Inserting "+a[i]+".....");
ROOT = insert(a[i], ROOT, null);
document.write("Finished Insertion.<br>");
}
// Apply pre-order traversal on BST
document.write("<br>Pre-Order Traversal : ");
preOrder(ROOT);
// Display pre-order Successors
// for all of the keys in BST
document.write("<br>=====================================<br>");
document.write("Key"+" " + "Pre-Order Successor<br>");
document.write("=====================================<br>");
// This stores the pre-order successor
// for a given key
let successor = null;
// Iterate through all of the elements inserted
// in BST to get their pre-order successor
for(let i = 0 ; i < n; ++i)
{
// Get the pre-order successor
// for the given key
successor = preOrderSuccessor(a[i], ROOT);
if(successor != null)
// Successor is not null and hence
// it contains the pre-order
// successor for given key
document.write(a[i]+" " +successor.key+"<br>");
else
// Successor is null and hence given key do
// not have a pre-order successor
document.write(a[i]+ " Do Not Exist.<br>");
}
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Inserting 51.....Finished Insertion. Inserting 39.....Finished Insertion. Inserting 31.....Finished Insertion. Inserting 54.....Finished Insertion. Inserting 92.....Finished Insertion. Inserting 42.....Finished Insertion. Inserting 21.....Finished Insertion. Inserting 10.....Finished Insertion. Inserting 26.....Finished Insertion. Inserting 52.....Finished Insertion. Inserting 36.....Finished Insertion. Inserting 47.....Finished Insertion. Inserting 82.....Finished Insertion. Inserting 5.....Finished Insertion. Inserting 62.....Finished Insertion. Pre-Order Traversal : 51 39 31 21 10 5 26 36 42 47 54 52 92 82 62 ===================================== Key Pre-Order Successor ===================================== 51 39 39 31 31 21 54 52 92 82 42 47 21 10 10 5 26 36 52 92 36 42 47 54 82 62 5 26 62 Do Not Exist.
Publicación traducida automáticamente
Artículo escrito por shubhampanchal9773 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA