Dado un árbol binario donde cada Node tiene la siguiente estructura.
struct node {
int key;
struct node *left,*right,*random;
}
El puntero aleatorio apunta a cualquier Node aleatorio del árbol binario e incluso puede apuntar a NULL, clonar el árbol binario dado.
Método 1 (usar hash): la idea es almacenar un mapeo de Nodes de árbol dados para clonar Nodes de árbol en la tabla hash. Los siguientes son pasos detallados.
1) Atraviese recursivamente el binario dado y copie el valor clave, el puntero izquierdo y un puntero derecho para clonar el árbol. Mientras copia, almacene el mapeo del Node de árbol dado para clonar el Node de árbol en una tabla hash. En el siguiente pseudocódigo, ‘cloneNode’ es el Node actualmente visitado del árbol de clonación y ‘treeNode’ es el Node actualmente visitado del árbol dado.
cloneNode->key = treeNode->key cloneNode->left = treeNode->left cloneNode->right = treeNode->right map[treeNode] = cloneNode
2) Atraviese recursivamente ambos árboles y establezca punteros aleatorios usando entradas de la tabla hash.
cloneNode->random = map[treeNode->random]
A continuación se muestra la implementación en C++ y Java de la idea anterior. La siguiente implementación usa unordered_map de C++ STL y HashMap en Java. Tenga en cuenta que el mapa no implementa una tabla hash, en realidad se basa en un árbol de búsqueda binaria autoequilibrado.
Implementación:
CPP
// A hashmap based C++ program to clone a binary
// tree with random pointers
#include<iostream>
#include<unordered_map>
using namespace std;
/* A binary tree node has data, pointer to left child,
a pointer to right child and a pointer to
random node*/
struct Node
{
int key;
struct Node* left, *right, *random;
};
/* Helper function that allocates a new Node with the
given data and NULL left, right and random pointers. */
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->random = temp->right = temp->left = NULL;
return (temp);
}
/* Given a binary tree, print its Nodes in inorder*/
void printInorder(Node* node)
{
if (node == NULL)
return;
/* First recur on left subtree */
printInorder(node->left);
/* then print data of Node and its random */
cout << "[" << node->key << " ";
if (node->random == NULL)
cout << "NULL], ";
else
cout << node->random->key << "], ";
/* now recur on right subtree */
printInorder(node->right);
}
/* This function creates clone by copying key
and left and right pointers. This function also
stores mapping from given tree node to clone. */
Node* copyLeftRightNode(Node* treeNode, unordered_map<Node *, Node *> &mymap)
{
if (treeNode == NULL)
return NULL;
Node* cloneNode = newNode(treeNode->key);
mymap[treeNode] = cloneNode;
cloneNode->left = copyLeftRightNode(treeNode->left, mymap);
cloneNode->right = copyLeftRightNode(treeNode->right, mymap);
return cloneNode;
}
// This function copies random node by using the hashmap built by
// copyLeftRightNode()
void copyRandom(Node* treeNode, Node* cloneNode, unordered_map<Node *, Node *> &mymap)
{
if (cloneNode == NULL)
return;
cloneNode->random = mymap[treeNode->random];
copyRandom(treeNode->left, cloneNode->left, mymap);
copyRandom(treeNode->right, cloneNode->right, mymap);
}
// This function makes the clone of given tree. It mainly uses
// copyLeftRightNode() and copyRandom()
Node* cloneTree(Node* tree)
{
if (tree == NULL)
return NULL;
unordered_map<Node *, Node *> mymap;
Node* newTree = copyLeftRightNode(tree, mymap);
copyRandom(tree, newTree, mymap);
return newTree;
}
/* Driver program to test above functions*/
int main()
{
//Test No 1
Node *tree = newNode(1);
tree->left = newNode(2);
tree->right = newNode(3);
tree->left->left = newNode(4);
tree->left->right = newNode(5);
tree->random = tree->left->right;
tree->left->left->random = tree;
tree->left->right->random = tree->right;
// Test No 2
// tree = NULL;
// Test No 3
// tree = newNode(1);
// Test No 4
/* tree = newNode(1);
tree->left = newNode(2);
tree->right = newNode(3);
tree->random = tree->right;
tree->left->random = tree;
*/
cout << "Inorder traversal of original binary tree is: \n";
printInorder(tree);
Node *clone = cloneTree(tree);
cout << "\n\nInorder traversal of cloned binary tree is: \n";
printInorder(clone);
return 0;
}
Java
import java.lang.*;
import java.util.*;
class Tree {
int data;
Tree left, right, random;
Tree(int d)
{
data = d;
left = null;
right = null;
random = null;
}
}
class CloneABT {
public static void main(String[] args)
{
Tree tree = new Tree(1);
tree.left = new Tree(2);
tree.right = new Tree(3);
tree.left.left = new Tree(4);
tree.left.right = new Tree(5);
tree.random = tree.left.right;
tree.left.left.random = tree;
tree.left.right.random = tree.right;
System.out.println(
"Inorder traversal of original binary tree is: \n");
printInorder(tree);
Tree clone = cloneTree(tree);
System.out.println(
"\n\nInorder traversal of cloned binary tree is: \n");
printInorder(clone);
}
public static Tree cloneTree(Tree tree)
{
if (tree == null)
return null;
HashMap<Tree, Tree> map
= new HashMap<>(); // create a hashmap to store
// the randoms
Tree newtree = clonelr(tree, map);
copyrandom(tree, newtree, map);
return newtree;
}
// cloning the left and right tree
public static Tree clonelr(Tree tree,
HashMap<Tree, Tree> map)
{
if (tree == null)
return null;
Tree clonenode = new Tree(tree.data);
map.put(tree, clonenode);
clonenode.left = clonelr(tree.left, map);
clonenode.right = clonelr(tree.right, map);
return clonenode;
}
// setting the random pointers in the cloned tree
public static void copyrandom(Tree tree, Tree clone,
HashMap<Tree, Tree> map)
{
if (clone == null)
return;
clone.random = map.get(tree.random);
copyrandom(tree.left, clone.left, map);
copyrandom(tree.right, clone.right, map);
}
static void printInorder(Tree node)
{
if (node == null)
return;
/* First recur on left subtree */
printInorder(node.left);
/* then print data of Node and its random */
System.out.print("[" + node.data + " ");
if (node.random == null)
System.out.print("null], ");
else
System.out.print(node.data + "]");
/* now recur on right subtree */
printInorder(node.right);
}
public static boolean printInorder(Tree a, Tree b)
{
if ((a == null) && (b == null))
return true;
if (a != null && b != null) {
boolean check
= ((a.data == b.data)
&& printInorder(a.left, b.left)
&& printInorder(a.right, b.right));
if (a.random != null && b.random != null)
return (
check
&& (a.random.data == b.random.data));
if (a.random == b.random)
return check;
return false;
}
return false;
}
public static void clone(Tree root, Tree proot, int n1,
int n2)
{
try {
if (root == null && proot == null)
return;
if (n1 == root.data) {
if (proot.data == n2)
root.random = proot;
else {
clone(root, proot.left, n1, n2);
clone(root, proot.right, n1, n2);
}
}
else {
clone(root.left, proot, n1, n2);
clone(root.right, proot, n1, n2);
}
}
catch (NullPointerException ex) {
}
}
public static void insert(Tree root, int n1, int n2,
char lr)
{
if (root == null)
return;
if (n1 == root.data) {
switch (lr) {
case 'L':
root.left = new Tree(n2);
break;
case 'R':
root.right = new Tree(n2);
break;
}
}
else {
insert(root.left, n1, n2, lr);
insert(root.right, n1, n2, lr);
}
}
}
Producción
Inorder traversal of original binary tree is: [4 1], [2 NULL], [5 3], [1 5], [3 NULL], Inorder traversal of cloned binary tree is: [4 1], [2 NULL], [5 3], [1 5], [3 NULL],
Método 2 (Modificar temporalmente el árbol binario dado):
1. Cree nuevos Nodes en el árbol clonado e inserte cada nuevo Node en el árbol original entre el borde del puntero izquierdo del Node correspondiente en el árbol original (consulte la imagen a continuación).
es decir, si el Node actual es A y su hijo izquierdo es B (A — >> B), entonces se creará un nuevo Node clonado con la clave A (digamos cA) y se pondrá como A — >> cA — >> B (B puede ser un hijo izquierdo NULL o no NULL). El puntero del hijo derecho se establecerá correctamente, es decir, si, para el Node A actual, el hijo derecho es C en el árbol original (A — >> C), entonces a los Nodes clonados correspondientes cA y cC les gustará cA —- >> cC
2. Establezca un puntero aleatorio en el árbol clonado según el árbol original
es decir, si el puntero aleatorio del Node A apunta al Node B, entonces en el árbol clonado, cA apuntará a cB (cA y cB son los nuevos Nodes en el árbol clonado correspondientes a los Nodes A y B en el árbol original)
3. Restaure los punteros izquierdos correctamente tanto en el árbol original como en el clonado
A continuación se muestra la implementación en C++ del algoritmo anterior.
CPP
#include <iostream>
using namespace std;
/* A binary tree node has data, pointer to left child, a pointer to right
child and a pointer to random node*/
struct Node
{
int key;
struct Node* left, *right, *random;
};
/* Helper function that allocates a new Node with the
given data and NULL left, right and random pointers. */
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->random = temp->right = temp->left = NULL;
return (temp);
}
/* Given a binary tree, print its Nodes in inorder*/
void printInorder(Node* node)
{
if (node == NULL)
return;
/* First recur on left subtree */
printInorder(node->left);
/* then print data of Node and its random */
cout << "[" << node->key << " ";
if (node->random == NULL)
cout << "NULL], ";
else
cout << node->random->key << "], ";
/* now recur on right subtree */
printInorder(node->right);
}
// This function creates new nodes cloned tree and puts new cloned node
// in between current node and it's left child
// i.e. if current node is A and it's left child is B ( A --- >> B ),
// then new cloned node with key A will be created (say cA) and
// it will be put as
// A --- >> cA --- >> B
// Here B can be a NULL or a non-NULL left child
// Right child pointer will be set correctly
// i.e. if for current node A, right child is C in original tree
// (A --- >> C) then corresponding cloned nodes cA and cC will like
// cA ---- >> cC
Node* copyLeftRightNode(Node* treeNode)
{
if (treeNode == NULL)
return NULL;
Node* left = treeNode->left;
treeNode->left = newNode(treeNode->key);
treeNode->left->left = left;
if(left != NULL)
left->left = copyLeftRightNode(left);
treeNode->left->right = copyLeftRightNode(treeNode->right);
return treeNode->left;
}
// This function sets random pointer in cloned tree as per original tree
// i.e. if node A's random pointer points to node B, then
// in cloned tree, cA will point to cB (cA and cB are new node in cloned
// tree corresponding to node A and B in original tree)
void copyRandomNode(Node* treeNode, Node* cloneNode)
{
if (treeNode == NULL)
return;
if(treeNode->random != NULL)
cloneNode->random = treeNode->random->left;
else
cloneNode->random = NULL;
if(treeNode->left != NULL && cloneNode->left != NULL)
copyRandomNode(treeNode->left->left, cloneNode->left->left);
copyRandomNode(treeNode->right, cloneNode->right);
}
// This function will restore left pointers correctly in
// both original and cloned tree
void restoreTreeLeftNode(Node* treeNode, Node* cloneNode)
{
if (treeNode == NULL)
return;
if (cloneNode->left != NULL)
{
Node* cloneLeft = cloneNode->left->left;
treeNode->left = treeNode->left->left;
cloneNode->left = cloneLeft;
}
else
treeNode->left = NULL;
restoreTreeLeftNode(treeNode->left, cloneNode->left);
restoreTreeLeftNode(treeNode->right, cloneNode->right);
}
//This function makes the clone of given tree
Node* cloneTree(Node* treeNode)
{
if (treeNode == NULL)
return NULL;
Node* cloneNode = copyLeftRightNode(treeNode);
copyRandomNode(treeNode, cloneNode);
restoreTreeLeftNode(treeNode, cloneNode);
return cloneNode;
}
/* Driver program to test above functions*/
int main()
{
/* //Test No 1
Node *tree = newNode(1);
tree->left = newNode(2);
tree->right = newNode(3);
tree->left->left = newNode(4);
tree->left->right = newNode(5);
tree->random = tree->left->right;
tree->left->left->random = tree;
tree->left->right->random = tree->right;
// Test No 2
// Node *tree = NULL;
/*
// Test No 3
Node *tree = newNode(1);
// Test No 4
Node *tree = newNode(1);
tree->left = newNode(2);
tree->right = newNode(3);
tree->random = tree->right;
tree->left->random = tree;
Test No 5
Node *tree = newNode(1);
tree->left = newNode(2);
tree->right = newNode(3);
tree->left->left = newNode(4);
tree->left->right = newNode(5);
tree->right->left = newNode(6);
tree->right->right = newNode(7);
tree->random = tree->left;
*/
// Test No 6
Node *tree = newNode(10);
Node *n2 = newNode(6);
Node *n3 = newNode(12);
Node *n4 = newNode(5);
Node *n5 = newNode(8);
Node *n6 = newNode(11);
Node *n7 = newNode(13);
Node *n8 = newNode(7);
Node *n9 = newNode(9);
tree->left = n2;
tree->right = n3;
tree->random = n2;
n2->left = n4;
n2->right = n5;
n2->random = n8;
n3->left = n6;
n3->right = n7;
n3->random = n5;
n4->random = n9;
n5->left = n8;
n5->right = n9;
n5->random = tree;
n6->random = n9;
n9->random = n8;
/* Test No 7
Node *tree = newNode(1);
tree->left = newNode(2);
tree->right = newNode(3);
tree->left->random = tree;
tree->right->random = tree->left;
*/
cout << "Inorder traversal of original binary tree is: \n";
printInorder(tree);
Node *clone = cloneTree(tree);
cout << "\n\nInorder traversal of cloned binary tree is: \n";
printInorder(clone);
return 0;
}
Producción
Inorder traversal of original binary tree is: [5 9], [6 7], [7 NULL], [8 10], [9 7], [10 6], [11 9], [12 8], [13 NULL], Inorder traversal of cloned binary tree is: [5 9], [6 7], [7 NULL], [8 10], [9 7], [10 6], [11 9], [12 8], [13 NULL],
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