Dado un árbol binario. Modifíquelo de tal manera que después de la modificación pueda tener un recorrido de orden anticipado utilizando solo los punteros correctos. Durante la modificación, puede usar punteros tanto a la derecha como a la izquierda.
Ejemplos:
Input : 10
/ \
8 2
/ \
3 5
Output : 10
\
8
\
3
\
5
\
2
Explanation : The preorder traversal
of given binary tree is 10 8 3 5 2.
C++
// C code to modify binary tree for
// traversal using only right pointer
#include <bits/stdc++.h>
using namespace std;
// A binary tree node has data,
// left child and right child
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// function that allocates a new node
// with the given data and NULL left
// and right pointers.
struct Node* newNode(int data)
{
struct Node* node = new struct Node;
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
// Function to modify tree
struct Node* modifytree(struct Node* root)
{
struct Node* right = root->right;
struct Node* rightMost = root;
// if the left tree exists
if (root->left) {
// get the right-most of the
// original left subtree
rightMost = modifytree(root->left);
// set root right to left subtree
root->right = root->left;
root->left = NULL;
}
// if the right subtree does
// not exists we are done!
if (!right)
return rightMost;
// set right pointer of right-most
// of the original left subtree
rightMost->right = right;
// modify the rightsubtree
rightMost = modifytree(right);
return rightMost;
}
// printing using right pointer only
void printpre(struct Node* root)
{
while (root != NULL) {
cout << root->data << " ";
root = root->right;
}
}
// Driver program to test above functions
int main()
{
/* Constructed binary tree is
10
/ \
8 2
/ \
3 5 */
struct Node* root = newNode(10);
root->left = newNode(8);
root->right = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(5);
modifytree(root);
printpre(root);
return 0;
}
Java
// Java code to modify binary tree for
// traversal using only right pointer
class GFG
{
// A binary tree node has data,
// left child and right child
static class Node
{
int data;
Node left;
Node right;
};
// function that allocates a new node
// with the given data and null left
// and right pointers.
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = null;
node.right = null;
return (node);
}
// Function to modify tree
static Node modifytree( Node root)
{
Node right = root.right;
Node rightMost = root;
// if the left tree exists
if (root.left != null)
{
// get the right-most of the
// original left subtree
rightMost = modifytree(root.left);
// set root right to left subtree
root.right = root.left;
root.left = null;
}
// if the right subtree does
// not exists we are done!
if (right == null)
return rightMost;
// set right pointer of right-most
// of the original left subtree
rightMost.right = right;
// modify the rightsubtree
rightMost = modifytree(right);
return rightMost;
}
// printing using right pointer only
static void printpre( Node root)
{
while (root != null)
{
System.out.print( root.data + " ");
root = root.right;
}
}
// Driver cde
public static void main(String args[])
{
/* Constructed binary tree is
10
/ \
8 2
/ \
3 5 */
Node root = newNode(10);
root.left = newNode(8);
root.right = newNode(2);
root.left.left = newNode(3);
root.left.right = newNode(5);
modifytree(root);
printpre(root);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python code to modify binary tree for # traversal using only right pointer class newNode(): def __init__(self, data): self.data = data self.left = None self.right = None # Function to modify tree def modifytree(root): right = root.right rightMost = root # if the left tree exists if (root.left): # get the right-most of the # original left subtree rightMost = modifytree(root.left) # set root right to left subtree root.right = root.left root.left = None # if the right subtree does # not exists we are done! if (not right): return rightMost # set right pointer of right-most # of the original left subtree rightMost.right = right # modify the rightsubtree rightMost = modifytree(right) return rightMost # printing using right pointer only def printpre(root): while (root != None): print(root.data,end=" ") root = root.right # Driver code if __name__ == '__main__': """ Constructed binary tree is 10 / \ 8 2 / \ 3 5 """ root = newNode(10) root.left = newNode(8) root.right = newNode(2) root.left.left = newNode(3) root.left.right = newNode(5) modifytree(root) printpre(root) # This code is contributed by SHUBHAMSINGH10
C#
// C# code to modify binary tree for
// traversal using only right pointer
using System;
class GFG
{
// A binary tree node has data,
// left child and right child
public class Node
{
public int data;
public Node left;
public Node right;
};
// function that allocates a new node
// with the given data and null left
// and right pointers.
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = null;
node.right = null;
return (node);
}
// Function to modify tree
static Node modifytree( Node root)
{
Node right = root.right;
Node rightMost = root;
// if the left tree exists
if (root.left != null)
{
// get the right-most of the
// original left subtree
rightMost = modifytree(root.left);
// set root right to left subtree
root.right = root.left;
root.left = null;
}
// if the right subtree does
// not exists we are done!
if (right == null)
return rightMost;
// set right pointer of right-most
// of the original left subtree
rightMost.right = right;
// modify the rightsubtree
rightMost = modifytree(right);
return rightMost;
}
// printing using right pointer only
static void printpre( Node root)
{
while (root != null)
{
Console.Write( root.data + " ");
root = root.right;
}
}
// Driver cde
public static void Main(String []args)
{
/* Constructed binary tree is
10
/ \
8 2
/ \
3 5 */
Node root = newNode(10);
root.left = newNode(8);
root.right = newNode(2);
root.left.left = newNode(3);
root.left.right = newNode(5);
modifytree(root);
printpre(root);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript code to modify binary tree for
// traversal using only right pointer
// A binary tree node has data,
// left child and right child
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// function that allocates a new node
// with the given data and null left
// and right pointers.
function newNode(data)
{
let node = new Node(data);
return (node);
}
// Function to modify tree
function modifytree(root)
{
let right = root.right;
let rightMost = root;
// if the left tree exists
if (root.left != null)
{
// get the right-most of the
// original left subtree
rightMost = modifytree(root.left);
// set root right to left subtree
root.right = root.left;
root.left = null;
}
// if the right subtree does
// not exists we are done!
if (right == null)
return rightMost;
// set right pointer of right-most
// of the original left subtree
rightMost.right = right;
// modify the rightsubtree
rightMost = modifytree(right);
return rightMost;
}
// printing using right pointer only
function printpre(root)
{
while (root != null)
{
document.write( root.data + " ");
root = root.right;
}
}
/* Constructed binary tree is
10
/ \
8 2
/ \
3 5 */
let root = newNode(10);
root.left = newNode(8);
root.right = newNode(2);
root.left.left = newNode(3);
root.left.right = newNode(5);
modifytree(root);
printpre(root);
</script>
C++
// C++ code to modify binary tree for
// traversal using only right pointer
#include <iostream>
#include <stack>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
// A binary tree node has data,
// left child and right child
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Helper function that allocates a new
// node with the given data and NULL
// left and right pointers.
struct Node* newNode(int data)
{
struct Node* node = new struct Node;
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
// An iterative process to set the right
// pointer of Binary tree
void modifytree(struct Node* root)
{
// Base Case
if (root == NULL)
return;
// Create an empty stack and push root to it
stack<Node*> nodeStack;
nodeStack.push(root);
/* Pop all items one by one.
Do following for every popped item
a) print it
b) push its right child
c) push its left child
Note that right child is pushed first
so that left is processed first */
struct Node* pre = NULL;
while (nodeStack.empty() == false) {
// Pop the top item from stack
struct Node* node = nodeStack.top();
nodeStack.pop();
// Push right and left children of
// the popped node to stack
if (node->right)
nodeStack.push(node->right);
if (node->left)
nodeStack.push(node->left);
// check if some previous node exists
if (pre != NULL) {
// set the right pointer of
// previous node to current
pre->right = node;
}
// set previous node as current node
pre = node;
}
}
// printing using right pointer only
void printpre(struct Node* root)
{
while (root != NULL) {
cout << root->data << " ";
root = root->right;
}
}
// Driver code
int main()
{
/* Constructed binary tree is
10
/ \
8 2
/ \
3 5
*/
struct Node* root = newNode(10);
root->left = newNode(8);
root->right = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(5);
modifytree(root);
printpre(root);
return 0;
}
Java
// Java code to modify binary tree for
// traversal using only right pointer
import java.util.*;
class GfG {
// A binary tree node has data,
// left child and right child
static class Node {
int data;
Node left;
Node right;
}
// Helper function that allocates a new
// node with the given data and NULL
// left and right pointers.
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = null;
node.right = null;
return (node);
}
// An iterative process to set the right
// pointer of Binary tree
static void modifytree(Node root)
{
// Base Case
if (root == null)
return;
// Create an empty stack and push root to it
Stack<Node> nodeStack = new Stack<Node> ();
nodeStack.push(root);
/* Pop all items one by one.
Do following for every popped item
a) print it
b) push its right child
c) push its left child
Note that right child is pushed first
so that left is processed first */
Node pre = null;
while (nodeStack.isEmpty() == false) {
// Pop the top item from stack
Node node = nodeStack.peek();
nodeStack.pop();
// Push right and left children of
// the popped node to stack
if (node.right != null)
nodeStack.push(node.right);
if (node.left != null)
nodeStack.push(node.left);
// check if some previous node exists
if (pre != null) {
// set the right pointer of
// previous node to current
pre.right = node;
}
// set previous node as current node
pre = node;
}
}
// printing using right pointer only
static void printpre(Node root)
{
while (root != null) {
System.out.print(root.data + " ");
root = root.right;
}
}
// Driver code
public static void main(String[] args)
{
/* Constructed binary tree is
10
/ \
8 2
/ \
3 5
*/
Node root = newNode(10);
root.left = newNode(8);
root.right = newNode(2);
root.left.left = newNode(3);
root.left.right = newNode(5);
modifytree(root);
printpre(root);
}
}
Python
# Python code to modify binary tree for # traversal using only right pointer # A binary tree node has data, # left child and right child class newNode(): def __init__(self, data): self.data = data self.left = None self.right = None # An iterative process to set the right # pointer of Binary tree def modifytree( root): # Base Case if (root == None): return # Create an empty stack and append root to it nodeStack = [] nodeStack.append(root) ''' Pop all items one by one. Do following for every popped item a) print b) append its right child c) append its left child Note that right child is appended first so that left is processed first ''' pre = None while (len(nodeStack)): # Pop the top item from stack node = nodeStack[-1] nodeStack.pop() # append right and left children of # the popped node to stack if (node.right): nodeStack.append(node.right) if (node.left): nodeStack.append(node.left) # check if some previous node exists if (pre != None): # set the right pointer of # previous node to current pre.right = node # set previous node as current node pre = node # printing using right pointer only def printpre( root): while (root != None): print(root.data, end = " ") root = root.right # Driver code ''' Constructed binary tree is 10 / \ 8 2 / \ 3 5 ''' root = newNode(10) root.left = newNode(8) root.right = newNode(2) root.left.left = newNode(3) root.left.right = newNode(5) modifytree(root) printpre(root) # This code is contributed by SHUBHAMSINGH10
C#
// C# code to modify binary tree for
// traversal using only right pointer
using System;
using System.Collections;
class GfG
{
// A binary tree node has data,
// left child and right child
public class Node
{
public int data;
public Node left;
public Node right;
}
// Helper function that allocates a new
// node with the given data and NULL
// left and right pointers.
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = null;
node.right = null;
return (node);
}
// An iterative process to set the right
// pointer of Binary tree
static void modifytree(Node root)
{
// Base Case
if (root == null)
return;
// Create an empty stack and Push root to it
Stack nodeStack = new Stack();
nodeStack.Push(root);
/* Pop all items one by one.
Do following for every Popped item
a) print it
b) Push its right child
c) Push its left child
Note that right child is Pushed first
so that left is processed first */
Node pre = null;
while (nodeStack.Count !=0)
{
// Pop the top item from stack
Node node = (Node)nodeStack.Peek();
nodeStack.Pop();
// Push right and left children of
// the Popped node to stack
if (node.right != null)
nodeStack.Push(node.right);
if (node.left != null)
nodeStack.Push(node.left);
// check if some previous node exists
if (pre != null)
{
// set the right pointer of
// previous node to current
pre.right = node;
}
// set previous node as current node
pre = node;
}
}
// printing using right pointer only
static void printpre(Node root)
{
while (root != null)
{
Console.Write(root.data + " ");
root = root.right;
}
}
// Driver code
public static void Main(String []args)
{
/* Constructed binary tree is
10
/ \
8 2
/ \
3 5
*/
Node root = newNode(10);
root.left = newNode(8);
root.right = newNode(2);
root.left.left = newNode(3);
root.left.right = newNode(5);
modifytree(root);
printpre(root);
}
}
// This code is contributed by
// Arnab Kundu
Javascript
<script>
// JavaScript code to modify binary tree for
// traversal using only right pointer
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// Helper function that allocates a new
// node with the given data and NULL
// left and right pointers.
function newNode(data)
{
let node = new Node(data);
return (node);
}
// An iterative process to set the right
// pointer of Binary tree
function modifytree(root)
{
// Base Case
if (root == null)
return;
// Create an empty stack and push root to it
let nodeStack = [];
nodeStack.push(root);
/* Pop all items one by one.
Do following for every popped item
a) print it
b) push its right child
c) push its left child
Note that right child is pushed first
so that left is processed first */
let pre = null;
while (nodeStack.length > 0) {
// Pop the top item from stack
let node = nodeStack[nodeStack.length - 1];
nodeStack.pop();
// Push right and left children of
// the popped node to stack
if (node.right != null)
nodeStack.push(node.right);
if (node.left != null)
nodeStack.push(node.left);
// check if some previous node exists
if (pre != null) {
// set the right pointer of
// previous node to current
pre.right = node;
}
// set previous node as current node
pre = node;
}
}
// printing using right pointer only
function printpre(root)
{
while (root != null) {
document.write(root.data + " ");
root = root.right;
}
}
/* Constructed binary tree is
10
/ \
8 2
/ \
3 5
*/
let root = newNode(10);
root.left = newNode(8);
root.right = newNode(2);
root.left.left = newNode(3);
root.left.right = newNode(5);
modifytree(root);
printpre(root);
</script>