Dado un árbol binario y un Node, necesitamos escribir un programa para encontrar el sucesor en orden de este Node.
Inorder El sucesor de un Node en el árbol binario es el siguiente Node en el recorrido Inorder del árbol binario. Sucesor en orden es NULL para el último Node en el recorrido en orden.
En el diagrama anterior, el sucesor en orden del Node 4 es 2 y el Node 5 es 1 .
Ya hemos discutido cómo encontrar el sucesor en orden de un Node en Binary Search Tree . No podemos usar el mismo enfoque para encontrar el sucesor en orden en árboles binarios generales.
Necesitamos ocuparnos de 3 casos para que cualquier Node encuentre su sucesor en orden como se describe a continuación:
- El hijo derecho del Node no es NULL. Si el hijo derecho del Node no es NULL, entonces el sucesor en orden de este Node será el Node más a la izquierda en su subárbol derecho.
- El hijo derecho del Node es NULL. Si el hijo derecho del Node es NULL. Luego seguimos encontrando el padre del Node dado x, digamos p tal que p->left = x. Por ejemplo, en el árbol anterior, el sucesor en orden del Node 5 será 1 . El primer padre de 5 es 2 pero 2->left != 5. Entonces, el siguiente padre de 2 es 1, ahora 1->left = 2. Por lo tanto, el sucesor en orden de 5 es 1.
A continuación se muestra el algoritmo para este caso:- Supongamos que el Node dado es x . Comience a atravesar el árbol desde el Node raíz para encontrar x recursivamente.
- Si root == x , detenga la recursión; de lo contrario, encuentre x recursivamente para los subárboles izquierdo y derecho.
- Ahora, después de encontrar el Node x , la recursividad retrocederá hasta la raíz . Cada llamada recursiva devolverá el Node a la función de llamada, almacenaremos esto en un Node temporal, por ejemplo , temp . Ahora, cuando retroceda a su padre, que será root ahora, verifique si root.left = temp, si no, mantenga subiendo
- Si el Node es el Node más a la derecha. Si el Node es el Node más a la derecha en el árbol dado. Por ejemplo, en el árbol anterior, el Node 6 es el Node más a la derecha. En este caso, no habrá sucesor en orden de este Node. es decir, el sucesor en orden del Node más a la derecha en un árbol es NULL.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find inorder successor of a node
#include<bits/stdc++.h>
using namespace std;
// A Binary Tree Node
struct Node
{
int data;
struct Node *left, *right;
};
// Temporary node for case 2
Node* temp = new Node;
// Utility function to create a new tree node
Node* newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// function to find left most node in a tree
Node* leftMostNode(Node* node)
{
while (node != NULL && node->left != NULL)
node = node->left;
return node;
}
// function to find right most node in a tree
Node* rightMostNode(Node* node)
{
while (node != NULL && node->right != NULL)
node = node->right;
return node;
}
// recursive function to find the Inorder Successor
// when the right child of node x is NULL
Node* findInorderRecursive(Node* root, Node* x )
{
if (!root)
return NULL;
if (root==x || (temp = findInorderRecursive(root->left,x)) ||
(temp = findInorderRecursive(root->right,x)))
{
if (temp)
{
if (root->left == temp)
{
cout << "Inorder Successor of " << x->data;
cout << " is "<< root->data << "\n";
return NULL;
}
}
return root;
}
return NULL;
}
// function to find inorder successor of
// a node
void inorderSuccessor(Node* root, Node* x)
{
// Case1: If right child is not NULL
if (x->right != NULL)
{
Node* inorderSucc = leftMostNode(x->right);
cout<<"Inorder Successor of "<<x->data<<" is ";
cout<<inorderSucc->data<<"\n";
}
// Case2: If right child is NULL
if (x->right == NULL)
{
Node* rightMost = rightMostNode(root);
// case3: If x is the right most node
if (rightMost == x)
cout << "No inorder successor! Right most node.\n";
else
findInorderRecursive(root, x);
}
}
// Driver program to test above functions
int main()
{
// Let's construct the binary tree
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
// Case 1 : When there is a right child
// eg: Node(1) has a right child ergo the inorder successor would be leftmost
// node of the right subtree ie 6.
inorderSuccessor(root, root);
// case 2: When the right child is NULL
// eg: From the above figure Node(5) satisfies this case
inorderSuccessor(root, root->left->left);
// case 3: When the node is the rightmost node of the binary tree
inorderSuccessor(root, root->right->right);
return 0;
}
Java
// Java program to find inorder successor of a node
class Solution
{
// A Binary Tree Node
static class Node
{
int data;
Node left, right;
}
// Temporary node for case 2
static Node temp = new Node();
// Utility function to create a new tree node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// function to find left most node in a tree
static Node leftMostNode(Node node)
{
while (node != null && node.left != null)
node = node.left;
return node;
}
// function to find right most node in a tree
static Node rightMostNode(Node node)
{
while (node != null && node.right != null)
node = node.right;
return node;
}
// recursive function to find the Inorder Successor
// when the right child of node x is null
static Node findInorderRecursive(Node root, Node x )
{
if (root==null)
return null;
if (root==x || (temp = findInorderRecursive(root.left,x))!=null ||
(temp = findInorderRecursive(root.right,x))!=null)
{
if (temp!=null)
{
if (root.left == temp)
{
System.out.print( "Inorder Successor of "+x.data);
System.out.print( " is "+ root.data + "\n");
return null;
}
}
return root;
}
return null;
}
// function to find inorder successor of
// a node
static void inorderSuccessor(Node root, Node x)
{
// Case1: If right child is not null
if (x.right != null)
{
Node inorderSucc = leftMostNode(x.right);
System.out.print("Inorder Successor of "+x.data+" is ");
System.out.print(inorderSucc.data+"\n");
}
// Case2: If right child is null
if (x.right == null)
{
int f = 0;
Node rightMost = rightMostNode(root);
// case3: If x is the right most node
if (rightMost == x)
System.out.print("No inorder successor! Right most node.\n");
else
findInorderRecursive(root, x);
}
}
// Driver program to test above functions
public static void main(String args[])
{
// Let's construct the binary tree
// as shown in above diagram
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.right.right = newNode(6);
// Case 1
inorderSuccessor(root, root.right);
// case 2
inorderSuccessor(root, root.left.left);
// case 3
inorderSuccessor(root, root.right.right);
}
}
//contributed by Arnab Kundu
Python3
""" Python3 code for inorder successor
and predecessor of tree """
# A Binary Tree Node
# Utility function to create a new tree node
class newNode:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# function to find left most node in a tree
def leftMostNode(node):
while (node != None and node.left != None):
node = node.left
return node
# function to find right most node in a tree
def rightMostNode(node):
while (node != None and node.right != None):
node = node.right
return node
# recursive function to find the Inorder Successor
# when the right child of node x is None
def findInorderRecursive(root, x ):
if (not root):
return None
if (root == x or (findInorderRecursive(root.left, x)) or
(findInorderRecursive(root.right, x))):
if findInorderRecursive(root.right, x):
temp=findInorderRecursive(root.right, x)
else:
temp=findInorderRecursive(root.left, x)
if (temp):
if (root.left == temp):
print("Inorder Successor of",
x.data, end = "")
print(" is", root.data)
return None
return root
return None
# function to find inorder successor
# of a node
def inorderSuccessor(root, x):
# Case1: If right child is not None
if (x.right != None) :
inorderSucc = leftMostNode(x.right)
print("Inorder Successor of", x.data,
"is", end = " ")
print(inorderSucc.data)
# Case2: If right child is None
if (x.right == None):
f = 0
rightMost = rightMostNode(root)
# case3: If x is the right most node
if (rightMost == x):
print("No inorder successor!",
"Right most node.")
else:
findInorderRecursive(root, x)
# Driver Code
if __name__ == '__main__':
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.left = newNode(4)
root.left.right = newNode(5)
root.right.right = newNode(6)
# Case 1
inorderSuccessor(root, root.right)
# case 2
inorderSuccessor(root, root.left.left)
# case 3
inorderSuccessor(root, root.right.right)
# This code is contributed
# by SHUBHAMSINGH10
C#
// C# program to find inorder
// successor of a node
using System;
class GFG
{
// A Binary Tree Node
public class Node
{
public int data;
public Node left, right;
}
// Temporary node for case 2
public static Node temp = new Node();
// Utility function to create
// a new tree node
public static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// function to find left most
// node in a tree
public static Node leftMostNode(Node node)
{
while (node != null &&
node.left != null)
{
node = node.left;
}
return node;
}
// function to find right most
// node in a tree
public static Node rightMostNode(Node node)
{
while (node != null &&
node.right != null)
{
node = node.right;
}
return node;
}
// recursive function to find the
// Inorder Successor when the right
// child of node x is null
public static Node findInorderRecursive(Node root,
Node x)
{
if (root == null)
{
return null;
}
if (root == x ||
(temp = findInorderRecursive(root.left, x)) != null ||
(temp = findInorderRecursive(root.right, x)) != null)
{
if (temp != null)
{
if (root.left == temp)
{
Console.Write("Inorder Successor of " + x.data);
Console.Write(" is " + root.data + "\n");
return null;
}
}
return root;
}
return null;
}
// function to find inorder successor
// of a node
public static void inorderSuccessor(Node root, Node x)
{
// Case1: If right child is not null
if (x.right != null)
{
Node inorderSucc = leftMostNode(x.right);
Console.Write("Inorder Successor of " +
x.data + " is ");
Console.Write(inorderSucc.data + "\n");
}
// Case2: If right child is null
if (x.right == null)
{
int f = 0;
Node rightMost = rightMostNode(root);
// case3: If x is the right most node
if (rightMost == x)
{
Console.Write("No inorder successor! " +
"Right most node.\n");
}
else
{
findInorderRecursive(root, x);
}
}
}
// Driver Code
public static void Main(string[] args)
{
// Let's construct the binary tree
// as shown in above diagram
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.right.right = newNode(6);
// Case 1
inorderSuccessor(root, root.right);
// case 2
inorderSuccessor(root, root.left.left);
// case 3
inorderSuccessor(root, root.right.right);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript program to find inorder successor of a node
// A Binary Tree Node
class Node
{
constructor(data)
{
this.data=data;
this.left=this.right=null;
}
}
// Temporary node for case 2
let temp = new Node();
// function to find left most node in a tree
function leftMostNode(node)
{
while (node != null && node.left != null)
node = node.left;
return node;
}
// function to find right most node in a tree
function rightMostNode(node)
{
while (node != null && node.right != null)
node = node.right;
return node;
}
// recursive function to find the Inorder Successor
// when the right child of node x is null
function findInorderRecursive(root,x)
{
if (root==null)
return null;
if (root==x || (temp = findInorderRecursive(root.left,x))!=null ||
(temp = findInorderRecursive(root.right,x))!=null)
{
if (temp!=null)
{
if (root.left == temp)
{
document.write( "Inorder Successor of "+x.data);
document.write( " is "+ root.data + "<br>");
return null;
}
}
return root;
}
return null;
}
// function to find inorder successor of
// a node
function inorderSuccessor(root,x)
{
// Case1: If right child is not null
if (x.right != null)
{
let inorderSucc = leftMostNode(x.right);
document.write("Inorder Successor of "+x.data+" is ");
document.write(inorderSucc.data+"<br>");
}
// Case2: If right child is null
if (x.right == null)
{
let f = 0;
let rightMost = rightMostNode(root);
// case3: If x is the right most node
if (rightMost == x)
document.write("No inorder successor! Right most node.\n");
else
findInorderRecursive(root, x);
}
}
// Driver program to test above functions
// Let's construct the binary tree
// as shown in above diagram
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.right = new Node(6);
// Case 1
inorderSuccessor(root, root.right);
// case 2
inorderSuccessor(root, root.left.left);
// case 3
inorderSuccessor(root, root.right.right);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Inorder Successor of 1 is 6 Inorder Successor of 4 is 2 No inorder successor! Right most node.
Otro enfoque:
haremos un recorrido en orden inverso y mantendremos el seguimiento del Node visitado actual. Una vez que encontramos el elemento, el último elemento rastreado sería nuestra respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find inorder successor.
#include<bits/stdc++.h>
using namespace std;
// structure of a Binary Node.
struct Node
{
int data;
Node* left;
Node* right;
};
// Function to create a new Node.
Node* newNode(int val)
{
Node* temp = new Node;
temp->data = val;
temp->left = NULL;
temp->right = NULL;
return temp;
}
// function that prints the inorder successor
// of a target node. next will point the last
// tracked node, which will be the answer.
void inorderSuccessor(Node* root,
Node* target_node,
Node* &next)
{
// if root is null then return
if(!root)
return;
inorderSuccessor(root->right, target_node, next);
// if target node found then enter this condition
if(root->data == target_node->data)
{
// this will be true to the last node
// in inorder traversal i.e., rightmost node.
if(next == NULL)
cout << "inorder successor of "
<< root->data << " is: null\n";
else
cout << "inorder successor of "
<< root->data << " is: "
<< next->data << "\n";
}
next = root;
inorderSuccessor(root->left, target_node, next);
}
// Driver Code
int main()
{
// Let's construct the binary tree
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
// Case 1
Node* next = NULL;
inorderSuccessor(root, root, next);
// case 2
next = NULL;
inorderSuccessor(root, root->left->left, next);
// case 3
next = NULL;
inorderSuccessor(root, root->right->right, next);
return 0;
}
// This code is contributed by AASTHA VARMA
Java
// Java program to find inorder successor of a node.
class Node {
int data;
Node left, right;
Node(int data) {
this.data = data;
left = null; right = null;
}
}
// class to find inorder successor of
// a node
class InorderSuccessor {
Node root;
// to change previous node
static class PreviousNode {
Node pNode;
PreviousNode() {
pNode = null;
}
}
// function to find inorder successor of
// a node
private void inOrderSuccessorOfBinaryTree(Node root,
PreviousNode pre, int searchNode)
{
// Case1: If right child is not NULL
if(root.right != null)
inOrderSuccessorOfBinaryTree(root.right, pre, searchNode);
// Case2: If root data is equal to search node
if(root.data == searchNode)
System.out.println("inorder successor of " + searchNode + " is: "
+ (pre.pNode != null ? pre.pNode.data : "null"));
pre.pNode = root;
if(root.left != null)
inOrderSuccessorOfBinaryTree(root.left, pre, searchNode);
}
// Driver program to test above functions
public static void main(String[] args)
{
InorderSuccessor tree = new InorderSuccessor();
// Let's construct the binary tree
// as shown in above diagram
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(6);
// Case 1
tree.inOrderSuccessorOfBinaryTree(tree.root,
new PreviousNode(), 3);
// Case 2
tree.inOrderSuccessorOfBinaryTree(tree.root,
new PreviousNode(), 4);
// Case 3
tree.inOrderSuccessorOfBinaryTree(tree.root,
new PreviousNode(), 6);
}
}
// This code is contributed by Ashish Goyal.
Python3
# Python3 program to find inorder successor.
# A Binary Tree Node
# Utility function to create a new tree node
class Node:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Function to create a new Node.
def newNode(val):
temp = Node(0)
temp.data = val
temp.left = None
temp.right = None
return temp
# function that prints the inorder successor
# of a target node. next will point the last
# tracked node, which will be the answer.
def inorderSuccessor(root, target_node):
global next
# if root is None then return
if(root == None):
return
inorderSuccessor(root.right, target_node)
# if target node found, then
# enter this condition
if(root.data == target_node.data):
# this will be true to the last node
# in inorder traversal i.e., rightmost node.
if(next == None):
print ("inorder successor of",
root.data , " is: None")
else:
print ( "inorder successor of",
root.data , "is:", next.data)
next = root
inorderSuccessor(root.left, target_node)
# global variable
next = None
# Driver Code
if __name__ == '__main__':
# Let's construct the binary tree
# as shown in above diagram.
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.left = newNode(4)
root.left.right = newNode(5)
root.right.right = newNode(6)
# Case 1
next = None
inorderSuccessor(root, root.right)
# case 2
next = None
inorderSuccessor(root, root.left.left)
# case 3
next = None
inorderSuccessor(root, root.right.right)
# This code is contributed by Arnab Kundu
C#
// C# program to find inorder successor of a node.
using System;
class Node
{
public int data;
public Node left, right;
public Node(int data)
{
this.data = data;
left = null; right = null;
}
}
// class to find inorder successor of
// a node
public class InorderSuccessor
{
Node root;
// to change previous node
class PreviousNode
{
public Node pNode;
public PreviousNode()
{
pNode = null;
}
}
// function to find inorder successor of
// a node
private void inOrderSuccessorOfBinaryTree(Node root,
PreviousNode pre, int searchNode)
{
// Case1: If right child is not NULL
if(root.right != null)
inOrderSuccessorOfBinaryTree(root.right,
pre, searchNode);
// Case2: If root data is equal to search node
if(root.data == searchNode)
{
Console.Write("inorder successor of " +
searchNode + " is: ");
if(pre.pNode != null)
Console.WriteLine(pre.pNode.data);
else
Console.WriteLine("null");
}
pre.pNode = root;
if(root.left != null)
inOrderSuccessorOfBinaryTree(root.left,
pre, searchNode);
}
// Driver code
public static void Main(String[] args)
{
InorderSuccessor tree = new InorderSuccessor();
// Let's construct the binary tree
// as shown in above diagram
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(6);
// Case 1
tree.inOrderSuccessorOfBinaryTree(tree.root,
new PreviousNode(), 3);
// Case 2
tree.inOrderSuccessorOfBinaryTree(tree.root,
new PreviousNode(), 4);
// Case 3
tree.inOrderSuccessorOfBinaryTree(tree.root,
new PreviousNode(), 6);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to find inorder successor of a node.
class Node
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// class to find inorder successor of
// a node
var root = null;
// to change previous node
class PreviousNode
{
constructor()
{
this.pNode = null;
}
}
// function to find inorder successor of
// a node
function inOrderSuccessorOfBinaryTree(root, pre, searchNode)
{
// Case1: If right child is not NULL
if(root.right != null)
inOrderSuccessorOfBinaryTree(root.right,
pre, searchNode);
// Case2: If root data is equal to search node
if(root.data == searchNode)
{
document.write("inorder successor of " +
searchNode + " is: ");
if(pre.pNode != null)
document.write(pre.pNode.data+"<br>");
else
document.write("null<br>");
}
pre.pNode = root;
if(root.left != null)
inOrderSuccessorOfBinaryTree(root.left,
pre, searchNode);
}
// Driver code
// Let's construct the binary tree
// as shown in above diagram
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.right = new Node(6);
// Case 1
inOrderSuccessorOfBinaryTree(root,
new PreviousNode(), 3);
// Case 2
inOrderSuccessorOfBinaryTree(root,
new PreviousNode(), 4);
// Case 3
inOrderSuccessorOfBinaryTree(root,
new PreviousNode(), 6);
</script>
Producción:
inorder successor of 1 is: 6 inorder successor of 4 is: 2 inorder successor of 7 is: null
Complejidad de tiempo : O( n ), donde n es el número de Nodes en el árbol.
Complejidad del espacio : O (n) para la pila de llamadas
Este artículo es una contribución de Harsh Agarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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