کلون کردن درخت دودویی با اشاره گرهای تصادفی — راهنمای کاربردی

1struct node {  
2    int key; 
3    struct node *left,*right,*random;
4}

1   cloneNode->random = map[treeNode->random] 

1// A hashmap based C++ program to clone a binary  
2// tree with random pointers 
3#include<iostream> 
4#include<unordered_map> 
5using namespace std; 
6  
7/* A binary tree node has data, pointer to left child, 
8    a pointer to right child and a pointer to  
9    random node*/
10struct Node 
11{ 
12    int key; 
13    struct Node* left, *right, *random; 
14}; 
15  
16/* Helper function that allocates a new Node with the 
17   given data and NULL left, right and random pointers. */
18Node* newNode(int key) 
19{ 
20    Node* temp = new Node; 
21    temp->key = key; 
22    temp->random = temp->right = temp->left = NULL; 
23    return (temp); 
24} 
25  
26/* Given a binary tree, print its Nodes in inorder*/
27void printInorder(Node* node) 
28{ 
29    if (node == NULL) 
30        return; 
31  
32    /* First recur on left sutree */
33    printInorder(node->left); 
34  
35    /* then print data of Node and its random */
36    cout << "[" << node->key << " "; 
37    if (node->random == NULL) 
38        cout << "NULL], "; 
39    else
40        cout << node->random->key << "], "; 
41  
42    /* now recur on right subtree */
43    printInorder(node->right); 
44} 
45  
46// This function creates clone by copying key and left and right pointers 
47// This function also stores mapping from given tree node to clone. 
48Node* copyLeftRightNode(Node* treeNode, unordered_map<Node *, Node *> &mymap) 
49{ 
50    if (treeNode == NULL) 
51        return NULL; 
52    Node* cloneNode = newNode(treeNode->key); 
53    mymap[treeNode] = cloneNode; 
54    cloneNode->left  = copyLeftRightNode(treeNode->left, mymap); 
55    cloneNode->right = copyLeftRightNode(treeNode->right, mymap); 
56    return cloneNode; 
57} 
58  
59// This function copies random node by using the hashmap built by 
60// copyLeftRightNode() 
61void copyRandom(Node* treeNode,  Node* cloneNode, unordered_map<Node *, Node *> &mymap) 
62{ 
63    if (cloneNode == NULL) 
64        return; 
65    cloneNode->random =  mymap[treeNode->random]; 
66    copyRandom(treeNode->left, cloneNode->left, mymap); 
67    copyRandom(treeNode->right, cloneNode->right, mymap); 
68} 
69  
70// This function makes the clone of given tree. It mainly uses 
71// copyLeftRightNode() and copyRandom() 
72Node* cloneTree(Node* tree) 
73{ 
74    if (tree == NULL) 
75        return NULL; 
76    unordered_map<Node *, Node *> mymap; 
77    Node* newTree = copyLeftRightNode(tree, mymap); 
78    copyRandom(tree, newTree, mymap); 
79    return newTree; 
80} 
81  
82/* Driver program to test above functions*/
83int main() 
84{ 
85    //Test No 1 
86    Node *tree = newNode(1); 
87    tree->left = newNode(2); 
88    tree->right = newNode(3); 
89    tree->left->left = newNode(4); 
90    tree->left->right = newNode(5); 
91    tree->random = tree->left->right; 
92    tree->left->left->random = tree; 
93    tree->left->right->random = tree->right; 
94  
95    //  Test No 2 
96    //    tree = NULL; 
97  
98    //  Test No 3 
99    //    tree = newNode(1); 
100  
101    //  Test No 4 
102    /*    tree = newNode(1); 
103        tree->left = newNode(2); 
104        tree->right = newNode(3); 
105        tree->random = tree->right; 
106        tree->left->random = tree; 
107    */
108  
109    cout << "Inorder traversal of original binary tree is: \n"; 
110    printInorder(tree); 
111  
112    Node *clone = cloneTree(tree); 
113  
114    cout << "\n\nInorder traversal of cloned binary tree is: \n"; 
115    printInorder(clone); 
116  
117    return 0; 
118}

