Dado un árbol binario donde cada Node tiene la siguiente estructura, escriba una función para completar el siguiente puntero para todos los Nodes. El próximo puntero para cada Node debe configurarse para que apunte al sucesor en orden.
C++
class node {
public:
int data;
node* left;
node* right;
node* next;
};
// This code is contributed
// by Shubham Singh
C
struct node {
int data;
struct node* left;
struct node* right;
struct node* next;
}
Java
// A binary tree node
class Node {
int data;
Node left, right, next;
Node(int item)
{
data = item;
left = right = next = null;
}
}
// This code is contributed by SUBHAMSINGH10.
Python3
class Node: def __init__(self, data): self.data = data self.left = None self.right = None self.next = None # This code is contributed by Shubham Singh
C#
class Node {
public int data;
public Node left, right, next;
public Node(int item)
{
data = item;
left = right = next = null;
}
}
Node root;
// This code is contributed
// by Shubham Singh
Javascript
<script>
class Node
{
constructor(x) {
this.data = x;
this.left = null;
this.right = null;
}
}
// This code is contributed by Shubham Singh
</script>
Inicialmente, todos los punteros siguientes tienen valores NULL. Su función debe llenar estos punteros siguientes para que apunten a un sucesor en orden.
C++
// C++ program to populate inorder
// traversal of all nodes
#include <bits/stdc++.h>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
node* next;
};
/* Set next of p and all descendants of p
by traversing them in reverse Inorder */
void populateNext(node* p)
{
// The first visited node will be the
// rightmost node next of the rightmost
// node will be NULL
static node* next = NULL;
if (p) {
// First set the next pointer
// in right subtree
populateNext(p->right);
// Set the next as previously visited
// node in reverse Inorder
p->next = next;
// Change the prev for subsequent node
next = p;
// Finally, set the next pointer in
// left subtree
populateNext(p->left);
}
}
/* UTILITY FUNCTIONS */
/* Helper function that allocates a new
node with the given data and NULL left
and right pointers. */
node* newnode(int data)
{
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
Node->next = NULL;
return (Node);
}
// Driver Code
int main()
{
/* Constructed binary tree is
10
/ \
8 12
/
3
*/
node* root = newnode(10);
root->left = newnode(8);
root->right = newnode(12);
root->left->left = newnode(3);
// Populates nextRight pointer in all nodes
populateNext(root);
// Let us see the populated values
node* ptr = root->left->left;
while (ptr) {
// -1 is printed if there is no successor
cout << "Next of " << ptr->data << " is "
<< (ptr->next ? ptr->next->data : -1) << endl;
ptr = ptr->next;
}
return 0;
}
// This code is contributed by rathbhupendra
Java
// Java program to populate inorder traversal of all nodes
// A binary tree node
class Node {
int data;
Node left, right, next;
Node(int item)
{
data = item;
left = right = next = null;
}
}
class BinaryTree {
Node root;
static Node next = null;
/* Set next of p and all descendants of p by traversing
them in reverse Inorder */
void populateNext(Node node)
{
// The first visited node will be the rightmost node
// next of the rightmost node will be NULL
if (node != null) {
// First set the next pointer in right subtree
populateNext(node.right);
// Set the next as previously visited node in
// reverse Inorder
node.next = next;
// Change the prev for subsequent node
next = node;
// Finally, set the next pointer in left subtree
populateNext(node.left);
}
}
/* Driver program to test above functions*/
public static void main(String args[])
{
/* Constructed binary tree is
10
/ \
8 12
/
3 */
BinaryTree tree = new BinaryTree();
tree.root = new Node(10);
tree.root.left = new Node(8);
tree.root.right = new Node(12);
tree.root.left.left = new Node(3);
// Populates nextRight pointer in all nodes
tree.populateNext(tree.root);
// Let us see the populated values
Node ptr = tree.root.left.left;
while (ptr != null) {
// -1 is printed if there is no successor
int print
= ptr.next != null ? ptr.next.data : -1;
System.out.println("Next of " + ptr.data
+ " is: " + print);
ptr = ptr.next;
}
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# Python3 program to populate
# inorder traversal of all nodes
# Tree node
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.next = None
# The first visited node will be
# the rightmost node next of the
# rightmost node will be None
next = None
# Set next of p and all descendants of p
# by traversing them in reverse Inorder
def populateNext(p):
global next
if (p != None):
# First set the next pointer
# in right subtree
populateNext(p.right)
# Set the next as previously visited node
# in reverse Inorder
p.next = next
# Change the prev for subsequent node
next = p
# Finally, set the next pointer
# in left subtree
populateNext(p.left)
# UTILITY FUNCTIONS
# Helper function that allocates
# a new node with the given data
# and None left and right pointers.
def newnode(data):
node = Node(0)
node.data = data
node.left = None
node.right = None
node.next = None
return(node)
# Driver Code
# Constructed binary tree is
# 10
# / \
# 8 12
# /
# 3
root = newnode(10)
root.left = newnode(8)
root.right = newnode(12)
root.left.left = newnode(3)
# Populates nextRight pointer
# in all nodes
p = populateNext(root)
# Let us see the populated values
ptr = root.left.left
while(ptr != None):
out = 0
if(ptr.next != None):
out = ptr.next.data
else:
out = -1
# -1 is printed if there is no successor
print("Next of", ptr.data, "is", out)
ptr = ptr.next
# This code is contributed by Arnab Kundu
C#
// C# program to populate inorder traversal of all nodes
using System;
class BinaryTree {
// A binary tree node
class Node {
public int data;
public Node left, right, next;
public Node(int item)
{
data = item;
left = right = next = null;
}
}
Node root;
static Node next = null;
/* Set next of p and all descendants of p by traversing
them in reverse Inorder */
void populateNext(Node node)
{
// The first visited node will be the rightmost node
// next of the rightmost node will be NULL
if (node != null) {
// First set the next pointer in right subtree
populateNext(node.right);
// Set the next as previously visited node in
// reverse Inorder
node.next = next;
// Change the prev for subsequent node
next = node;
// Finally, set the next pointer in left subtree
populateNext(node.left);
}
}
/* Driver program to test above functions*/
static public void Main(String[] args)
{
/* Constructed binary tree is
10
/ \
8 12
/
3 */
BinaryTree tree = new BinaryTree();
tree.root = new Node(10);
tree.root.left = new Node(8);
tree.root.right = new Node(12);
tree.root.left.left = new Node(3);
// Populates nextRight pointer in all nodes
tree.populateNext(tree.root);
// Let us see the populated values
Node ptr = tree.root.left.left;
while (ptr != null) {
// -1 is printed if there is no successor
int print
= ptr.next != null ? ptr.next.data : -1;
Console.WriteLine("Next of " + ptr.data
+ " is: " + print);
ptr = ptr.next;
}
}
}
// This code has been contributed by Arnab Kundu
Javascript
<script>
// Javascript program to populate inorder traversal of all nodes
// A binary tree node
class Node
{
constructor(x) {
this.data = x;
this.left = null;
this.right = null;
}
}
let root;
let next = null;
/* Set next of p and all descendants of p by traversing them in
reverse Inorder */
function populateNext(node)
{
// The first visited node will be the rightmost node
// next of the rightmost node will be NULL
if (node != null)
{
// First set the next pointer in right subtree
populateNext(node.right);
// Set the next as previously visited node in reverse Inorder
node.next = next;
// Change the prev for subsequent node
next = node;
// Finally, set the next pointer in left subtree
populateNext(node.left);
}
}
/* Driver program to test above functions*/
/* Constructed binary tree is
10
/ \
8 12
/
3 */
root = new Node(10)
root.left = new Node(8)
root.right = new Node(12)
root.left.left = new Node(3)
// Populates nextRight pointer
// in all nodes
p = populateNext(root)
// Let us see the populated values
ptr = root.left.left
while (ptr != null)
{
// -1 is printed if there is no successor
let print = ptr.next != null ? ptr.next.data : -1;
document.write("Next of " + ptr.data + " is: " + print+"<br>");
ptr = ptr.next;
}
// This code is contributed by unknown2108
</script>
C++
// An implementation that doesn't use static variable
// A wrapper over populateNextRecur
void populateNext(node* root)
{
// The first visited node will be the rightmost node
// next of the rightmost node will be NULL
node* next = NULL;
populateNextRecur(root, &next);
}
/* Set next of all descendants of p by
traversing them in reverse Inorder */
void populateNextRecur(node* p, node** next_ref)
{
if (p) {
// First set the next pointer in right subtree
populateNextRecur(p->right, next_ref);
// Set the next as previously visited
// node in reverse Inorder
p->next = *next_ref;
// Change the prev for subsequent node
*next_ref = p;
// Finally, set the next pointer in right subtree
populateNextRecur(p->left, next_ref);
}
}
// This is code is contributed by rathbhupendra
C
// An implementation that doesn't use static variable
// A wrapper over populateNextRecur
void populateNext(struct node* root)
{
// The first visited node will be the rightmost node
// next of the rightmost node will be NULL
struct node* next = NULL;
populateNextRecur(root, &next);
}
/* Set next of all descendants of p by traversing them in
* reverse Inorder */
void populateNextRecur(struct node* p,
struct node** next_ref)
{
if (p) {
// First set the next pointer in right subtree
populateNextRecur(p->right, next_ref);
// Set the next as previously visited node in
// reverse Inorder
p->next = *next_ref;
// Change the prev for subsequent node
*next_ref = p;
// Finally, set the next pointer in right subtree
populateNextRecur(p->left, next_ref);
}
}
Java
// A wrapper over populateNextRecur
void populateNext(Node node)
{
// The first visited node will be the rightmost node
// next of the rightmost node will be NULL
populateNextRecur(node, next);
}
/* Set next of all descendants of p by traversing them in
* reverse Inorder */
void populateNextRecur(Node p, Node next_ref)
{
if (p != null) {
// First set the next pointer in right subtree
populateNextRecur(p.right, next_ref);
// Set the next as previously visited node in
// reverse Inorder
p.next = next_ref;
// Change the prev for subsequent node
next_ref = p;
// Finally, set the next pointer in right subtree
populateNextRecur(p.left, next_ref);
}
}
Python3
# A wrapper over populateNextRecur def populateNext(node): # The first visited node will be the rightmost node # next of the rightmost node will be NULL populateNextRecur(node, next) # /* Set next of all descendants of p by # traversing them in reverse Inorder */ def populateNextRecur(p, next_ref): if (p != None): # First set the next pointer in right subtree populateNextRecur(p.right, next_ref) # Set the next as previously visited node in reverse Inorder p.next = next_ref # Change the prev for subsequent node next_ref = p # Finally, set the next pointer in right subtree populateNextRecur(p.left, next_ref) # This code is contributed by Mohit kumar 29
C#
// A wrapper over populateNextRecur
void populateNext(Node node)
{
// The first visited node will be the rightmost node
// next of the rightmost node will be NULL
populateNextRecur(node, next);
}
/* Set next of all descendants of p by
traversing them in reverse Inorder */
void populateNextRecur(Node p, Node next_ref)
{
if (p != null) {
// First set the next pointer in right subtree
populateNextRecur(p.right, next_ref);
// Set the next as previously visited node in
// reverse Inorder
p.next = next_ref;
// Change the prev for subsequent node
next_ref = p;
// Finally, set the next pointer in right subtree
populateNextRecur(p.left, next_ref);
}
}
// This code is contributed by princiraj1992
Javascript
<script>
// A wrapper over populateNextRecur
function populateNext(node)
{
// The first visited node will be the rightmost node
// next of the rightmost node will be NULL
populateNextRecur(node, next);
}
/* Set next of all descendants of p by
traversing them in reverse Inorder */
function populateNextRecur(p, next_ref)
{
if (p != null)
{
// First set the next pointer in right subtree
populateNextRecur(p.right, next_ref);
// Set the next as previously visited node in reverse Inorder
p.next = next_ref;
// Change the prev for subsequent node
next_ref = p;
// Finally, set the next pointer in right subtree
populateNextRecur(p.left, next_ref);
}
}
// This code is contributed by importantly.
</script>
Java
import java.util.ArrayList;
// class Node
class Node {
int data;
Node left, right, next;
// constructor for initializing key value and all the
// pointers
Node(int data)
{
this.data = data;
left = right = next = null;
}
}
public class Solution {
Node root = null;
// list to store inorder sequence
ArrayList<Node> list = new ArrayList<>();
// function for populating next pointer to inorder
// successor
void populateNext()
{
// list = [3,8,10,12]
// inorder successor of the present node is the
// immediate right node for ex: inorder successor of
// 3 is 8
for (int i = 0; i < list.size(); i++) {
// check if it is the last node
// point next of last node(right most) to null
if (i != list.size() - 1) {
list.get(i).next = list.get(i + 1);
}
else {
list.get(i).next = null;
}
}
// Let us see the populated values
Node ptr = root.left.left;
while (ptr != null) {
// -1 is printed if there is no successor
int print
= ptr.next != null ? ptr.next.data : -1;
System.out.println("Next of " + ptr.data
+ " is: " + print);
ptr = ptr.next;
}
}
// insert the inorder into a list to keep track
// of the inorder successor
void inorder(Node root)
{
if (root != null) {
inorder(root.left);
list.add(root);
inorder(root.right);
}
}
// Driver function
public static void main(String args[])
{
Solution tree = new Solution();
/* 10
/ \
8 12
/
3 */
tree.root = new Node(10);
tree.root.left = new Node(8);
tree.root.right = new Node(12);
tree.root.left.left = new Node(3);
// function calls
tree.inorder(tree.root);
tree.populateNext();
}
}
Python3
# class Node
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.right = None
self.left = None
root = None
# list to store inorder sequence
list = []
# function for populating next pointer to inorder successor
def populateNext(root):
# list = [3,8,10,12]
# inorder successor of the present Node is the immediate
# right Node
# for ex: inorder successor of 3 is 8
for i in range(len(list)):
# check if it is the last Node
# point next of last Node(right most) to None
if (i != len(list) - 1):
list[i].next = list[i + 1]
else:
list[i].next = None
# Let us see the populated values
ptr = root.left.left
while (ptr != None):
# -1 is printed if there is no successor
pt = -1
if(ptr.next != None):
pt = ptr.next.data
print("Next of ", ptr.data, " is: ", pt)
ptr = ptr.next
# insert the inorder into a list to keep track
# of the inorder successor
def inorder(root):
if (root != None):
inorder(root.left)
list.append(root)
inorder(root.right)
# Driver function
if __name__ == '__main__':
'''
* 10 / \ 8 12 / 3
'''
root = Node(10)
root.left = Node(8)
root.right = Node(12)
root.left.left = Node(3)
# function calls
inorder(root)
populateNext(root)
# This code is contributed by Rajput-Ji
C#
using System;
using System.Collections.Generic;
// class Node
public class Node {
public
int data;
public
Node left,
right, next;
// constructor for initializing key value and all the
// pointers
public
Node(int data)
{
this.data = data;
left = right = next = null;
}
}
public class Solution {
Node root = null;
// list to store inorder sequence
List<Node> list = new List<Node>();
// function for populating next pointer to inorder
// successor
void populateNext()
{
// list = [3,8,10,12]
// inorder successor of the present node is the
// immediate right node for ex: inorder successor of
// 3 is 8
for (int i = 0; i < list.Count; i++) {
// check if it is the last node
// point next of last node(right most) to null
if (i != list.Count - 1) {
list[i].next = list[i + 1];
}
else {
list[i].next = null;
}
}
// Let us see the populated values
Node ptr = root.left.left;
while (ptr != null) {
// -1 is printed if there is no successor
int print
= ptr.next != null ? ptr.next.data : -1;
Console.WriteLine("Next of " + ptr.data
+ " is: " + print);
ptr = ptr.next;
}
}
// insert the inorder into a list to keep track
// of the inorder successor
void inorder(Node root)
{
if (root != null) {
inorder(root.left);
list.Add(root);
inorder(root.right);
}
}
// Driver function
public static void Main(String[] args)
{
Solution tree = new Solution();
/*
* 10 / \ 8 12 / 3
*/
tree.root = new Node(10);
tree.root.left = new Node(8);
tree.root.right = new Node(12);
tree.root.left.left = new Node(3);
// function calls
tree.inorder(tree.root);
tree.populateNext();
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// class Node
class Node
{
// constructor for initializing key value and all the
// pointers
constructor(data)
{
this.data = data;
this.left = this.right = this.next = null;
}
}
let root = null;
// list to store inorder sequence
let list = [];
// function for populating next pointer to inorder successor
function populateNext()
{
// list = [3,8,10,12]
// inorder successor of the present node is the immediate
// right node
// for ex: inorder successor of 3 is 8
for(let i = 0; i < list.length; i++)
{
// check if it is the last node
// point next of last node(right most) to null
if(i != list.length - 1)
{
list[i].next = list[i + 1];
}
else {
list[i].next = null;
}
}
// Let us see the populated values
let ptr = root.left.left;
while (ptr != null)
{
// -1 is printed if there is no successor
let print = ptr.next != null ? ptr.next.data : -1;
document.write("Next of " + ptr.data + " is: " + print+"<br>");
ptr = ptr.next;
}
}
// insert the inorder into a list to keep track
// of the inorder successor
function inorder(root)
{
if(root != null)
{
inorder(root.left);
list.push(root);
inorder(root.right);
}
}
// Driver function
/* 10
/ \
8 12
/
3 */
root = new Node(10);
root.left = new Node(8);
root.right = new Node(12);
root.left.left = new Node(3);
// function calls
inorder(root);
populateNext();
// This code is contributed by avanitrachhadiya2155
</script>
C++
#include <iostream>
#include <stack>
using namespace std;
struct Node {
int data;
struct Node* left;
struct Node* right;
struct Node* next;
Node(int x)
{
data = x;
left = NULL;
right = NULL;
next = NULL;
}
};
Node* inorder(Node* root)
{
if (root->left == NULL)
return root;
inorder(root->left);
}
void populateNext(Node* root)
{
stack<Node*> s;
Node* temp = root;
while (temp->left) {
s.push(temp);
temp = temp->left;
}
Node* curr = temp;
if (curr->right) {
Node* q = curr->right;
while (q) {
s.push(q);
q = q->left;
}
}
while (!s.empty()) {
Node* inorder = s.top();
s.pop();
curr->next = inorder;
if (inorder->right) {
Node* q = inorder->right;
while (q) {
s.push(q);
q = q->left;
}
}
curr = inorder;
}
}
Node* newnode(int data)
{
Node* node = new Node(data);
return (node);
}
int main()
{
/* Constructed binary tree is
10
/ \
8 12
/
3
*/
Node* root = newnode(10);
root->left = newnode(8);
root->right = newnode(12);
root->left->left = newnode(3);
populateNext(root);
Node* ptr = inorder(root);
while (ptr) {
// -1 is printed if there is no successor
cout << "Next of " << ptr->data << " is "
<< (ptr->next ? ptr->next->data : -1) << endl;
ptr = ptr->next;
}
return 0;
}
Java
import java.util.*;
class GFG{
static class Node {
int data;
Node left;
Node right;
Node next;
Node(int x)
{
data = x;
left = null;
right = null;
next = null;
}
};
static Node inorder(Node root)
{
if (root.left == null)
return root;
root = inorder(root.left);
return root;
}
static void populateNext(Node root)
{
Stack<Node> s = new Stack<>();
Node temp = root;
while (temp.left!=null) {
s.add(temp);
temp = temp.left;
}
Node curr = temp;
if (curr.right!=null) {
Node q = curr.right;
while (q!=null) {
s.add(q);
q = q.left;
}
}
while (!s.isEmpty()) {
Node inorder = s.peek();
s.pop();
curr.next = inorder;
if (inorder.right!=null) {
Node q = inorder.right;
while (q!=null) {
s.add(q);
q = q.left;
}
}
curr = inorder;
}
}
static Node newnode(int data)
{
Node node = new Node(data);
return (node);
}
public static void main(String[] args)
{
/* Constructed binary tree is
10
/ \
8 12
/
3
*/
Node root = newnode(10);
root.left = newnode(8);
root.right = newnode(12);
root.left.left = newnode(3);
populateNext(root);
Node ptr = inorder(root);
while (ptr != null)
{
// -1 is printed if there is no successor
System.out.print("Next of " + ptr.data+ " is "
+ (ptr.next!=null ? ptr.next.data : -1) +"\n");
ptr = ptr.next;
}
}
}
// This code is contributed by Rajput-Ji
Python3
class GFG:
class Node:
data = 0
left = None
right = None
next = None
def __init__(self, x):
self.data = x
self.left = None
self.right = None
self.next = None
@staticmethod
def inorder(root):
if (root.left == None):
return root
root = GFG.inorder(root.left)
return root
@staticmethod
def populateNext(root):
s = []
temp = root
while (temp.left != None):
s.append(temp)
temp = temp.left
curr = temp
if (curr.right != None):
q = curr.right
while (q != None):
s.append(q)
q = q.left
while (not (len(s) == 0)):
inorder = s[-1]
s.pop()
curr.next = inorder
if (inorder.right != None):
q = inorder.right
while (q != None):
s.append(q)
q = q.left
curr = inorder
@staticmethod
def newnode(data):
node = GFG.Node(data)
return (node)
@staticmethod
def main(args):
# Constructed binary tree is
# 10
# / \
# 8 12
# /
# 3
root = GFG.newnode(10)
root.left = GFG.newnode(8)
root.right = GFG.newnode(12)
root.left.left = GFG.newnode(3)
GFG.populateNext(root)
ptr = GFG.inorder(root)
while (ptr != None):
# -1 is printed if there is no successor
print("Next of " + str(ptr.data) + " is " +
str((ptr.next.data if ptr.next != None else -1)) + "\n", end="")
ptr = ptr.next
if __name__ == "__main__":
GFG.main([])
# This code is contributed by mukulsomukesh
C#
using System;
using System.Collections.Generic;
public class GFG {
public class Node {
public int data;
public Node left;
public Node right;
public Node next;
public Node(int x) {
data = x;
left = null;
right = null;
next = null;
}
};
static Node inorder(Node root) {
if (root.left == null)
return root;
root = inorder(root.left);
return root;
}
static void populateNext(Node root) {
Stack<Node> s = new Stack<Node>();
Node temp = root;
while (temp.left != null) {
s.Push(temp);
temp = temp.left;
}
Node curr = temp;
if (curr.right != null) {
Node q = curr.right;
while (q != null) {
s.Push(q);
q = q.left;
}
}
while (s.Count!=0) {
Node inorder = s.Peek();
s.Pop();
curr.next = inorder;
if (inorder.right != null) {
Node q = inorder.right;
while (q != null) {
s.Push(q);
q = q.left;
}
}
curr = inorder;
}
}
static Node newnode(int data) {
Node node = new Node(data);
return (node);
}
public static void Main(String[] args) {
/*
* Constructed binary tree is 10 / \ 8 12 / 3
*/
Node root = newnode(10);
root.left = newnode(8);
root.right = newnode(12);
root.left.left = newnode(3);
populateNext(root);
Node ptr = inorder(root);
while (ptr != null) {
// -1 is printed if there is no successor
Console.Write("Next of " + ptr.data + " is " + (ptr.next != null ? ptr.next.data : -1) + "\n");
ptr = ptr.next;
}
}
}
// This code contributed by Rajput-Ji
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