1#include <iostream> 
2using namespace std; 
3  
4/* A binary tree node has data, pointer to left child, a pointer to right 
5   child and a pointer to random node*/
6struct Node 
7{ 
8    int key; 
9    struct Node* left, *right, *random; 
10}; 
11  
12/* Helper function that allocates a new Node with the 
13   given data and NULL left, right and random pointers. */
14Node* newNode(int key) 
15{ 
16    Node* temp = new Node; 
17    temp->key = key; 
18    temp->random = temp->right = temp->left = NULL; 
19    return (temp); 
20} 
21  
22/* Given a binary tree, print its Nodes in inorder*/
23void printInorder(Node* node) 
24{ 
25    if (node == NULL) 
26        return; 
27  
28    /* First recur on left sutree */
29    printInorder(node->left); 
30  
31    /* then print data of Node and its random */
32    cout << "[" << node->key << " "; 
33    if (node->random == NULL) 
34        cout << "NULL], "; 
35    else
36        cout << node->random->key << "], "; 
37  
38    /* now recur on right subtree */
39    printInorder(node->right); 
40} 
41  
42// This function creates new nodes cloned tree and puts new cloned node 
43// in between current node and it's left child 
44// i.e. if current node is A and it's left child is B ( A --- >> B ), 
45//      then new cloned node with key A wil be created (say cA) and 
46//      it will be put as 
47//      A --- >> cA --- >> B 
48// Here B can be a NULL or a non-NULL left child 
49// Right child pointer will be set correctly 
50// i.e. if for current node A, right child is C in original tree 
51// (A --- >> C) then corresponding cloned nodes cA and cC will like 
52// cA ---- >> cC 
53Node* copyLeftRightNode(Node* treeNode) 
54{ 
55    if (treeNode == NULL) 
56        return NULL; 
57  
58    Node* left = treeNode->left; 
59    treeNode->left = newNode(treeNode->key); 
60    treeNode->left->left = left; 
61    if(left != NULL) 
62        left->left = copyLeftRightNode(left); 
63  
64    treeNode->left->right = copyLeftRightNode(treeNode->right); 
65    return treeNode->left; 
66} 
67  
68// This function sets random pointer in cloned tree as per original tree 
69// i.e. if node A's random pointer points to node B, then 
70// in cloned tree, cA wil point to cB (cA and cB are new node in cloned 
71// tree corresponding to node A and B in original tree) 
72void copyRandomNode(Node* treeNode, Node* cloneNode) 
73{ 
74    if (treeNode == NULL) 
75        return; 
76    if(treeNode->random != NULL) 
77        cloneNode->random = treeNode->random->left; 
78    else
79        cloneNode->random = NULL; 
80  
81    if(treeNode->left != NULL && cloneNode->left != NULL) 
82        copyRandomNode(treeNode->left->left, cloneNode->left->left); 
83    copyRandomNode(treeNode->right, cloneNode->right); 
84} 
85  
86// This function will restore left pointers correctly in 
87// both original and cloned tree 
88void restoreTreeLeftNode(Node* treeNode, Node* cloneNode) 
89{ 
90    if (treeNode == NULL) 
91        return; 
92    if (cloneNode->left != NULL) 
93    { 
94        Node* cloneLeft = cloneNode->left->left; 
95        treeNode->left = treeNode->left->left; 
96        cloneNode->left = cloneLeft; 
97    } 
98    else
99        treeNode->left = NULL; 
100  
101    restoreTreeLeftNode(treeNode->left, cloneNode->left); 
102    restoreTreeLeftNode(treeNode->right, cloneNode->right); 
103} 
104  
105//This function makes the clone of given tree 
106Node* cloneTree(Node* treeNode) 
107{ 
108    if (treeNode == NULL) 
109        return NULL; 
110    Node* cloneNode = copyLeftRightNode(treeNode); 
111    copyRandomNode(treeNode, cloneNode); 
112    restoreTreeLeftNode(treeNode, cloneNode); 
113    return cloneNode; 
114} 
115  
116  
117/* Driver program to test above functions*/
118int main() 
119{ 
120/*  //Test No 1 
121    Node *tree = newNode(1); 
122    tree->left = newNode(2); 
123    tree->right = newNode(3); 
124    tree->left->left = newNode(4); 
125    tree->left->right = newNode(5); 
126    tree->random = tree->left->right; 
127    tree->left->left->random = tree; 
128    tree->left->right->random = tree->right; 
129  
130//  Test No 2 
131//    Node *tree = NULL; 
132/* 
133//  Test No 3 
134    Node *tree = newNode(1); 
135  
136//  Test No 4 
137    Node *tree = newNode(1); 
138    tree->left = newNode(2); 
139    tree->right = newNode(3); 
140    tree->random = tree->right; 
141    tree->left->random = tree; 
142  
143  Test No 5 
144    Node *tree = newNode(1); 
145    tree->left = newNode(2); 
146    tree->right = newNode(3); 
147    tree->left->left = newNode(4); 
148    tree->left->right = newNode(5); 
149    tree->right->left = newNode(6); 
150    tree->right->right = newNode(7); 
151    tree->random = tree->left; 
152*/
153//    Test No 6 
154    Node *tree = newNode(10); 
155    Node *n2 = newNode(6); 
156    Node *n3 = newNode(12); 
157    Node *n4 = newNode(5); 
158    Node *n5 = newNode(8); 
159    Node *n6 = newNode(11); 
160    Node *n7 = newNode(13); 
161    Node *n8 = newNode(7); 
162    Node *n9 = newNode(9); 
163    tree->left = n2; 
164    tree->right = n3; 
165    tree->random = n2; 
166    n2->left = n4; 
167    n2->right = n5; 
168    n2->random = n8; 
169    n3->left = n6; 
170    n3->right = n7; 
171    n3->random = n5; 
172    n4->random = n9; 
173    n5->left = n8; 
174    n5->right = n9; 
175    n5->random = tree; 
176    n6->random = n9; 
177    n9->random = n8; 
178  
179/*    Test No 7 
180    Node *tree = newNode(1); 
181    tree->left = newNode(2); 
182    tree->right = newNode(3); 
183    tree->left->random = tree; 
184    tree->right->random = tree->left; 
185*/
186    cout << "Inorder traversal of original binary tree is: \n"; 
187    printInorder(tree); 
188  
189    Node *clone = cloneTree(tree); 
190  
191    cout << "\n\nInorder traversal of cloned binary tree is: \n"; 
192    printInorder(clone); 
193  
194    return 0; 
195}